CGU-NET | UGC-NET CS 2017 2 de diciembre | Pregunta 5

Considere el gráfico que se presenta a continuación:

Use el algoritmo de Kruskal para encontrar un árbol de expansión mínimo para el gráfico. La Lista de las aristas del árbol en el orden en que se eligen es?
(1) AD, AE, AG, GC, GB, BF
(2) GC, GB, BF, GA, AD, AE
(3) GC, AD, GB, GA, BF, AE
(4) AD, AG, GC , AE, GB, BF
(A) (1)
(B) (1), (2)
(C) (1), (2), (3)
(D) (1), (2), (3) ,(4)

Respuesta: (D)
Explicación: Usando el algoritmo de Kruskal para el árbol de expansión mínimo:
Primero seleccione el borde de peso mínimo, es decir, 2 tenemos dos opciones GC y AD
Ahora seleccione Siguiente borde de peso mínimo: para GC tenemos que seleccionar GB o AD, etc. Seleccione el peso mínimo. Tenga en cuenta que no queda ningún vértice para visitar.
Aquí todas las opciones coinciden con el árbol de expansión mínimo.
Entonces, la opción (D) es correcta.

Cuestionario de esta pregunta