Notwendige und ausreichende Bedingung für einen einzigartigen minimalen Spannbaum

8

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 geltenG

  • 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 „ “ 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?

Hengxin
quelle
3
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
2
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. 1 G.G1G
Luke Mathieson
1
Hoppla! Ja, das ist ein Fehler. (Hinweis für sich selbst: Ändern Sie jede Instanz von "Prove" in "Prove or
Disprove

Antworten:

0

Beantworten Sie meine eigene Frage, indem Sie einfach den Kommentar von @JeffE, dem Autor der Vorlesungsnotiz, kopieren:

Hoppla! Ja, das ist ein Fehler. (Hinweis für sich selbst: Ändern Sie jede Instanz von "Beweisen" in "Beweisen oder widerlegen".) - JeffE

Hengxin
quelle