LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

El algoritmo de Tarjan es un algoritmo en teoría de grafos para encontrar los componentes fuertemente conectados de un grafo dirigido . Se ejecuta en tiempo lineal , coincidiendo con el límite de tiempo para métodos alternativos que incluyen el algoritmo de Kosaraju y el algoritmo de componente fuerte basado en la ruta . El algoritmo de Tarjan lleva el nombre de su inventor, Robert Tarjan .

Algoritmo de componentes fuertemente conectados de Tarjan

Animación del algoritmo de Tarjan
Estructura de datos	Grafico
El peor de los casos	$${\ displaystyle O (| V | + | E |)}

Descripción general [ editar ]

El algoritmo toma un gráfico dirigido como entrada y produce una partición de los vértices del gráfico en los componentes fuertemente conectados del gráfico. Cada vértice del gráfico aparece exactamente en uno de los componentes fuertemente conectados. Cualquier vértice que no esté en un ciclo dirigido forma un componente fuertemente conectado por sí mismo: por ejemplo, un vértice cuyo grado de entrada o salida es 0, o cualquier vértice de un gráfico acíclico.

La idea básica del algoritmo es la siguiente: una búsqueda de profundidad primero comienza desde un nodo de inicio arbitrario (y las búsquedas de profundidad primero posteriores se realizan en los nodos que aún no se han encontrado). Como es habitual con la búsqueda de profundidad primero, la búsqueda visita cada nodo del gráfico exactamente una vez, y se niega a volver a visitar cualquier nodo que ya haya sido visitado. Por lo tanto, la colección de árboles de búsqueda es un bosque que abarca el gráfico. Los componentes fuertemente conectados se recuperarán como ciertos subárboles de este bosque. Las raíces de estos subárboles se denominan "raíces" de los componentes fuertemente conectados. Cualquier nodo de un componente fuertemente conectado podría servir como raíz, si resulta ser el primer nodo del componente descubierto por la búsqueda.

Pila invariante [ editar ]

Los nodos se colocan en una pila en el orden en que se visitan. Cuando la búsqueda de profundidad primero visita de forma recursiva un nodo vy sus descendientes, no todos esos nodos se sacan necesariamente de la pila cuando regresa esta llamada recursiva. La propiedad invariante crucial es que un nodo permanece en la pila después de haber sido visitado si y solo si existe una ruta en el gráfico de entrada desde él a algún nodo anterior en la pila.

Al final de la llamada que visita vy sus descendientes, sabemos si vtiene una ruta a algún nodo anterior en la pila. Si es así, la llamada regresa, dejando ven la pila para preservar la invariante. De lo contrario, vdebe ser la raíz de su componente fuertemente conectado, que consiste en, vjunto con los nodos más tarde en la pila que v(todos estos nodos tienen rutas de regreso vpero no a ningún nodo anterior, porque si tenían rutas a nodos anteriores, entonces vtambién tendría rutas a nodos anteriores que es falso). El componente conectado enraizado en ventonces se saca de la pila y se devuelve, conservando nuevamente la invariante.

Contabilidad [ editar ]

A cada nodo vse le asigna un número entero único v.index, que numera los nodos consecutivamente en el orden en que se descubren. También mantiene un valor v.lowlinkque representa el índice más pequeño de cualquier nodo conocido para ser alcanzable a partir de va través de v'es subárbol DFS, incluyendo ven sí. Por vlo tanto, debe dejarse en la pila if v.lowlink < v.index, mientras que v debe eliminarse como la raíz de un componente fuertemente conectado if v.lowlink == v.index. El valor v.lowlinkse calcula durante la búsqueda de profundidad desde v, ya que esto encuentra los nodos a los que se puede acceder v.

