G = (V, E) es un gráfico simple no dirigido en el que cada borde tiene un peso distinto, y e es un borde particular de G. ¿Cuál de las siguientes afirmaciones sobre los árboles de expansión mínimos (MST) de G es VERDADERA?
I. If e is the lightest edge of some cycle in G,
then every MST of G includes e
II. If e is the heaviest edge of some cycle in G,
then every MST of G excludes e
(A) solo I
(B) solo II
(C) tanto I como II
(D) ni I ni II
Respuesta: (B)
Explicación:
I NO es cierto.
Sea G=(V, E) una gráfica rectangular donde V = {a, b, c, d} y E = {ab, bc, cd, da, ac}.
Dejemos que las aristas tengan pesos: ab = 1, bc = 2, cd = 4, da = 5, ac = 3. Entonces, claramente, ac es la arista más liviana del ciclo cdac, sin embargo, el MST abcd con costo 7 (= ab + bc + cd) no lo incluye.
Deje que los bordes tengan pesos: ab = 6, bc – 7, cd = 4, da = 5, ac = 3. Entonces, nuevamente, ac es el borde más liviano del ciclo cdac, y el MST retrocedió con un costo de 13 (= ba + ac + cd) lo incluye.
Entonces, los MST de G pueden o no incluir el borde más claro.
II es cierto
Que el borde de los pesados sea e. Supongamos que el árbol de expansión mínimo que contiene e. Si agregamos un borde más al árbol de expansión, crearemos un ciclo. Supongamos que agregamos el borde e’ al árbol de expansión que generó el ciclo C. Podemos reducir el costo del árbol de expansión mínimo si elegimos un borde que no sea e de C para eliminarlo, lo que implica que e no debe estar en el árbol de expansión mínimo y obtener una contradicción.
Fuente: http://www.ece.northwestern.edu/~dda902/336/hw5-sol.pdf
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