Considere un gráfico G ponderado no dirigido simple, cuyos pesos de borde son distintos. ¿Cuál de las siguientes afirmaciones sobre los árboles de expansión mínimos de G es (son) VERDADERA?
(A)
La arista con el segundo peso más pequeño siempre forma parte de cualquier árbol generador mínimo de G .
(B)
Uno o ambos bordes con el tercer peso más pequeño y el cuarto más pequeño son parte de cualquier árbol de expansión mínimo de G .
(C)
Supongamos que S C V sea tal que S ≠∅ y S ≠ V . Considere la arista con el peso mínimo tal que uno de sus vértices está en S y el otro en V \ S . Tal arista siempre será parte de cualquier árbol de expansión mínimo de G
(D)
G puede tener múltiples árboles de expansión mínimos
Respuesta: (A) (B) (C)
Explicación:
El borde más pequeño siempre forma parte del árbol de expansión mínimo.
El gráfico no tiene árboles de expansión múltiples, ya que todos los pesos de borde son únicos.
El segundo y tercer borde más pequeño formarán parte del árbol de expansión mínimo si el número de vértices es mayor que n>3 y 4 respectivamente
Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior
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