Aktualisieren eines MST

8

Bei einem ungerichteten, verbundenen, gewichteten Diagramm G=(V.,E.,w)G=(V,E,w) wo ww ist die Gewichtsfunktion w::E.R.w:ER und ein Minimum Spanning Tree (MST) T.T von GG.
Jetzt verringern wir das Gewicht umkk einer Kante eedas gehört nicht dazuT.T.

So aktualisieren Sie effizient T.T um es zu einem MST zu machen (bezeichnet T.'T) von G'=(V.,E.,w')G=(V,E,w), wo w'w ist das gleiche wie ww außer dass w'(e)=w(e)- -kw(e)=w(e)k?

Der Algorithmus zum AktualisierenT.T zu T.'T ist einfach: Hinzufügen ee zu T.T erstellt einen Zyklus C.C im T.T. Lassene'e eine maximal gewichtete Kante im Zyklus sein C.C. Wennw(e')>w'(e)w(e)>w(e), dann T.'=T.{e}}- -{e'}}T=T{e}{e}ist der MST wie gewünscht. Andernfalls,T.'=T.T=T.

Ich habe Schwierigkeiten, seine Richtigkeit durch Widerspruch zu beweisen . AnnehmenT.T′′ ist ein Spannbaum von G'G und w'(T.)<w'(T.')w(T′′)<w(T).

  • eT.eT′′: wir haben w(T.)=w'(T.)<w'(T.')w(T.)w(T′′)=w(T′′)<w(T)w(T). Widerspricht der Tatsache, dassT.T ist ein MST von GG.
  • eT.eT′′: Ich stecke hier fest.

Zwei Anmerkungen:

  • Die hier akzeptierte Antwort auf dieselbe Frage ist zu allgemein, als dass ich ihr folgen könnte.

  • Ich bevorzuge Beweise, die nicht auf konkreten MST-Algorithmen beruhen, wie die Algorithmen von Kruskal und Prim. Sie müssen dies jedoch nicht durch Widerspruch beweisen oder die beiden Fälle trenneneT.eT′′ und eT.eT′′ wie ich es tat.

Hengxin
quelle
Wenn die Gewichte ganzzahlig sind, können Sie den MST genauso gut neu berechnen. Suchen Sie einen Algorithmus oder ein strukturelles Ergebnis?
Pål GD
@ PålGD Die Neuberechnung eines MST kostet "zu viel" für dieses Problem. Der im Beitrag beschriebene Algorithmus ist linear. Eigentlich suche ich einen formalen, strengen Korrektheitsnachweis dafür .
Hengxin
Tipp: Wie finde ich den minimalen Spannbaum, der eine bestimmte Kante enthält / nicht enthält?
Ablmf
@ablmf Danke. Meinst du einen Algorithmus? Ich suche jedoch einen Beweis. Würde es Ihnen etwas ausmachen, eine Antwort zu veröffentlichen, wenn Sie eine haben?
Hengxin
@hengxin Der Algorithmus zum Ermitteln des Mindestbaums mit einer Kante eeist geradeaus. Finde einen MSTT.T. Hinzufügeneedazu entsteht ein Kreislauf. Entfernen Sie dann die schwerste Kante außereein diesem Zyklus. Wenn Sie beweisen können, dass der Algorithmus korrekt ist, sind Sie fertig.
Ablmf

Antworten:

2

Lassen T.T ein Minimum Spanning Tree von sein GG. Lassenee Sei der Rand, den wir modifizieren, um ihn zu bekommen G'G, und lass T.'Tsei der nach dem Algorithmus berechnete Baum. Wir kennen das Gewicht vonT.'T ist kleiner oder gleich dem Gewicht von T.T.

Zuerst, T.'T ist ein Baum - wir erstellen genau einen Zyklus im Algorithmus und brechen ihn auf, sodass wir keine Zyklen haben T.'T.

Zweitens T.'Tist ein Spannbaum vonG'G. Lassene'e die Kante entfernt werden und ee′′ sei die Kante, die im Algorithmus hinzugefügt wird (wir haben entweder e=e'e′′=e oder e=ee′′=e). Um ein Spanning Tree zu sein, müssen wir einen Pfad zwischen jedem Scheitelpunktpaar habenuu, vv mit nur Kanten von T.'T. Angenommen, das inT.T (was definitiv ein Spannbaum ist), der Weg von uu zu vv nicht beteiligt e'e, dann existiert der gleiche Pfad in T.'T. Angenommen, es wurde verwendete'e, dann gibt es einen Weg (ohne Verlust der Allgemeinheit) von uu zu einem Endpunkt von e'e und vom anderen Endpunkt von e'e zu vv. Es gibt auch einen Pfad von einem Endpunkt vone'e zum anderen Endpunkt über ee′′ (rund um den Zyklus), alle innerhalb T.'T. Dann können wir einen Pfad aus konstruierenuu zu vv über ee′′ im T.'T durch Zusammenführen dieser drei Pfade und Entfernen der Überlappung (obwohl ein Spaziergang für die Konnektivität ausreicht).

