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

Considere un gráfico completo ponderado G en el conjunto de vértices {v1,v2,v} tal que el peso de la arista (v,,v) es 2|ij|. El peso de un árbol de expansión mínimo de G es: (GATE CS 2006)

(A) n — 1
(B) 2n — 2
(C) nC2
(D) 2

Respuesta: (B)
Explicación: el árbol de expansión mínimo de tal gráfico es

v1
  \
    v2
      \
       v3
         \
          v4
            .
              .
                .
                 vn
 

Peso del árbol de expansión mínimo
= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |
= 2n – 2

Cuestionario de esta pregunta