← Volver a los ejercicios

El grafo al revés y el grafo de componentes

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.

1. El grafo y la predicción

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?

2. Los mismos grupos en los dos grafos

Corra el algoritmo sobre G y sobre Gᵀ y compare los grupos que devuelve cada uno.

3. Un camino y el mismo camino al revés

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.

De a

4. El grafo de componentes

¿Cuántas aristas tiene este grafo de componentes?

5. Por qué no puede tener ciclos

¿Qué impide que el grafo de componentes tenga un ciclo?

6. Para llevarse

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.