PUERTA | PUERTA-CS-2003 | Pregunta 90 – Part 6

¿Cuál es el peso de un árbol de expansión mínimo del siguiente gráfico?

(A) 29
(B) 31
(C) 38
(D) 41

Respuesta: (B)
Explicación: (a,c), (a,d), (d,b), (b,g), (g, h), (h,f), (h,i), (i,j), (i,e) = 31
 

Antecedentes requeridos: árbol de expansión mínimo ( Prims / Kruskal )

En este tipo de preguntas, siempre utilice el algoritmo de Kruskal para encontrar el árbol de expansión mínimo, ya que es fácil y hay menos posibilidades de cometer errores tontos.

Algoritmo:

Elija siempre el peso de borde mínimo e intente agregarlo al bosque actual (Colección de árboles) si no se forma un ciclo; de lo contrario, deséchelo.
Tan pronto como haya agregado n-1 bordes al bosque, deténgase y tendrá su árbol de expansión mínimo.

Vea la imagen a continuación para la construcción de MST de esta pregunta.

Peso del árbol de expansión mínimo = Suma de todos los bordes en el árbol de expansión mínimo
= 31

Esta explicación ha sido proporcionada por Pranjul Ahuja.

Visite los siguientes enlaces para obtener más información:
http://www.ics.uci.edu/~eppstein/161/960206.html
https://en.wikipedia.org/wiki/Minimum_spanning_tree

Cuestionario de esta pregunta