Considere la búsqueda en profundidad de un grafo no dirigido con 3 vértices P, Q y R. Deje que el tiempo de descubrimiento d(u) represente el instante de tiempo cuando se visita el vértice u por primera vez, y que el tiempo de finalización f(u) represente el tiempo instante en que se visitó por última vez el vértice u. Dado que
d(P) = 5 unidades f(P) = 12 unidades
d(Q) = 6 unidades f(Q) = 10 unidades
d(R) = 14 unidades f(R) = 18 unidades ¿
cuál de los siguientes enunciados es VERDADERO sobre la gráfica
(A) Solo hay un componente conectado
(B) Hay dos componentes conectados, y P y R están conectados
(C) Hay dos componentes conectados, y Q y R están conectados
(D) Hay dos componentes conectados, y P y Q están conectados
Respuesta: (D)
Explicación: dado que d(q)=d(p)+1 y f(q)< f(p), lo que significa que p y q están conectados y r está separado, entonces d es la respuesta al
cuestionario de esta pregunta
. algo mal en el post anterior
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA