PUERTA | PUERTA CS 2021 | Juego 2 | Pregunta 11

Sea G un grafo ponderado no dirigido conexo. Considere las siguientes dos afirmaciones.

• S1: existe un borde de peso mínimo en G que está presente en cada árbol de expansión mínimo de G.
• S2: si cada borde en G tiene un peso distinto, entonces G tiene un árbol de expansión mínimo único.

¿Cuál de las siguientes opciones es la correcta?
(A) Tanto S1 como S2 son verdaderas
(B) S1 es verdadera y S2 es falsa
(C) S1 es falsa y S2 es verdadera
(D) Tanto S1 como S2 son falsas

Respuesta: (C)
Explicación:

• S1: Falso porque cuando cambiamos el número de aristas en el árbol de expansión mínimo. Ese borde mínimo se cambiaría por algún otro borde. También puede haber un caso si todos los bordes tienen un peso similar que puede elegir cualquier borde.
• S2: Cierto porque si los pesos de borde son únicos, solo es posible un único MST.

Cuestionario de esta pregunta