Nun, der wichtige Teil, wir möchten das beweisen T.'Tist ein minimaler Spannbaum fürG'G.

Fall 1 : Der Algorithmus fügt nicht hinzueezum Baum. In diesem FallT.'=T.T=T. Angenommen, es gibt einen minimalen SpannbaumH.H zum G'G das ist anders als T.'T. WennH.H hat das gleiche Gewicht wie T.'T, Wir sind fertig. Nehmen wir nun für den Widerspruch an, dass das Gewicht vonH.H ist weniger als das Gewicht von T.'T. Es muss eine Kante gebene'e des niedrigsten Gewichts, das in ist H.H aber nicht in T.'T (Es muss eine Kante geben, die es sonst besser macht GG wäre nicht von geringerem Gewicht als T.'TAußerdem können wir davon ausgehen, dass die Kante, die besser abschneidet, die Kante mit dem niedrigsten Gewicht ist, die nicht vorhanden ist T.'T - Wir können jeden nehmen H.'H das ist ein Baum mit geringerem Gewicht als T.'T und schauen Sie sich den Kandidaten für e'e, wenn es nicht kleiner als eine Kante in seinem Zyklus ist, dann auch nicht H.'H ist kein MST, oder wir können ein neues erstellen H.'H wo wir die tauschen e'e für einen Rand von T.'TDieser Prozess muss mit einer Kante enden e'e welches die Eigenschaft hat, dass es die Kante ist, die es besser macht).

  1. Wenn e'eeeBetrachten Sie dann den Baum, der durch Hinzufügen erhalten wurde e'e zu T.T (Beachten Sie nicht T.'T) und Entfernen der höchsten Gewichtskante des gebildeten Zyklus. Dieser neue Baum hat ein geringeres Gewicht als das vonT.T und ist ein Spannbaum für GGim Widerspruch zu der Tatsache, dass T.T ist ein MST für GG - Wir wissen also, dass dies nicht passieren kann.
  2. Wenn e'=ee=eBetrachten Sie den Zyklus, der durch Hinzufügen gebildet wird e'=ee=e zu T.'T(dh derjenige, den der Algorithmus berücksichtigt). Alle anderen Kanten im Zyklus haben ein geringeres Gewicht alse'e (sonst hätte der Algorithmus enthalten ee als Kante) und muss daher in sein H.H (wie e'e ist die Kante mit dem niedrigsten Gewicht, die noch nicht vorhanden ist T.'T), aber dann H.H muss einen Zyklus enthalten, ist also kein Baum und wir haben einen Widerspruch.

Fall 2 : Der Algorithmus fügt hinzuee zu T.'T. Lassenxx sei der Rand in T.T das wird vom Algorithmus entfernt (und damit nicht in T.'T) Nehmen wir wieder an, wir haben eine andere MST H.Hwie vorher. Wenn das Gewicht gleich ist, freuen wir uns. Nehmen Sie also für den Widerspruch an, dassH.H hat ein geringeres Gewicht und wie zuvor e'e ist die niedrigste Gewichtskante in H.H das ist nicht in T.'T. Wir können ähnliche Argumente wie zuvor mit vorbringenxx.

  1. Wenn e'xex, (beachte auch das e'eee), dann können wir uns verbessern T.T wie zuvor, aber das wissen wir T.T ist ein MST und erinnert an die Eigenschaft, die wir annehmen können e'e hat ein geringeres Gewicht als mindestens eine Kante in dem Zyklus, den seine Addition induziert, dies ergibt einen Widerspruch und H.H kann nicht existieren.
  2. Wenn e'=xe=x, dann wieder e'e muss daher ein höheres Gewicht haben als alle anderen Kanten im Zyklus H.H muss alle diese Kanten enthalten und H.H ist kein Baum, und wir leiten einen Widerspruch her.

In jedem Fall leiten wir also einen Widerspruch ab, daher kann es keinen Spannbaum mit geringerem Gewicht geben T.'Tdaher T.'T ist ein minimaler Spannbaum für G'G.

