Sea G un grafo no dirigido conexo de 100 vértices y 300 aristas. El peso de un árbol de expansión mínimo de G es 500. Cuando el peso de cada arista de G aumenta en cinco, el peso de un árbol de expansión mínimo se convierte en ________.
(A) 1000
(B) 995
(C) 2000
(D) 1995
Respuesta: (B)
Explicación: dado que hay 100 vértices, debe haber 99 aristas en el árbol de expansión mínima (MST).
Cuando el peso de cada borde aumenta en 5, el incremento en el peso de MST es = 99 * 5 = 495
Entonces, el nuevo peso de MST es 500 + 495, que es 995
Prueba 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