Sea G un grafo conexo no dirigido con distinto peso de arista. Sea emax la arista con peso máximo y emin la arista con peso mínimo. ¿Cuál de las siguientes afirmaciones es falsa? (GATE CS 2000)
(A) Cada árbol de expansión mínimo de G debe contener emin
(B) Si emax está en un árbol de expansión mínimo, entonces su eliminación debe desconectar G
(C) Ningún árbol de expansión mínimo contiene emax
(D) G tiene un árbol de expansión mínimo único
Respuesta: (C)
Explicación: (a) y (b) siempre son verdaderas.
(c) es falsa porque (b) es verdadera.
(d) es cierto porque todos los pesos de los bordes son distintos para G.
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