PUERTA | PUERTA CS Simulacro 2018 | Pregunta 37

Sea G = (V, E) cualquier gráfico ponderado de borde no dirigido conectado. Los pesos de las aristas en E son positivos. Considere las siguientes declaraciones:

1. El camino entre un par de vértices en un árbol de expansión mínimo de un gráfico no dirigido es necesariamente el camino más corto (peso mínimo).
2. El árbol de expansión mínimo de G siempre es único y el camino más corto entre un par de vértices puede no ser único.

¿Cuál de las afirmaciones anteriores es/son necesariamente verdaderas?
(A) (1) solo
(B) (2) solo
(C) tanto (1) como (2)
(D) ni (1) ni (2)

Respuesta: (D)
Explicación: Dado que los pesos de los bordes no están definidos . Si los pesos de los bordes son distintos, MST siempre es único, pero es posible que no sean las rutas más cortas.

(A)---1----(B)----2---(C)
 \                    /
  ---------3----------

Y, si los pesos de los bordes no son distintos, tanto el MST como los caminos cortos no son únicos.

(A)---2----(B)----2---(C)
 \                    /
  ---------2----------

Entonces, ambas afirmaciones son falsas.
La opción (D) es correcta.
Cuestionario de esta pregunta