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:
- 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).
- 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
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