Luke Mathieson
quelle
Danke für deine Bemühungen. Einige Verwirrung über die Aussage "Wenne'xex (Beachten Sie auch das e'eee), dann können wir ... "in Fall 2.1: (1) warum ist e'eee? Nehmen Sie das an?eH.eH? (2) VerbesserungT.T beim Hinzufügen e'e dazu und entfernen Sie eine andere Kante, sagen wir ee′′Das müssen wir zeigen e'T.eT und w(e)>w(e')w(e′′)>w(e). Wie garantieren Sie diese?
Hengxin
@hengxin weil in 2.1 e'eist nicht inT.'T, aber eeist, also können sie nicht gleich sein.
Luke Mathieson
OK, ich verstehe. Was ist dann mit meiner zweiten Frage? Ich glaube, ich habe das bewiesene'T.eT, so können wir hinzufügen e'e zu T.Teinen Zyklus erstellen. Wie garantieren Sie jedoch, dass es einen Vorteil gibt?ee′′, in the cycle of greater weight than w(e)w(e) so that we can improve TT by removing ee′′?
hengxin
@hengxin, sorry missed the (2) in there exeexe, and xx and ee is the only swap from TT to TT, so ee must be a different, third edge that's in nether TT nor TT, and the properties we had before are true again, if HH were a better MST, then ee must weigh less than some edge in TT, in particular, it must weigh less than some edge in the cycle it creates (otherwise all those edges must also be in HH, and HH isn't a tree).
Luke Mathieson
1
Still confused. I am almost lost in the "forest" of trees. I know ee weighs less than some edge in TT: why does it also weigh less than some edge in TT? Suppose it does, why does it weigh less than some edge in the cycle (I don't understand the "otherwise")? Can other edges all have equal weights with w(e)w(e)? Do you have the time for a chat?
hengxin
2

Let SS be a spanning tree of an edge-weighted graph GG. We call SS a local-minimum spanning tree of GG if for any edge ee not in SS, ee is a heaviest edge in the cycle created when we add ee to SS.

Let me introduce a theorem about minimum spanning tree (MST).

A spanning tree is an MST if and only if it is a local-minimum spanning tree.

A proof of the above theorem by the OP herself/himself does not rely on any concrete MST algorithm.

In another proof of the above theorem but stated differently, you can also read the reason why such a spanning tree is called "local-minimum".

The above theorem enables us to verify an MST edge by edge although MST is defined with respect to all edges together.


Once we are armed with the above theorem, it becomes easy to prove the correctness of the algorithm in the question. It should be, in fact, easier to construct a proof by yourself than reading the rigorous proof below.

A simple proof of the algorithm in the question

Let us reuse all notations in OP's definition of the algorithm.

Note that TT is a local-minimum spanning tree of GG. To prove TT is an MST of GG, we will show TT is a local-minimum spanning tree of GG. There are two cases.

  • when w(e)w(e) and T=T.

    Since the only difference between T in G and T in G is the weight of edge e, we need to check e only. Since e is a heaviest edge in C with w, the condition w(e)w(e) means that e is a heaviest edge in C with w. We are done in this case.

  • when w(e)>w(e) and T=T{e}{e}.

    1. Let us consider e. The cycle created when we add e to T is also C. Since e is a heaviest edge in C with w, the new weight of e, w(e)<w(e) means that e remains a heaviest edge in C with w.
    2. Now let fe be an edge not in T. Let D be the cycle created when we add f to T. Since T is an MST of G, f is a heaviest edge in D with w.
      • If eD, D is also the cycle created when we add f to T. As w and w are the same on D, f remains a heaviest edge in D with w.
      • Now suppose eD. If we replace e with all edges in C other than e, we get from D a new cycle D, which is the cycle created when we add f to T. Since e is a heaviest edge in C with w, f remains a heaviest edge in D with w. Since the only difference between w and w is their values on e, for which we have w(e)<w(e)w(f)=w(f), we see that f remains a heaviest edge in D with w.
    3. Combining step 1 and 2, we are done in this case.

Note that both the algorithm and the proof above work well regardless whether the weight of e is decreased, intact or increased.

On the equal weights of edges

It is a common practice to assume distinct weights of all edges for the sake of clearer exposition. However, this post works well with possibly equal edge-weights. In particular, we have been referring to "a heaviest edge" but never "the heaviest edge".

John L.
quelle
A simpler proof is to apply the delete-heavy-edge algorithm
John L.