Hispanopedia Wiki
Articulo de referencia

Componente fuertemente conectado

Gráfico con áreas sombreadas que muestran componentes fuertemente conectados. En la teoría matemática de grafos dirigidos , se dice que un grafo es fuertemente conexo si cada vé...

Hispanopedia WikiContenido en espanolLectura gratuita
Gráfico con áreas sombreadas que muestran componentes fuertemente conectados.

En la teoría matemática de grafos dirigidos , se dice que un grafo es fuertemente conexo si cada vértice es alcanzable desde cualquier otro vértice. Los componentes fuertemente conexos de un grafo dirigido forman una partición en subgrafos que también son fuertemente conexos. Es posible comprobar la conectividad fuerte de un grafo, o hallar sus componentes fuertemente conexos, en tiempo lineal (es decir, Θ( V  + E )). 

Definiciones

Un grafo dirigido se considera fuertemente conexo si existe un camino en cada dirección entre cada par de vértices. Es decir, existe un camino desde el primer vértice del par hasta el segundo, y otro camino desde el segundo vértice hasta el primero. En un grafo dirigido G que no necesariamente es fuertemente conexo, se dice que un par de vértices u y v están fuertemente conexos si existe un camino en cada dirección entre ellos.

La relación binaria de ser fuertemente conexo es una relación de equivalencia , y los subgrafos inducidos de sus clases de equivalencia se denominan componentes fuertemente conexas . De forma equivalente, una componente fuertemente conexa de un grafo dirigido G es un subgrafo que es fuertemente conexo y es maximal con esta propiedad: ningún conjunto de aristas o vértices adicionales de G puede incluirse en el subgrafo sin romper su propiedad de ser fuertemente conexo. La colección de componentes fuertemente conexas forma una partición del conjunto de vértices de G. Una componente fuertemente conexa C se denomina trivial cuando C consta de un único vértice que no está conectado a sí mismo por una arista, y no trivial en caso contrario. [ 1 ]

El grafo acíclico dirigido amarillo es la condensación del grafo dirigido azul. Se forma al contraer cada componente fuertemente conexa del grafo azul en un único vértice amarillo.

Si cada componente fuertemente conexa se contrae a un solo vértice, el grafo resultante es un grafo dirigido acíclico , la condensación de G. Un grafo dirigido es acíclico si y solo si no tiene subgrafos fuertemente conexos con más de un vértice, porque un ciclo dirigido es fuertemente conexo y cada componente fuertemente conexa no trivial contiene al menos un ciclo dirigido.

Algoritmos

Algoritmos de tiempo lineal basados ​​en DFS

Varios algoritmos basados ​​en la búsqueda en profundidad calculan componentes fuertemente conexas en tiempo lineal.

  • El algoritmo de Kosaraju utiliza dos pasadas de búsqueda en profundidad. La primera, en el grafo original, se utiliza para elegir el orden en que el bucle externo de la segunda búsqueda en profundidad comprueba si los vértices ya han sido visitados y los explora recursivamente si no lo han sido. La segunda búsqueda en profundidad se realiza en el grafo transpuesto del grafo original, y cada exploración recursiva encuentra un único componente fuertemente conexo nuevo. [ 2 ] [ 3 ] Recibe su nombre de S. Rao Kosaraju , quien lo describió (pero no publicó sus resultados) en 1978; Micha Sharir lo publicó posteriormente en 1981. [ 4 ]
  • El algoritmo de componentes fuertemente conectados de Tarjan , publicado por Robert Tarjan en 1972, [ 5 ] realiza una sola pasada de búsqueda en profundidad. Mantiene una pila de vértices que han sido explorados por la búsqueda pero que aún no se han asignado a un componente, y calcula los "números bajos" de cada vértice (un número de índice del ancestro más alto alcanzable en un paso desde un descendiente del vértice) que utiliza para determinar cuándo se debe extraer un conjunto de vértices de la pila para formar un nuevo componente.
  • El algoritmo de componentes fuertes basado en rutas utiliza una búsqueda en profundidad, similar al algoritmo de Tarjan, pero con dos pilas. Una de las pilas se utiliza para registrar los vértices que aún no se han asignado a componentes, mientras que la otra registra la ruta actual en el árbol de búsqueda en profundidad. La primera versión de tiempo lineal de este algoritmo fue publicada por Edsger W. Dijkstra en 1976. [ 6 ]

