Tema
Componentes fuertemente conexas
- Algoritmos
- Nivel avanzado
En un grafo dirigido, una componente fuertemente conexa es un conjunto máximo de vértices en el que cada uno alcanza a todos los demás.
Nombre en inglés
Strongly connected components
Intuición
Al contraer cada componente en un solo nodo, el grafo resultante nunca tiene ciclos, y ese metagrafo se puede ordenar topológicamente. El algoritmo de Kosaraju usa esa idea dos veces: Un primer recorrido en profundidad ordena los vértices por tiempo de salida y un segundo recorrido sobre el grafo con las aristas invertidas descubre las componentes en ese orden.
Fórmula
coste O(V + E) ; primer recorrido sobre G ordenando por tiempo de salida decreciente ; segundo recorrido sobre G invertido siguiendo ese orden
Ejemplo resuelto
Un grafo con aristas de A a B, de B a C, de C a A y de C a D tiene dos componentes: El triángulo formado por A, B y C, donde cada vértice alcanza a los otros dos, y el vértice D por sí solo, ya que desde D no se vuelve. El metagrafo tiene una sola arista, que va de la componente del triángulo a la de D.
Errores frecuentes
- Aplicar la idea a grafos no dirigidos: Allí la noción que corresponde es la de componente conexa y basta un recorrido.
- Olvidar invertir las aristas en la segunda pasada: Sin esa inversión se obtienen los vértices alcanzables, que no es lo mismo que la componente.
- Equivocar el sentido del orden topológico del metagrafo: El vértice con mayor tiempo de salida pertenece a la primera componente de ese orden, y confundirlo invalida el algoritmo.
Ejercicio
¿Cuántas componentes fuertemente conexas tiene un ciclo dirigido de 5 vértices?
Ver la solución
En un ciclo dirigido todo vértice alcanza a todos los demás dando la vuelta, de manera que el grafo entero forma una sola componente.
Respuesta: 1