El gráfico que se muestra debajo de 8 aristas con distintos pesos de aristas enteras. El árbol de expansión mínimo (MST) tiene un peso de 36 y contiene las aristas: {(A, C), (B, C), (B, E), (E, F), (D, F)}. Los pesos de borde de solo aquellos bordes que están en el MST se dan en la figura que se muestra a continuación. La suma mínima posible de los pesos de las 8 aristas de este gráfico es ______________.
(A) 66
(B) 69
(C) 68
(D) 70
Respuesta: (B)
Explicación: En cada ciclo, el peso de una arista que no forma parte de MST debe ser mayor o igual al peso de otras aristas que forman parte del MST.
Dado que todos los pesos de los bordes son distintos, el peso debe ser mayor.
Entonces, el peso mínimo posible de ED es 7, el peso mínimo posible de CD es 16 y el peso mínimo posible de AB es 10.
Por lo tanto, la suma mínima posible de pesos es 69.
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