Considere las siguientes declaraciones:
S1: DFS de un gráfico dirigido siempre produce el mismo número de aristas en el recorrido, independientemente del vértice inicial.
S2: si se eliminan todos los bordes posteriores que se encuentran durante el recorrido DFS en el gráfico dirigido, el gráfico resultante es acíclico.
¿Cuáles de las siguientes afirmaciones anteriores son válidas?
(A) Tanto S1 como S2 son válidos
(B) Solo S1 es válido
(C) Solo S2 es válido
(D) Ni s1 ni S2 son válidos
Respuesta: (C)
Explicación: Declaración S1: considere el gráfico
Comenzando con A (vértice de origen) obtendremos 2 aristas
Comenzando con B obtendrá solo 1 arista
Comenzando con C no obtendremos ninguna arista
Por lo tanto, DFS en el gráfico dirigido puede no dar el mismo número de aristas.
Declaración S2: Los bordes posteriores son aquellos bordes (u, v) que conectan un vértice u con un ancestro u en un
árbol de profundidad. Los bucles automáticos se consideran bordes posteriores. Los bordes posteriores describen las relaciones de descendiente a antepasado, ya que conducen de los Nodes «altos» a los «bajos».
Supongamos que hay un borde posterior (u, v). Entonces el vértice v es un ancestro del vértice u en el bosque de profundidad primero. Por lo tanto, hay un camino de v a u en G, y el borde posterior (u, v) completa un ciclo. Quitar el borde trasero romperá el ciclo.
Por lo tanto, eliminar todos los bordes posteriores hará que el gráfico sea acíclico. Entonces la afirmación es verdadera.
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