El algoritmo en pseudocódigo [ editar ]

 el algoritmo tarjan es 
  entrada: gráfico G = ( V , E )
   salida: conjunto de componentes fuertemente conectados (conjuntos de vértices)

  index  : = 0
   S  : = stack vacío
   para cada  v  en  V  do 
    if ( v .index no está definido) luego 
      strongconnect ( v )
     end si 
  end para

  function strongconnect ( v )
     // Establezca el índice de profundidad para v en el índice no utilizado más pequeño 
    v .index: = index 
    v .lowlink: = index 
    index  : = index + 1
     S .push ( v )
     v .onStack: = true

    // Considere sucesores de v 
    para cada ( v , w ) en  E  do 
      if ( w .index no está definido) entonces 
        // El sucesor w aún no ha sido visitado; recurse en él 
        strongconnect ( w )
         v .lowlink: = min ( v .lowlink, w .lowlink)
       más si ( w .onStack) entonces 
        // El sucesor w está en la pila S y por lo tanto en el SCC actual 
        // Si w no está en la pila, entonces ( v , w) es un borde cruzado en el árbol DFS y debe ignorarse 
        // Nota: La siguiente línea puede parecer extraña, pero es correcta. 
        // Dice w.index no w.lowlink; eso es deliberado y del documento original 
        v .lowlink: = min ( v .lowlink, w .index)
       end if 
    end for

    // Si v es un nodo raíz,
     abre la pila y genera un SCC if ( v .lowlink = v .index) luego
      iniciar un nuevo componente fuertemente conectado
      repetir 
        w  : = S .pop ()
         w .onStack: = false
        agregue w al componente actual fuertemente conectado
       mientras ( w  ! = v )
      salida del componente actual fuertemente conectado
    fin si 
  función final

La indexvariable es el contador de número de nodo de búsqueda de profundidad primero. Ses la pila de nodos, que comienza vacía y almacena el historial de nodos explorados pero aún no comprometidos con un componente fuertemente conectado. Tenga en cuenta que esta no es la pila normal de búsqueda de profundidad primero, ya que los nodos no aparecen cuando la búsqueda vuelve al árbol; solo aparecen cuando se ha encontrado un componente completamente conectado.

El bucle más externo busca cada nodo que aún no ha sido visitado, asegurando que los nodos a los que no se pueda acceder desde el primer nodo aún se atraviesen. La función strongconnectrealiza una sola búsqueda en profundidad del gráfico, encuentra todos los sucesores del nodo ve informa todos los componentes fuertemente conectados de ese subgrafo.

Cuando cada nodo termina de recurrir, si su enlace bajo todavía está establecido en su índice, entonces es el nodo raíz de un componente fuertemente conectado, formado por todos los nodos sobre él en la pila. El algoritmo muestra la pila hasta e incluyendo el nodo actual, y presenta todos estos nodos como un componente fuertemente conectado.

Tenga en cuenta que es la forma correcta de actualizar si está en la pila. Como ya está en la pila, es un back-edge en el árbol DFS y, por lo tanto, no está en el subárbol de . Debido a que tiene en cuenta nodos accesibles solo a través de los nodos en el subárbol de debemos detenernos y usar en lugar de . v.lowlink := min(v.lowlink, w.index) v.lowlinkww(v, w)wvv.lowlinkvww.indexw.lowlink

Complejidad [ editar ]

Complejidad de tiempo : el procedimiento de Tarjan se llama una vez para cada nodo; La declaración general considera cada ventaja como máximo una vez. Por lo tanto, el tiempo de ejecución del algoritmo es lineal en el número de aristas y nodos en G, es decir$${\ displaystyle O (| V | + | E |)}.

Para lograr esta complejidad, la prueba de si westá en la pila debe hacerse en tiempo constante. Esto se puede hacer, por ejemplo, almacenando una bandera en cada nodo que indique si está en la pila, y realizando esta prueba examinando la bandera.

