En un recorrido primero en profundidad de un gráfico G con n vértices, los bordes k se marcan como bordes de árbol. El número de componentes conectados en G es
(A) k
(B) k + 1
(C) n – k – 1
(D) n – k
Respuesta: (D)
Explicación: Los bordes del árbol son los bordes que forman parte del árbol DFS . Si hay x aristas de árbol en un árbol, entonces x+1 vértices en el árbol.
La salida de DFS es un bosque si el gráfico está desconectado. Veamos a continuación un ejemplo simple donde el gráfico está desconectado.
El ejemplo anterior coincide con la opción D
Más ejemplos:
1) Todos los vértices de Graph están conectados. k debe ser n-1. Obtenemos número de componentes conectados = n- k = n – (n-1) = 1
2) Ningún vértice está conectado. k debe ser 0. Obtenemos el número de componentes conectados = n- k = n – 0 = n
Cuestionario de esta pregunta
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