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 e
graph-theory
spanning-trees
weighted-graphs
Aden Dong
quelle
quelle
Antworten:
Behauptung: Ja, diese Aussage ist wahr.
Beweisskizze: SeiT1,T2 zwei minimale Spannbäume mit kantengewichteten Multisätzen W1,W2 . Nehmen Sie W1≠W2 und bezeichnen Sie ihre symmetrische Differenz mit W=W1ΔW2 .
Wählen Sie die Kantee∈T1Δ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 e∈T1ΔT2 , existiert immer: klar, dass nicht alle Kanten des Gewichts minW in beiden Bäume sein kann, sonst minW∉W . Wlog lasse e∈T1 und nehme T1 hat mehr Gewichtskanten minW als T2 .
Betrachten Sie nun alle Kanten inT2 , 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 entfernene in jedem Schritt. Daher kommen wir nach endlich vielen Schritten zu einer Einstellung, bei der alle Kanten in T2∩CT1(e) (wobei T1 die aktualisierte Version ist) andere Gewichte als w(e) .
Jetzt können wir immere′∈CT1(e)∩T2 so wählen , dass wir e und e′ ¹ tauschen können, dh wir können einen neuen Spannbaum erzeugen
die ein geringeres Gewicht alsT1 und T2 ; dies widerspricht der Wahl von T1,T2 als minimale Spannbäume. Daher ist W1=W2 .
quelle
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 nG m w [ m ] E Ei:=w−1(i) i∈[m] j Ei n G j=1 n ist 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 .T w T
Um die Induktion zu schließen, nimm als die größte Zahl, damit E t nicht leer ist. Setze E ' = E 1 ∪ ⋯ ∪ E 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 Ft Et E′=E1∪⋯∪Et−1 w E′ Et F E′ Et F 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.
quelle