Si bien el algoritmo de Kosaraju es conceptualmente simple, el de Tarjan y el algoritmo basado en rutas solo requieren una búsqueda en profundidad en lugar de dos.

Algoritmos basados ​​en la accesibilidad

Los algoritmos anteriores de tiempo lineal se basan en la búsqueda en profundidad, que generalmente se considera difícil de paralelizar. Fleischer et al. [ 7 ] en 2000 propusieron un enfoque de divide y vencerás basado en consultas de alcanzabilidad , y dichos algoritmos se denominan habitualmente algoritmos SCC basados ​​en alcanzabilidad. La idea de este enfoque es elegir un vértice pivote aleatorio y aplicar consultas de alcanzabilidad hacia adelante y hacia atrás desde este vértice. Las dos consultas dividen el conjunto de vértices en 4 subconjuntos: vértices alcanzados por ambas búsquedas, por una sola o por ninguna. Se puede demostrar que un componente fuertemente conectado debe estar contenido en uno de los subconjuntos. El subconjunto de vértices alcanzado por ambas búsquedas forma un componente fuertemente conectado, y el algoritmo recurre entonces sobre los otros 3 subconjuntos.

Se demuestra que el tiempo de ejecución secuencial esperado de este algoritmo es O( n  log n ), un factor de O(log n ) mayor que el de los algoritmos clásicos. El paralelismo proviene de: (1) las consultas de alcanzabilidad se pueden paralelizar más fácilmente (por ejemplo, mediante una búsqueda en anchura (BFS), y puede ser rápido si el diámetro del grafo es pequeño); y (2) la independencia entre las subtareas en el proceso de divide y vencerás. Este algoritmo funciona bien en grafos del mundo real, [ 3 ] pero no tiene garantía teórica sobre el paralelismo (considere que si un grafo no tiene aristas, el algoritmo requiere O( n ) niveles de recursión).

Blelloch et al. [ 8 ] en 2016 demostraron que, si las consultas de alcanzabilidad se aplican en un orden aleatorio, el límite de costo de O( n  log n ) se mantiene. Además, las consultas se pueden agrupar duplicando el prefijo (es decir, 1, 2, 4, 8 consultas) y ejecutarse simultáneamente en una sola ronda. El alcance total de este algoritmo es log 2 n consultas de alcanzabilidad, lo que probablemente representa el paralelismo óptimo que se puede lograr con el enfoque basado en alcanzabilidad.

Generación de grafos aleatorios fuertemente conectados

Peter M. Maurer describe un algoritmo para generar grafos fuertemente conectados aleatorios, [ 9 ] basado en una modificación de un algoritmo para el aumento de la conectividad fuerte , el problema de agregar la menor cantidad posible de aristas para hacer que un grafo sea fuertemente conectado. Cuando se utiliza junto con los modelos de Gilbert o Erdős-Rényi con reetiquetado de nodos, el algoritmo es capaz de generar cualquier grafo fuertemente conectado de n nodos, sin restricciones en los tipos de estructuras que se pueden generar.

Aplicaciones

Los algoritmos para encontrar componentes fuertemente conexas pueden utilizarse para resolver problemas de 2-satisfacibilidad (sistemas de variables booleanas con restricciones en los valores de pares de variables): como demostraron Aspvall, Plass y Tarjan (1979) , una instancia de 2-satisfacibilidad es insatisfacible si y solo si existe una variable v tal que v y su negación están contenidas en la misma componente fuertemente conexa del grafo de implicación de la instancia. [ 10 ]

Los componentes fuertemente conectados también se utilizan para calcular la descomposición de Dulmage-Mendelsohn , una clasificación de las aristas de un grafo bipartito , según si pueden o no formar parte de un emparejamiento perfecto en el grafo. [ 11 ]

