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

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 " $\Rightarrow$ "dirección y el siguiente gráfico $G$ .

mst

$G$ tiene 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?

graph-theory spanning-trees hengxina
fuente

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

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, tome

G

$G$ ser cualquier árbol donde todos los pesos de borde sean

1

$1$ , entonces

G

$G$ tiene 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

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

JeffE

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

Respuestas: