Haben die minimalen Spannbäume eines gewichteten Graphen die gleiche Anzahl von Kanten bei einer bestimmten Gewichtung?

21

Wenn ein gewichteter Graph zwei verschiedene minimale Spannbäume und , dann ist es wahr, dass für jede Kante in die Anzahl der Kanten in mit dem gleichen Gewicht wie (einschließlich selbst) entspricht der Anzahl der Kanten in mit demselben Gewicht wie ? Wenn die Aussage wahr ist, wie können wir sie dann beweisen?T 1 = ( V 1 , E 1 ) T 2 = ( V 2 , E 2 ) e E 1 E 1 e e E 2 eGT1=(V1,E1)T2=(V2,E2)eE1E1eeE2e

Aden Dong
quelle
Ein kniffliger, aber praktikabler Ansatz besteht darin, zu zeigen, dass 1) der Kruskal-Algorithmus jeden minimalen Spannbaum erzeugen kann und 2) alle minimalen Spannbäume, die von Kruskal gefunden werden, dasselbe Kantengewicht-Multiset aufweisen.
Raphael

Antworten:

16

Behauptung: Ja, diese Aussage ist wahr.

Beweisskizze: Sei T1,T2 zwei minimale Spannbäume mit kantengewichteten Multisätzen W1,W2 . Nehmen Sie W1W2 und bezeichnen Sie ihre symmetrische Differenz mit W=W1ΔW2 .

Wählen Sie die Kante eT1ΔT2 mit w(e)=minW , d. H. e ist eine Kante, die nur in einem der Bäume auftritt und ein minimales nicht übereinstimmendes Gewicht hat. Eine solche Kante, die insbesondere eT1ΔT2 , existiert immer: klar, dass nicht alle Kanten des Gewichts minW in beiden Bäume sein kann, sonst minWW . Wlog lasse eT1 und nehme T1hat mehr Gewichtskanten minW als T2 .

Betrachten Sie nun alle Kanten in T2 , die sich auch im Schnitt CT1(e) , der durch e in T1 induziert wird . Wenn es eine Kante e dort die das gleiche Gewicht wie besitzt e , update T1 unter Verwendung von e anstelle von e ; Es ist zu beachten, dass der neue Baum immer noch ein minimaler Spannbaum mit demselben Kantengewicht-Multiset wie T1 . Wir wiederholen dieses Argument, indem wir W um zwei Elemente verkleinern und dadurch eine Kante aus der Menge der Kandidaten für e entfernenein jedem Schritt. Daher kommen wir nach endlich vielen Schritten zu einer Einstellung, bei der alle Kanten in T2CT1(e) (wobei T1 die aktualisierte Version ist) andere Gewichte als w(e) .

Jetzt können wir immer eCT1(e)T2 so wählen , dass wir e und e ¹ tauschen können, dh wir können einen neuen Spannbaum erzeugen

T3={(T1{e}){e},w(e)<w(e)(T2{e}){e},w(e)>w(e)

die ein geringeres Gewicht als T1 und T2 ; dies widerspricht der Wahl von T1,T2 als minimale Spannbäume. Daher ist W1=W2 .


  1. Die von e einfallenden Knoten sind in T2 durch einen Pfad P ; e ist die eindeutige Kante in PCT1(e) .
Raphael
quelle
3
In Bezug auf Daves Kommentar kam ich zu diesem Beweis, nachdem ich 0) geglaubt hatte, ich hätte ein Gegenbeispiel, das ich als falsch angesehen habe, 1) versucht habe, die Aussage zu beweisen, aber gescheitert ist, 2) versucht habe, ein Gegenbeispiel zu konstruieren basierend darauf, wo der Beweis fehlgeschlagen ist und wo er erneut fehlgeschlagen ist, und schließlich 3) auf die Art und Weise, wie diese neuen Beispiele nicht funktioniert haben, um den Beweis zu erstellen. Das ist wahrscheinlich auch der Grund, warum es nicht so raffiniert ist, wie es sein könnte.
Raphael
Yeas genau, ich verstehe nicht , was durch cyt durch induzierte gemeint ist in T 1 I nur Schnitt gesehen hatte , wie ( S , V - S ) SchnitteT1(S,VS)
dragoboy
@ Dragoboy Entfernen von trennt T 1 ; eine Komponente bildet S , die andere das Komplement. eT1S
Raphael
5

Hier ist ein etwas einfacheres Argument, das auch für andere Matroiden gilt. (Ich habe diese Frage von einer anderen gesehen .)

Angenommen, hat m Kanten. Nehmen wir ohne Einschränkung der Allgemeinheit an, dass die Gewichtsfunktion w Werte in [ m ] annimmt , so dass wir eine Aufteilung von E in Mengen E i : = w - 1 ( i ) für i [ m ] haben . Wir können die Anzahl j von nicht leeren E i und die Anzahl der Eckpunkte n in G induzieren ; für j = 1 und jedes nGmw[m]EEi:=w1(i)i[m]jEinGj=1nist die Aussage offensichtlich.

Eine Standardtatsache über Matroiden ist, dass es für jedes MST eine lineare Erweiterung der durch w induzierten Ordnung gibt, so dass der Greedy-Algorithmus T erzeugt .TwT

Um die Induktion zu schließen, nimm als die größte Zahl, damit E t nicht leer ist. Setze E ' = E 1E t - 1 . Man beachte, dass jede lineare Ausdehnung von w jede Kante in E ' vor jede Kante in E t setzt . Demnach besteht jede MST aus einem durch E ' induzierten Spannwald F des Teilgraphen und einigen Kanten von E t . Nach der induktiven Hypothese ist jede zusammenhängende Komponente von FtEtE=E1Et1wEEtFEEtF has the same number of edges from each Ei for i<t. Since all the choices of F have the same size, the number of edges from Et required to complete F to a spanning tree is independent of the choice of F and we are done.

Louis
quelle
Can you give the matroid for the MST problem? I seem to remember that it is a tough thing to come up with, and I have yet to see it done (rigorously). Yes, we use greedy algorithms, but not the (canonical) greedy from matroid theory.
Raphael
That said, I think your core argument works (and does not need matroids at all): by correctness of Kruskal's algorithm and the fact that every MST can be obtained from a run of Kruskal with a specific (sorted) permutation of the weight multiset (rigorous proof pending), the claim follows. I write "proof pending" because it's neither trivial nor immediate: without using the claim itself it is not at all clear why Kruskal should find all MSTs. Clearly, if one had a different weight multiset, Kruskal would never find it!
Raphael
1. The matroid is the graphic matroid. Done!
Louis
2. You're confused. Abstractly, we are doing linear optimization over the basis polytope. One of the standard characterizations of matroids is that the greedy algorithm works for any choice of weights. All the w-minimal spanning trees are vertices of a face of this polytope. Now standard ideas from LP lead to the standard fact I mentioned.
Louis
1. Can you give a reference? I don't know the graphic matroid. 2. Now you drag LP into it, too! All I'm saying is that your answer lacks the matroid, and that without the matroid the line of reasoning seems to rely on the claim itself. If you have a way around that, please edit/clarify the answer.
Raphael