Componente fuertemente conectado

En la teoría matemática de los grafos dirigidos, se dice que un grafo está fuertemente conexo si cada vértice es accesible desde todos los demás vértices. Los componentes fuertemente conectados de un gráfico dirigido arbitrario forman una partición en subgrafos que a su vez están fuertemente conectados. Es posible probar la fuerte conectividad de un gráfico, o encontrar sus componentes fuertemente conectados, en tiempo lineal (es decir, Θ(V + E)).

Definiciones

Un gráfico dirigido se llama fuertemente conectado si hay un camino en cada dirección entre cada par de vértices del gráfico. 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 puede no estar fuertemente conectado, se dice que un par de vértices u y v están fuertemente conectados entre sí. si hay un camino en cada dirección entre ellos.

La relación binaria de estar fuertemente conectada es una relación de equivalencia, y los subgrafos inducidos de sus clases de equivalencia se llaman componentes fuertemente conectados. Equivalentemente, un componente fuertemente conectado de un gráfico dirigido G es un subgrafo que está fuertemente conectado, y es maximal con esta propiedad: no hay bordes adicionales o vértices de G se puede incluir 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 G. Un componente fuertemente conectado ${displaystyle C}$ se llama trivial cuando ${displaystyle C}$ consiste en un solo vértice que no está conectado a sí mismo con un borde y non-trivial de lo contrario.

Si cada componente fuertemente conectado se contrae a un solo vértice, el gráfico resultante es un gráfico acíclico dirigido, la condensación de G. Un gráfico dirigido es acíclico si y sólo si no tiene subgrafos fuertemente conectados con más de un vértice, porque un ciclo dirigido está fuertemente conectado y cada componente no trivial fuertemente conectado 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 conectados en tiempo lineal.

• El algoritmo de Kosaraju utiliza dos pases de búsqueda de profundidad. El primero, en el gráfico original, se utiliza para elegir el orden en el que el bucle exterior de las segundas pruebas de búsqueda de profundidad-primera vertices por haber sido visitado ya y recurrentemente los explora si no. La segunda búsqueda de profundidad-primera es en el gráfico transpose del gráfico original, y cada exploración recursiva encuentra un solo nuevo componente fuertemente conectado. Es nombrado después de S. Rao Kosaraju, quien lo describió (pero no publicó sus resultados) en 1978; Micha Sharir posteriormente lo publicó en 1981.
• El algoritmo de componentes fuertemente conectados de Tarjan, publicado por Robert Tarjan en 1972, realiza un solo paso de búsqueda de profundidad. Mantiene una pila de vértices que han sido exploradas por la búsqueda pero no asignada aún a un componente, y calcula "números bajos" de cada vértice (número índice del antepasado más alto alcanzable en un paso de un descendiente del vértice) que utiliza para determinar cuándo un conjunto de vértices debe ser sacado de la pila en un nuevo componente.
• El algoritmo de componente fuerte basado en la trayectoria utiliza una búsqueda de profundidad primera, como el algoritmo de Tarjan, pero con dos pilas. Una de las pilas se utiliza para hacer un seguimiento de los vértices que aún no se asignan a los componentes, mientras que la otra mantiene la pista actual en el árbol de búsqueda de profundidad primero. La primera versión lineal de este algoritmo fue publicada por Edsger W. Dijkstra en 1976.

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.

Algoritmos basados en accesibilidad

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. en 2000 propuso un enfoque de divide y vencerás basado en consultas de accesibilidad, y estos algoritmos generalmente se denominan algoritmos SCC basados en la accesibilidad. La idea de este enfoque es elegir un vértice de pivote aleatorio y aplicar consultas de accesibilidad 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, por una o por ninguna de las búsquedas. Se puede demostrar que un componente fuertemente conexo debe 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 en 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 accesibilidad se pueden paralelizar más fácilmente (por ejemplo, mediante una búsqueda en amplitud (BFS), y puede ser rápida si el diámetro del gráfico es pequeño); y (2) la independencia entre las subtareas en el proceso de divide y vencerás. Este algoritmo funciona bien en gráficos del mundo real, pero no tiene garantía teórica sobre el paralelismo (considere que si un gráfico no tiene aristas, el algoritmo requiere O(n) niveles de recursividad).

Blelloch et al. en 2016 muestra que si las consultas de accesibilidad se aplican en orden aleatorio, el límite de costo de O(n log n) aún se mantiene. Además, las consultas se pueden agrupar en forma de duplicación de prefijos (es decir, 1, 2, 4, 8 consultas) y ejecutarse simultáneamente en una ronda. El alcance general de este algoritmo es log₂ n consultas de accesibilidad, que es probablemente el paralelismo óptimo que se puede lograr utilizando el enfoque basado en la accesibilidad.

Generar gráficos aleatorios fuertemente conectados

Peter M. Maurer describe un algoritmo para generar gráficos aleatorios fuertemente conectados, basado en una modificación de un algoritmo para un fuerte aumento de conectividad, el problema de agregar la menor cantidad de aristas posible para hacer un gráfico 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 gráfico fuertemente conectado en n nodos, sin restricciones en los tipos de estructuras que se pueden generar.

Aplicaciones

Se pueden utilizar algoritmos para encontrar componentes fuertemente conectados para resolver problemas de 2-satisfacibilidad (sistemas de variables booleanas con restricciones en los valores de pares de variables): como Aspvall, Plass & Tarjan (1979) demostró que una instancia de 2-satisfacibilidad es insatisfacible si y sólo si hay una variable v tal que v y su complemento estén ambos contenidos en la misma variable fuertemente conectada. componente del gráfico de implicaciones de la instancia.

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 si pueden o no ser parte de una coincidencia perfecta en el gráfico.

Resultados relacionados

Un grafo dirigido está fuertemente conectado si y sólo si tiene una descomposición de oreja, una partición de los bordes en una secuencia de caminos y ciclos dirigidos de modo que el primer subgrafo de la secuencia sea un ciclo, y cada subgrafo subsiguiente sea un ciclo que comparte un vértice con subgrafos anteriores, o un camino que comparte sus dos puntos finales con subgrafos anteriores.

Según Robbins' teorema, un gráfico no dirigido puede orientarse de tal manera que se vuelva fuertemente conexo, si y solo si es conexo por 2 aristas. Una forma de probar este resultado es encontrar una descomposición en oído del gráfico no dirigido subyacente y luego orientar cada oído de manera consistente.