Notwendige und ausreichende Bedingung für einen einzigartigen minimalen Spannbaum

Dies ist ein Übungsproblem (Bsp. 3) aus der ausgezeichneten Vorlesungsnotiz von Jeff Erickson, Vorlesung 20: Minimum Spanning Trees [Fa'13] .

Beweisen Sie, dass ein kantengewichteter Graph genau dann einen eindeutigen minimalen Spannbaum hat, wenn die folgenden Bedingungen gelten $G$

Für jede Aufteilung der Eckpunkte von in zwei Teilmengen ist die Kante mit minimaler Gewichtung mit einem Endpunkt in jeder Teilmenge eindeutig. $G$

Die Kante mit maximalem Gewicht in jedem Zyklus von $G$ ist einzigartig.

Betrachten Sie die „ $\Rightarrow$ “ Richtung und die folgende Grafik $G$ .

mst

$G$ hat eine einzigartige MST. Für die Partition $\{A\}$ und $\{B,C\}$ ist die Kreuzungskante mit minimalem Gewicht jedoch nicht eindeutig.

Habe ich einige Punkte falsch verstanden? Oder wie können wir Fehler beheben, wenn der Satz Fehler enthält?

graph-theory spanning-trees Hengxin
quelle

Ja, das scheint ein Fehler zu sein. Versuchen Sie herauszufinden, welche Version der Übung korrekt ist. Zum Beispiel scheint die zweite Bedingung tatsächlich notwendig zu sein.

Yuval Filmus

Sofern ich nicht falsch verstehe, ist auch die zweite Bedingung nicht erforderlich. Betrachten Sie den Graphen {(A, B, 1), (A, C, 1), (A, D, 1), (B, D, 10), (D, C, 10)}. Es hat auch einen minimalen Spannbaum, der aus mit A verbundenen Kanten besteht. Es gibt jedoch einen Zyklus mit 2 Kanten mit maximalem Gewicht (und die erste Bedingung ist auch nicht erfüllt). CC @YuvalFilmus

Babou

@ Jeffe, was denkst du? ;)

Luke Mathieson

Ich denke, der zweite sollte in "in jedem akkordlosen Zyklus" sein (also ein minimaler Zyklus in dem Sinne, dass er keine kleineren als induzierte Untergraphen enthält). Die erste Bedingung scheint erheblich falsch zu sein. Nehmen wir zum Beispiel als einen Baum, in dem alle Kantengewichte , dann hat eine eindeutige MST (selbst), aber jede Partition mit mehr als einer sich kreuzenden Kante hat mehrere Kanten mit minimalem Gewicht.

G

$G$

1

$1$

G

$G$

Luke Mathieson

Hoppla! Ja, das ist ein Fehler. (Hinweis für sich selbst: Ändern Sie jede Instanz von "Prove" in "Prove or

Disprove

Notwendige und ausreichende Bedingung für einen einzigartigen minimalen Spannbaum

Antworten: