← Volver a los ejercicios

Los tipos de arista de la profundidad

Cada vez que el recorrido en profundidad mira una arista (u, v), el color de v decide el tipo. Si v está blanco, la arista lo descubre y es de árbol; si está gris, v sigue en la pila de llamadas, es ancestro de u y la arista es de retroceso; si está negro, la arista es de avance cuando d[u] < d[v] y cruzada en el otro caso. En un grafo no dirigido cada arista aparece en las dos listas, y la segunda vez hay que reconocerla. El reloj suma uno al descubrir un vértice y uno al terminarlo, y arranca en 1.

1. El recorrido, arista por arista

━━ árbol ┅┅ retroceso (R) ━ avance (A) ━ cruzada (C) ━ la que se mira ahora vértices: blanco, gris, negro, con d/f encima

Pila de llamadas: vacía
Paso 0 de 0
VérticeEstadodf
Aristas en el orden en que se miran:

2. Al terminar el recorrido

La pregunta se abre cuando el recorrido del grafo termina.

¿Cuántas aristas de retroceso dejó el recorrido? ¿Hay ciclo?

3. Para llevarse

En un grafo no dirigido el recorrido nunca deja una arista cruzada ni una de avance. Demuéstrelo: suponga que al mirar u–v el vértice v ya está negro y explique por qué esa arista ya se había mirado desde v, con u gris. Después tome el grafo dirigido de ocho vértices, cambie la lista del 0 por [4, 2, 1] y prediga, antes de trazarlo, qué aristas cambian de tipo y cuántas de retroceso quedan.