Complejidad espacial : el procedimiento de Tarjan requiere dos palabras de datos suplementarios por vértice para los campos indexy lowlink, junto con un bit para onStacky otro para determinar cuándo indexno está definido. Además, se requiere una palabra en cada marco de pila para mantener vy otra para la posición actual en la lista de bordes. Finalmente, el tamaño del peor caso de la pila Sdebe ser$${\ displaystyle | V |}(es decir, cuando el gráfico es un componente gigante). Esto da un análisis final de$${\ displaystyle O (| V | \ cdot (2 + 5w))} dónde $${\ displaystyle w}es el tamaño de la palabra máquina La variación de Nuutila y Soisalon-Soininen redujo esto a$${\ displaystyle O (| V | \ cdot (1 + 4w))} y, posteriormente, el de Pearce solo requiere $${\ displaystyle O (| V | \ cdot (1 + 3w))}. ^[2] [3]

Observaciones adicionales [ editar ]

Si bien no hay nada especial sobre el orden de los nodos dentro de cada componente fuertemente conectado, una propiedad útil del algoritmo es que no se identificará ningún componente fuertemente conectado antes que ninguno de sus sucesores. Por lo tanto, el orden en el que se identifican los componentes fuertemente conectados constituye un tipo topológico inverso del DAG formado por los componentes fuertemente conectados. ^[4]

Donald Knuth describió el algoritmo de Tarjan como una de sus implementaciones favoritas en el libro The Stanford GraphBase . ^[5]

También escribió: ^[6]

Las estructuras de datos que ideó para este problema se unen de una manera increíblemente hermosa, de modo que las cantidades que necesita mirar mientras explora un gráfico dirigido siempre están mágicamente a su alcance. Y su algoritmo también realiza la clasificación topológica como subproducto.

subgrafo isomorfismo problema es una tarea computacional en el que dos gráficos G y H se dan como entrada, y uno debe determinar si G contiene un subgrafo que es isomorfo a H . El isomorfismo del subgrafo es una generalización tanto del problema de la camarilla máxima como del problema de probar si un gráfico contiene un ciclo hamiltoniano y, por lo tanto, es NP completo . ^[1] Sin embargo, ciertos otros casos de isomorfismo subgráfico pueden resolverse en tiempo polinómico. ^[2]

A veces, la coincidencia de subgrafo de nombre también se usa para el mismo problema. Este nombre pone énfasis en encontrar un subgráfico como opuesto al simple problema de decisión.

Problema de decisión y complejidad computacional [ editar ]

Para probar que el isomorfismo del subgrafo es NP-completo, debe formularse como un problema de decisión . La entrada para el problema de decisión es un par de gráficos G y H . La respuesta al problema es positiva si H es isomórfica a una subgrafía de G , y negativa de lo contrario.

Pregunta formal:

Dejar $${\ displaystyle G = (V, E)}, $${\ displaystyle H = (V ^ {\ prime}, E ^ {\ prime})}Ser gráficos. ¿Hay un subgrafo?$${\ displaystyle G_ {0} = (V_ {0}, E_ {0}): V_ {0} \ subseteq V, E_ {0} \ subseteq E \ cap (V_ {0} \ veces V_ {0})} tal que $${\ displaystyle G_ {0} \ cong H}? Es decir, ¿existe una biyección? $${\ displaystyle f \ colon V_ {0} \ rightarrow V ^ {\ prime}} tal que $${\ displaystyle (v_ {1}, v_ {2}) \ en E_ {0} \ Rightarrow (f (v_ {1}), f (v_ {2})) \ en E ^ {\ prime}}?

La prueba de que el isomorfismo del subgrafo es NP completo es simple y se basa en la reducción del problema de camarilla , un problema de decisión de NP completo en el que la entrada es un solo gráfico G y un número k , y la pregunta es si G contiene un subgráfico completo con k vértices. Para traducir esto a un problema de isomorfismo subgráfico, simplemente deje que H sea ​​el gráfico completo K _k ; entonces la respuesta al subgrafo problema de isomorfismo para G y H es igual a la respuesta al problema de camarilla para G y k. Dado que el problema de la camarilla es NP completo, esta reducción de tiempo múltiple polinomial muestra que el isomorfismo del subgrafo también es NP completo. ^[3]

