Condición necesaria y suficiente para un árbol de expansión mínimo único

8

Este es un problema de ejercicio (Ej. 3) de la excelente nota de lectura de Jeff Erickson Lectura 20: Árboles de expansión mínima [Fa'13] .

Probar que un gráfico ponderado por el borde G tiene un árbol de expansión mínimo único si y solo si se cumplen las siguientes condiciones

  • Para cualquier partición de los vértices de G en dos subconjuntos, el borde de peso mínimo con un punto final en cada subconjunto es único.

  • La ventaja de peso máximo en cualquier ciclo de G es único.

Considera el ""dirección y el siguiente gráfico G.

mst

Gtiene un MST único. Sin embargo, para la partición{A} y {B,C}, el borde de cruce de peso mínimo no es único.

¿Entendí mal algunos puntos? O si hay fallas en el teorema, ¿cómo podemos solucionarlo?

hengxina
fuente
3
Sí, esto parece ser un error. Intenta averiguar qué versión del ejercicio es correcta. Por ejemplo, parece que la segunda condición es realmente necesaria.
Yuval Filmus
2
A menos que no lo entienda bien, la segunda condición tampoco es necesaria. Considere la gráfica {(A, B, 1), (A, C, 1), (A, D, 1), (B, D, 10), (D, C, 10)}. También tiene un árbol de expansión mínimo compuesto por bordes conectados a A. Pero hay un ciclo con 2 bordes de peso máximo (y la primera condición tampoco se cumple). CC @YuvalFilmus
babou
@jeffe, ¿qué te parece? ;)
Luke Mathieson
Creo que el segundo debería estar en "en cualquier ciclo sin acordes " (por lo tanto, un ciclo mínimo en el sentido de que no incluye los más pequeños como subgrafías inducidas). La primera condición parece significativamente incorrecta. Por ejemplo, tomeG ser cualquier árbol donde todos los pesos de borde sean 1, entonces Gtiene un MST único (sí mismo), pero cualquier partición con más de un borde que lo cruce tiene varios bordes de peso mínimo.
Luke Mathieson
1
¡Uy! Sí, esto es un error. (Nota personal: cambie cada instancia de "Probar" a "Probar o refutar".)
JeffE

Respuestas:

0

Responda mi propia pregunta simplemente copiando el comentario hecho por @JeffE, el autor de la nota de conferencia:

¡Uy! Sí, esto es un error. (Nota para uno mismo: cambie cada instancia de "Probar" a "Probar o refutar"). - JeffE

hengxina
fuente