Un componente fuertemente conexo pide dos caminos entre cada par de vértices, uno de ida y otro de vuelta. Invertir todas las flechas intercambia esos dos caminos y deja la exigencia igual, así que los grupos no se mueven. Contraer cada grupo a un solo nodo deja un grafo sin ciclos, y esa es la pieza sobre la que se apoya Kosaraju.
Nueve vértices y trece flechas: 0 → 1, 1 → 2, 2 → 0, 1 → 3, 3 → 4, 4 → 3, 2 → 5, 5 → 6, 6 → 7, 7 → 5, 4 → 6, 6 → 8, 3 → 8.
¿Cuántos componentes fuertemente conexos tiene?
Corra el algoritmo sobre G y sobre Gᵀ y compare los grupos que devuelve cada uno.
Escoja dos vértices. Si hay camino del primero al segundo en G, la misma secuencia leída al revés es un camino del segundo al primero en Gᵀ, arista por arista. El camino queda resaltado en el dibujo de arriba.
¿Cuántas aristas tiene este grafo de componentes?
Sin solución aquí. Agregue al grafo la flecha 8 → 1 y diga, antes de comprobarlo, cuáles componentes se funden y cuántos quedan. Después dibuje el grafo de componentes que resulta y verifique que sigue sin ciclos.