Bei einem gewichteten, ungerichteten Graphen G: Welche Bedingungen müssen erfüllt sein, damit es für G mehrere minimale Spannbäume gibt?
Ich weiß, dass der MST eindeutig ist, wenn alle Gewichtungen unterschiedlich sind, aber Sie können diese Aussage nicht umkehren. Wenn das Diagramm mehrere Kanten mit derselben Gewichtung enthält, kann es mehrere MSTs geben , es kann jedoch auch nur eine geben:
In diesem Beispiel hat das Diagramm links eine eindeutige MST, das rechte jedoch nicht.
Das, was ich am ehesten erreichen konnte, um Bedingungen für die Nicht-Eindeutigkeit des MST zu finden, war Folgendes:
Berücksichtigen Sie alle akkordlosen Zyklen (Zyklen, die keine anderen Zyklen enthalten) im Diagramm G. Wenn in einem dieser Zyklen die maximal gewichtete Kante mehrmals vorhanden ist, hat das Diagramm keinen eindeutigen minimalen Spannbaum.
Meine Idee war das für einen Zyklus wie diesen
Mit n Scheitelpunkten können Sie genau eine der Kanten weglassen und trotzdem alle Scheitelpunkte verbinden. Daher haben Sie mehrere Möglichkeiten, die Kante mit dem höchsten Gewicht zu entfernen, um eine MST zu erhalten, sodass die MST nicht eindeutig ist.
Ich habe mir dann aber folgendes Beispiel ausgedacht:
Sie können sehen, dass dieses Diagramm einen Zyklus hat, der zu meiner Bedingung passt: (E, F, G, H), aber soweit ich sehen kann, ist der minimale Spannbaum eindeutig:
Es scheint also, als ob mein Zustand nicht korrekt ist (oder nur nicht vollständig korrekt ist). Ich würde mich sehr über jede Hilfe freuen, um die notwendigen und ausreichenden Bedingungen für die Nicht-Eindeutigkeit des minimalen Spannbaums zu finden.
Antworten:
im ersten Bild: Die rechte Grafik hat eine eindeutige MST, indem Kanten und ( F , G ) mit einem Gesamtgewicht von 2 genommen werden.(F,H) (F,G) Bei einem Graphen und lassen Sie M = ( V , F ) sein ein Minimum Spanning Tree (MST) in G .G=(V,E) M=(V,F) G
Wenn es eine Kante mit dem Gewicht w ( e ) = m gibt, so dass die Addition von e zu unserem MST einen Zyklus C ergibt , und m auch das niedrigste Kantengewicht von F ∩ C sein soll , dann können wir eine zweite MST erzeugen, indem wir eine Kante von F ∩ C mit Kantengewicht m mit e tauschen . Somit haben wir keine Einzigartigkeit.e={v,w}∈E∖F w(e)=m e C m F∩C F∩C m e
quelle
Eine vorherige Antwort gibt einen Algorithmus an, um zu bestimmen, ob es mehrere MSTs gibt, die für jede Kante nicht in G enthalten ist, den Zyklus finden, der durch Hinzufügen von e zu einer vorberechneten MST erstellt wurde, und prüfen, ob e nicht die eindeutig schwerste Kante in diesem Zyklus ist. Dieser Algorithmus wird wahrscheinlich in der Zeit O ( | E | | V | ) ausgeführt .e G e e O ( | E| | V| )
Ein einfacher Algorithmus , um zu bestimmen , ob es mehrere MSTs von G in zeit KomplexitätO ( | E| Log( | V| )) .
Ein gewöhnlicher Durchlauf des Kruskal-Algorithmus benötigt Zeit. Die zusätzliche Auswahl von Kanten, die nicht in m angegeben sind, kann in O ( | E | ) erfolgen . Der Algorithmus erreicht also O ( | E | log ( | V | ) ) Zeitkomplexität.O ( | E| Log( | V| )) m O ( | E| ) O ( | E| Log( | V| ))
Warum kann dieser Algorithmus feststellen, ob mehrere MSTs vorhanden sind?
Angenommen, wir haben ein MST , das nicht dasselbe wie m ist . Es genügt zu zeigen, dass der auf G ausgeführte Algorithmus Schritt 3 nicht erreichen wird, da die am Ende von Schritt 2 gefundene Kante, die nicht in m ist und zwei verschiedene Bäume verbindet, in der resultierenden MST enthalten gewesen wäre, wenn wir Kruskals ausgeführt hätten Algorithmus zur Vervollständigung. Lassen w das größte Gewicht so beschaffen sein , dass für jede Kante mit einem Gewicht von weniger als w , es ist m , wenn und nur wenn es in den m ' . Da m und m ' die gleiche Anzahl von Gewichtskanten w haben , existieren Gewichtskantenm′ m G m w w m m′ m m′ w , die in m ' aber nicht in m sind . Wenn der Algorithmus beendet wurde, bevor Kanten dieser Kanten verarbeitet wurden, sind wir fertig. Ansonsten wird angenommen, dass der Algorithmusjetztdie erste Kante e ' unter diesen Kanten verarbeitet. Sei S die Menge aller Kanten, die bisher erhalten geblieben sind, um in den resultierenden MST einbezogen zu werden. S ⊂ m . Da der Algorithmus die Verarbeitung der Gewichtskante w nicht in m beendet hat, wie z. B. e ' , darf er nicht mit der Verarbeitung der Gewichtskanten w in m begonnen haben . Also Kanten in Sw m′ m e′ S S⊂m w m e′ w m S wiegen weniger als . Das heißt S ⊂ m ' . Denken Sie daran, dass e ' in m ' ist . Da { e ' } ∪ S ⊂ m ' ist , wobei m ' ein Baum ist , muss e ' zwei verschiedene Bäume in S verbinden, und der Algorithmus wird an dieser Stelle beendet.w S⊂m′. e′ m′ {e′}∪S⊂m′ m′ e′ S
Hinweis zur weiteren Entwicklung
Schritt 1 und Schritt 2 können verschachtelt werden, damit wir den Algorithmus so schnell wie möglich beenden können, ohne Kanten größerer Gewichte zu verarbeiten.
Wenn Sie die Anzahl der MSTs berechnen möchten, können Sie eine Antwort darauf überprüfen , wie die Anzahl der MSTs berechnet werden soll .
quelle
Sei ein (einfacher endlicher) kantengewichteter ungerichteter zusammenhängender Graph mit mindestens zwei Eckpunkten. Es sei ST Mean Spanning Tree und MST Mean Minimum Spanning Tree. Lassen Sie mich zuerst einige weniger gebräuchliche Begriffe definieren.G
Wann gibt es mehr als einen minimalen Spannbaum?
Um die Frage von OP zu beantworten, sind hier fünf Charakterisierungen von mit mehr als einem MSTG .
Die Neuheit dieser Antwort sind meist die letzten beiden Charakterisierungen. Die vorletzte Charakterisierung kann als nächster Schritt des OP-Ansatzes betrachtet werden . Die ersten drei Charakterisierungen zusammen können als leicht verbesserte Version der Antwort von dtt betrachtet werden .
Wann ist das Minimum an Spannbäumen einzigartig?
Hier kommt mein Beweis.
"Eindeutigkeit von MST" => "Kein benachbartes MST": offensichtlich.
"Keine benachbarten MSTs" => "Eine isolierte MST": offensichtlich.
"One isolated MST" => "One local minimum ST": Eine isolierte MST ist leichter als alle benachbarten STs.
"Local minimum ST" => "Extreme Schnittkante": Der Nachweis bleibt als Übung erhalten.
"Extreme Schnittkante" => "Einzigartigkeit von MST": Der Beweis bleibt als Übung.
Die obigen Implikationsketten beweisen den Satz.
Die Neuheit dieser Antworten ist wiederum hauptsächlich die Eigenschaft "extreme Zykluskante" und die Eigenschaft "extreme Schnittkante", bei denen die Konzepte "nicht zyklenschwer" und "nicht schnittleicht" verwendet werden. Ich habe diese Konzepte anderswo nicht gesehen, obwohl sie ganz natürlich sind.
Hier sind zwei interessante Beobachtungen.
Zwei ausreichende, aber nicht notwendige Bedingungen für eine eindeutige MST
quelle