So aktualisiert MST aus dem alten MST wenn eine Flanke

Question

gelöscht

Ich studiere Algorithmen, und ich habe eine Übung wie diese

gesehen ich dieses Problem mit exponentieller Zeit überwinden kann aber. Ich weiß nicht, wie man diese lineare Zeit beweist O (E + V)

Ich werde jede Hilfe schätzen.

Answer 1

Sei G der Graph, in dem der minimale Spannbaum T eingebettet ist; A und B seien die beiden Bäume sein, die nach (u, v) entfernt wird von T.

Premise P: Wählen Mindestgewicht Kante (x, y) von G - (u, v), der erneut eine Verbindung A und B. Dann ist T '= A + B + (x, y) ein MST von G - (u, v).

Nachweis P: Es ist offensichtlich, dass T‘ist ein Baum. Angenommen, es wäre kein Minimum. Dann würde es eine MST - nennen Sie es M - von geringerem Gewicht. Und entweder enthält M (x, y), oder es nicht.

Wenn M (x, y) enthält, muss es die Form A '+ B' + (x, y) haben, wobei A 'und B' Bäume mit minimalem Gewicht sind, die die gleichen Ecken wie A bzw. B umfassen . Diese dürfen kein geringeres Gewicht als A und B haben, sonst wäre T kein MST gewesen. Also ist M nicht kleiner als T ', ein Widerspruch; M kann nicht existieren.

Wenn M nicht (x, y) enthält, dann gibt es einen anderen Pfad P von x nach y in M. Eine oder mehrere Kanten von P gehen von einer Ecke in A zu einer anderen in B. Rufen Sie eine solche Kante auf c. Nun, c hat mindestens das Gewicht von (x, y), sonst hätten wir es anstelle von (x, y) gewählt, um T 'zu bilden. Hinweis P + (x, y) ist ein Zyklus. Folglich ist M - c + (x, y) auch ein Spannbaum.Wenn c ein größeres Gewicht als (x, y) hätte, hätte dieser neue Baum ein geringeres Gewicht als M. Dies widerspricht der Annahme, dass M eine MST ist. Wiederum kann M nicht existieren.

Da in beiden Fällen M nicht existieren kann, muss T 'eine MST sein. QED

Algorithmus Durchqueren Sie A und färben Sie alle Ecken rot. In ähnlicher Weise kennzeichnen Sie die Scheitelpunkte von Blue. Durchquere nun die Kantenliste von G - (u, v), um eine Kante mit minimalem Gewicht zu finden, die einen roten Scheitelpunkt mit einem blauen verbindet. Die neue MST ist diese Kante plus A und B.

Answer 2

Wenn Sie eine der Kanten entfernen dann die MST bricht in zwei Teile, rufen sie a und b können, also was Sie tun können, ist a alle Ecken von dem Teil durchlaufen und suchen für alle benachbarten Kanten, wenn eine der Die Kanten bilden eine Verbindung zwischen dem Teil a und Teil b Sie haben das neue MST gefunden.

Pseudocode:

for(all vertices in part a){ 
    u = current vertex; 
    for(all adjacent edges of u){ 
     v = adjacent vertex of u for the current edge 
     if(u and v belong to different part of the MST) found new MST; 
    } 
} 

Komplexität O (V + E)

Anmerkung: Man kann ein einfaches Array halten zu überprüfen, ob Vertex in Teil a des MST oder teil b ist.

Beachten Sie auch, dass Sie eine Adjazenzlisten-Darstellung des Graphen benötigen, um die O (V + E) -Komplexität zu erhalten.

Answer 3

Nehmen wir an, Sie haben Graph G 'nach dem Entfernen der Kante. G 'besteht aus zwei verbundenen Komponenten.

Lassen Sie jeden Knoten im Diagramm eine Komponenten-ID haben. Legen Sie die Komponenten-ID für alle Knoten fest, basierend darauf, zu welcher Komponente sie gehören. Dies kann mit einem einfachen BFS beispielsweise auf G 'erfolgen. Dies ist eine O (V) -Operation, da G 'nur V-Knoten und V-2-Kanten hat.

Sobald alle Knoten markiert sind, iteriere über alle unbenutzten Kanten und finde die mit der geringsten Gewichtung, die die beiden Komponenten verbindet (die Komponenten-IDs der beiden Knoten sind unterschiedlich). Dies ist eine O (E) -Operation.

Somit ist die Gesamtlaufzeit O (V + E).