En la teoría matemática de grafos dirigidos , se dice que un grafo está fuertemente conectado si cada vértice es alcanzable desde todos los demás vértices. Los componentes fuertemente conectados de un grafo dirigido forman una partición en subgrafos que a su vez están fuertemente conectados. Es posible probar la fuerte conectividad de un grafo, o encontrar sus componentes fuertemente conectados, en tiempo lineal (es decir, Θ( V + E )).
Un grafo dirigido se denomina fuertemente conexo si existe un camino en cada dirección entre cada par de vértices del grafo. Es decir, existe un camino desde el primer vértice del par hasta el segundo, y existe otro camino desde el segundo vértice hasta el primero. En un grafo dirigido G que puede no estar fuertemente conexo, se dice que un par de vértices u y v están fuertemente conexos entre sí si existe un camino en cada dirección entre ellos.
La relación binaria de estar fuertemente conectado es una relación de equivalencia , y los subgrafos inducidos de sus clases de equivalencia se denominan componentes fuertemente conectados . De manera equivalente, un componente fuertemente conectado de un grafo dirigido G es un subgrafo que está fuertemente conectado, y es máximo con esta propiedad: no se pueden incluir aristas o vértices adicionales de G en el subgrafo sin romper su propiedad de estar fuertemente conectado. La colección de componentes fuertemente conectados forma una partición del conjunto de vértices de G . Un componente fuertemente conectado C se denomina trivial cuando C consiste en un solo vértice que no está conectado consigo mismo con una arista, y no trivial en caso contrario. [1]
Si cada componente fuertemente conexo se contrae a un solo vértice, el grafo resultante es un grafo acíclico dirigido , 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 está fuertemente conexo y cada componente fuertemente conexo no trivial contiene al menos un ciclo dirigido.
Varios algoritmos basados en la búsqueda en profundidad calculan componentes fuertemente conectados en tiempo lineal.
Aunque el algoritmo de Kosaraju es conceptualmente simple, el de Tarjan y el algoritmo basado en rutas requieren solo una búsqueda en profundidad en lugar de dos.
Los algoritmos de tiempo lineal anteriores 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 generalmente se denominan 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, una o ninguna de las búsquedas. Se puede demostrar que un componente fuertemente conectado tiene que estar contenido en uno de los subconjuntos. El subconjunto de vértices alcanzado por ambas búsquedas forma un componente fuertemente conectado, y luego el algoritmo recurre sobre los otros 3 subconjuntos.
Se muestra que el tiempo de ejecución secuencial esperado de este algoritmo es O( n log n ), un factor de O(log n ) más que 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 amplitud (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 si un grafo no tiene aristas, el algoritmo requiere O( n ) niveles de recursiones).
Blelloch et al. [8] en 2016 demuestra que si las consultas de accesibilidad se aplican en un orden aleatorio, el límite de costo de O( n log n ) aún se mantiene. Además, las consultas se pueden agrupar de manera que se dupliquen los prefijos (es decir, 1, 2, 4, 8 consultas) y ejecutar simultáneamente en una ronda. El alcance general de este algoritmo es de log 2 n consultas de accesibilidad, que es probablemente el paralelismo óptimo que se puede lograr utilizando el enfoque basado en la accesibilidad.
Peter M. Maurer describe un algoritmo para generar grafos fuertemente conectados al azar, [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 un grafo 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 en n nodos, sin restricción en los tipos de estructuras que se pueden generar.
Los algoritmos para encontrar componentes fuertemente conectados se pueden utilizar para resolver problemas de 2-satisfacibilidad (sistemas de variables booleanas con restricciones en los valores de pares de variables): como Aspvall, Plass y Tarjan (1979) demostraron, una instancia de 2-satisfacibilidad es insatisfacible si y solo si hay una variable v tal que v y su negación están ambas contenidas en el mismo componente fuertemente conectado del gráfico 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 los bordes de un gráfico bipartito , según puedan o no ser parte de una correspondencia perfecta en el gráfico. [11]
Un gráfico dirigido está fuertemente conectado si y solo si tiene una descomposición en orejas , una partición de los bordes en una secuencia de caminos y ciclos dirigidos de manera que el primer subgráfico de la secuencia es un ciclo y cada subgráfico subsiguiente es un ciclo que comparte un vértice con subgráficos anteriores o un camino que comparte sus dos puntos finales con subgráficos anteriores.
Según el teorema de Robbins , un grafo no dirigido puede estar orientado de tal manera que se vuelva fuertemente conexo, si y solo si es conexo por dos aristas . 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]