Una reducción alternativa de la ciclo hamiltoniano problema se traduce en una gráfica G que va a ser probado para Hamiltonicity en el par de gráficos G y H , donde H es un ciclo que tienen el mismo número de vértices como G . Debido a que el problema del ciclo hamiltoniano es NP completo incluso para gráficos planos , esto muestra que el isomorfismo del subgrafo permanece NP completo incluso en el caso plano. ^[4]

El isomorfismo de subgrafo es una generalización del problema de isomorfismo de grafos , que pregunta si G es isomorfo a H : la respuesta al problema de isomorfismo de grafos es verdadera si y solo si G y H tienen los mismos números de vértices y bordes y el problema de isomorfismo de subgrafo para G y H es cierto. Sin embargo, el estado teórico de la complejidad del isomorfismo gráfico sigue siendo una pregunta abierta.

En el contexto de la conjetura de Aanderaa-Karp-Rosenberg sobre la complejidad de la consulta de las propiedades del gráfico monótono, Gröger (1992) mostró que cualquier problema de isomorfismo de subgrafo tiene complejidad de consulta Ω ( n ^3/2 ); es decir, resolver el isomorfismo del subgrafo requiere un algoritmo para verificar la presencia o ausencia en la entrada de Ω ( n ^3/2 ) diferentes bordes en el gráfico. ^[5]

Algoritmos [ editar ]

Ullmann (1976) describe un procedimiento de retroceso recursivo para resolver el problema de isomorfismo del subgrafo. Aunque su tiempo de ejecución es, en general, exponencial, toma tiempo polinomial para cualquier elección fija de H (con un polinomio que depende de la elección de H ). Cuando G es un gráfico plano (o más generalmente un gráfico de expansión acotada ) y H es fijo, el tiempo de ejecución del isomorfismo del subgrafo puede reducirse a tiempo lineal . ^[2]

Ullmann (2010) es una actualización sustancial del artículo sobre el algoritmo de isomorfismo del subgrafo de 1976.

Cordella (2004) propuso en 2004 otro algoritmo basado en Ullmann's, VF2, que mejora el proceso de refinamiento usando diferentes heurísticas y usa significativamente menos memoria.

Bonnici (2013) propuso un mejor algoritmo, que mejora el orden inicial de los vértices utilizando algunas heurísticas.

Aplicaciones [ editar ]

Como subgrafo, se ha aplicado el isomorfismo en el área de la quimioinformática para encontrar similitudes entre los compuestos químicos a partir de su fórmula estructural; a menudo en esta área se usa el término búsqueda de subestructura . ^[6] Una estructura de consulta a menudo se define gráficamente utilizando un programa editor de estructura ; Los sistemas de bases de datos basados ​​en SMILES suelen definir consultas utilizando SMARTS , una extensión de SMILES .

El problema estrechamente relacionado de contar el número de copias isomórficas de un gráfico H en un gráfico más grande G se ha aplicado al descubrimiento de patrones en bases de datos, ^[7] la bioinformática de las redes de interacción proteína-proteína, ^[8] y en métodos de gráfico aleatorio exponencial para modelar matemáticamente las redes sociales . ^[9]

Ohlrich y col. (1993) describen una aplicación del isomorfismo subgráfico en el diseño asistido por computadora de circuitos electrónicos . La coincidencia de subgrafos es también un subpaso en la reescritura de gráficos (la que requiere más tiempo de ejecución) y, por lo tanto, la ofrecen las herramientas de reescritura de gráficos .

El problema también es de interés en la inteligencia artificial , donde se considera parte de una serie de patrones coincidentes en problemas de gráficos; Una extensión del isomorfismo del subgrafo conocida como minería de grafos también es de interés en esa área.