Sea G un grafo no dirigido simple. Sea T D un árbol de búsqueda en profundidad de G. Sea T B un árbol de búsqueda en anchura de G. Considere las siguientes afirmaciones.
(I) Ningún borde de G es un borde transversal con respecto a T D . (Un borde cruzado en G está entre dos Nodes, ninguno de los cuales es un antepasado del otro en T D ).
(II) Para cada arista (u, v) de G, si u está en la profundidad i y v está en la profundidad j en T B , entonces ∣i − j∣ = 1.
¿Cuál de las afirmaciones anteriores debe ser necesariamente cierta?
(A) Solo I
(B) Solo II
(C) Tanto I como II
(D) Ni I ni II
Respuesta: (A)
Explicación: Hay cuatro tipos de bordes que pueden producir en DFS. Estos son los bordes de árbol, delantero, trasero y transversal. En un gráfico conectado no dirigido, los bordes delantero y trasero son lo mismo. Una arista cruzada en un grafo es una arista que va de un vértice v a otro vértice u tal que u no es ni un ancestro ni un descendiente de v. Por lo tanto, la arista cruzada no es posible en un grafo no dirigido.
Entonces, la afirmación (I) es correcta.
Para el enunciado (II) tome el contraejemplo del gráfico completo de tres vértices, es decir, K3 con XYZ, donde X es la fuente e Y y Z están en el mismo nivel. Además, hay una arista entre los vértices Y y Z, es decir, |ij| = 0 ≠ 1 en BFS. Entonces, la declaración se volvió falsa.
La opción (A) es correcta.
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