PUERTA | PUERTA CS 2020 | Pregunta 59

Considere un gráfico G=(V, E), donde V = { v ₁ ,v ₂ ,…,v ₁₀₀ }, E={ (v _i , v _j ) ∣ 1≤ii, v _j ) es ∣i–j∣. El peso del árbol de expansión mínimo de G es ________.

Nota: esta pregunta era de tipo numérico.
(A) 99
(B) 100
(C) 98
(D) 101

Respuesta: (A)
Explicación: Hay 100 vértices numerados del 1 al 100.
Las aristas están presentes en este gráfico E={ (v _i , v _j ) ∣ 1≤i1, v ₂ ), (v ₂ , v ₃ ), ….. (v ₉₉ , v ₁₀₀ ) tendrán un peso mínimo, es decir, 1 por cada arista.

Como sabemos, hay 99 aristas posibles en un árbol de expansión mínimo de un gráfico de 100 vértices.

Por lo tanto, estos bordes (v ₁ , v ₂ ), (v ₂ , v ₃ ), ….. (v ₉₉ , v ₁₀₀ ) serán el árbol de expansión para el gráfico dado. Estos son 99 bordes con 1 costo de cada uno.

El peso del árbol de expansión mínimo de G es 99*1 = 99.

La opción (A) es correcta.
Cuestionario de esta pregunta