Algoritmos | Gráficos transversales | Pregunta 12 – Part 3

Sea G un grafo no dirigido. Considere un recorrido de G primero en profundidad, y sea T el árbol de búsqueda primero en profundidad resultante. Sea u un vértice en G y sea v el primer vértice nuevo (no visitado) visitado después de visitar u en el recorrido. ¿Cuál de las siguientes afirmaciones es siempre cierta? (GATE CS 2000)
(A) {u,v} debe ser una arista en G, y u es un descendiente de v en T
(B) {u,v} debe ser una arista en G, y v es un descendiente de u en T
(C) Si {u,v} no es una arista en G entonces u es una hoja en T
(D) Si {u,v} no es una arista en G entonces u y v deben tener el mismo padre en T

Respuesta: (C)
Explicación:

In DFS, if 'v' is visited
after 'u', then one of the following is true.
1) (u, v) is an edge.
     u
   /   \
  v     w
 /     / \
x     y   z

2) 'u' is a leaf node.
     w
   /   \
  x     v
 /     / \
u     y   z 

En DFS , después de visitar un Node, primero recurrimos para todos los niños no visitados. Si no hay hijos no visitados (u es una hoja), entonces el control vuelve al padre y luego el padre visita a los siguientes hijos no visitados.
Cuestionario de esta pregunta