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?
(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:
En el algoritmo de Kruskal, seleccionamos los bordes en orden ascendente y los agregamos al bosque si no se forma un ciclo. La opción A es verdadera porque el primer borde nunca podría crear un ciclo.
La única razón para que emax esté presente en el árbol de expansión mínimo podría ser que es el único borde posible para cubrir un vértice particular en un árbol, ya que todos los vértices deben estar presentes en un árbol de expansión por definición. Considere la imagen de abajo
Consulte la pregunta 2 de https://www.geeksforgeeks.org/data-structures-and-algorithms-set-8/
Esta solución es aportada por Pranjul Ahuja
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