¿El árbol mínimo de abarcantes no tendrá solo los bordes especificados por la propiedad del ciclo?[duplicar]

Question

Esta pregunta ya tiene una respuesta aquí :

¿Qué bordes no están en ningún MST? (1 respuesta)

Cerrado hace 4 meses .

Acabo de empezar a entender los "árboles mínimos" (MSTS), y se había encontrado con la propiedad del ciclo. Me refiero al libro - Diseño del algoritmo de Jon Kleinberg y Eva Tardos. La declaración de la propiedad según la escritura en el libro es:

Supongamos que todos los costos del borde son distintos. Sea C cualquier ciclo en G, y deje que el borde E= (V, W) sea el borde más caro que pertenece a C., entonces e no pertenece a ningún árbol de expansión mínimo.

Ahora, mi duda es: son los bordes de un gráfico (gráfico no dirigido con bordes que tienen pesos positivos distintos) que no satisfacen la propiedad del ciclo, los únicos que no están presentes en el MST o habrán otros bordes que ¿No pertenezcan al MST y no está cubierto por esta propiedad?

No puedo encontrar una prueba para discutir si estos bordes existen o no. ¿Puede algunos por favor dar una prueba para esto?

Answer 1

Digamos que un borde $ e $ en $ g $ es mal < / Strong> Si existe un ciclo en $ g $ en el que $ e $ tiene un peso máximo.

Define $ {\ cal b}={e ~ | \ \ {span> es mal en $ g \ \ \} $ Para ser la colección de todos los bordes malos.

Su pregunta es si el gráfico $ (g - {\ cal b}) $ el MST de $ g $ (asumiendo que todos los pesos de bordes son distintos). La respuesta es sí!

Para demostrar esto, se basa en mostrar que $ (g - {\ cal b}) $ es acíclico.

Asumir en contra de que $ (g - {\ cal b}) $ contiene un ciclo, digamos $ c $ . Observe que $ C $ es un ciclo en $ g $ también. Deje que $ e ^ * $ sea el borde del peso máximo en el ciclo $ C $ . Ahora $ e ^ * $ es un borde mal , por lo que no debería haber sido el gráfico $ (G - {\ cal b}) $ en primer lugar. Esto demuestra que $ (g - {\ cal b}) $ es acíclico.

Answer 2

Perdón Si no entendía su pregunta, pero lo que creo que quisiste preguntar es, ya sea posible para que un borde no esté en un MST si este borde no está en un ciclo.

Aquí está mi respuesta.

Supongamos que tenemos un borde (u, v) en un gráfico G, que no es parte de un ciclo.Esto significaría que no hay camino de u a v que no es el borde (u, v). Si el borde (U, V) no estaba en el MST, esto significaría que no hay ruta de U a v en este MST, lo que significa que el MST se desconectaría y, por lo tanto, no es un MST en absoluto. Por lo tanto, si un borde no es parte de un ciclo, debe estar en el MST de la gráfica.