Algoritmos | Árbol de expansión mínimo del gráfico | Pregunta 3

Considere un gráfico no dirigido completo con el conjunto de vértices {0, 1, 2, 3, 4}. La entrada Wij en la array W a continuación es el peso de la arista {i, j}. ¿Cuál es el peso mínimo posible de un árbol de expansión T en este gráfico tal que el vértice 0 sea un Node hoja en el árbol T? (PUERTA CS 2010)

(A) 7
(B) 8
(C) 9
(D) 10

Respuesta: (D)
Explicación: para obtener el árbol de expansión mínimo con el vértice 0 como hoja, primero elimine la fila 0 y la columna 0 y luego obtenga el árbol de expansión mínimo ( MST) del gráfico restante. Una vez que tengamos el MST del gráfico restante, conecte el MST al vértice 0 con el borde con peso mínimo (tenemos dos opciones ya que hay dos 1 en la fila 0).
Cuestionario de esta pregunta