Un grafo dirigido es fuertemente conexo si y solo si tiene una descomposición en orejas , una partición de las aristas en una secuencia de caminos dirigidos y ciclos tal que el primer subgrafo de la secuencia es un ciclo, y cada subgrafo subsiguiente es o bien un ciclo que comparte un vértice con subgrafos anteriores, o bien un camino que comparte sus dos extremos con subgrafos anteriores.

Según el teorema de Robbins , un grafo no dirigido puede orientarse de tal manera que se vuelva fuertemente conexo, si y solo si es 2-arista-conexo . Una forma de demostrar este resultado es encontrar una descomposición en orejas del grafo no dirigido subyacente y luego orientar cada oreja de manera consistente. [ 12 ]

Véase también

Referencias

  1. ↑ Nuutila, Esko; Soisalon-Soininen, Eljas (1994), "Sobre cómo encontrar los componentes fuertemente conectados en un grafo dirigido", Information Processing Letters , 49 (1): 9–14 , doi : 10.1016/0020-0190(94)90047-7
  2. ↑ Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7Sección 22.5, págs.  552 – 557.
  3. 1 2 Hong, Sungpack; Rodia, Nicole C.; Olukotun, Kunle (2013), "Sobre la detección paralela rápida de componentes fuertemente conectados (SCC) en grafos de mundo pequeño" (PDF) , Actas de la Conferencia Internacional sobre Computación de Alto Rendimiento, Redes, Almacenamiento y Análisis - SC '13 , págs. 1–11 , doi : 10.1145/2503210.2503246 , ISBN  9781450323789, S2CID 2156324 
  4. ↑ Sharir, Micha (1981), "Un algoritmo de conectividad fuerte y sus aplicaciones en el análisis de flujo de datos", Computers & Mathematics with Applications , 7 : 67–72 , doi : 10.1016/0898-1221(81)90008-0
  5. ↑ Tarjan, RE (1972), "Búsqueda en profundidad y algoritmos de grafos lineales", SIAM Journal on Computing , 1 (2): 146– 160, doi : 10.1137/0201010 , S2CID 16467262 
  6. ↑ Dijkstra, Edsger (1976), A Discipline of Programming , NJ: Prentice Hall, Cap. 25 .
  7. ↑ Fleischer, Lisa K.; Hendrickson, Bruce; Pınar, Ali (2000), "Sobre la identificación de componentes fuertemente conectados en paralelo" (PDF) , Procesamiento paralelo y distribuido , Lecture Notes in Computer Science, vol. 1800, pp. 505–511 , doi : 10.1007/3-540-45591-4_68 , ISBN   978-3-540-67442-9
  8. ↑ Blelloch, Guy E.; Gu, Yan; Shun, Julian; Sun, Yihan (2016), "Paralelismo en algoritmos incrementales aleatorios" (PDF) , Actas del 28.º Simposio ACM sobre paralelismo en algoritmos y arquitecturas - SPAA '16 , págs. 467–478 , arXiv : 1810.05303 , doi : 10.1145/2935764.2935766 , hdl : 1721.1/146176 , ISBN  9781450342100.
  9. ↑ Maurer, PM (febrero de 2018), Generación de grafos aleatorios fuertemente conectados (PDF) , Conferencia Internacional sobre Modelado, Simulación y Métodos Visuales MSV'17, CSREA Press, ISBN 978-1-60132-465-8Consultado el 27 de diciembre de 2019 .
  10. ↑ Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "Un algoritmo de tiempo lineal para probar la veracidad de ciertas fórmulas booleanas cuantificadas", Information Processing Letters , 8 (3): 121– 123, doi : 10.1016/0020-0190(79)90002-4.
  11. ↑ Dulmage, AL y Mendelsohn, NS (1958), "Recubrimientos de grafos bipartitos", Can. J. Math. , 10 : 517– 534, doi : 10.4153/cjm-1958-052-0 , S2CID 123363425 .
  12. ↑ Robbins, HE (1939), "Un teorema sobre grafos, con una aplicación a un problema de control de tráfico", American Mathematical Monthly , 46 (5): 281–283 , doi : 10.2307/2303897 , JSTOR 2303897 .
  • Implementación en Java para el cálculo de componentes fuertemente conexas en la biblioteca jBPT (véase la clase StronglyConnectedComponents).
  • Implementación en C++ de componentes fuertemente conectados