Seite 1 von 1

Wiki: Prim

Verfasst: 6. Jul 2012 08:35
von null
Hallo zusammen,

mir ist der Induktionsschritt des Algorithmus von Prim in der Wiki nicht ganz klar. Angenommen man habe diesen Graphen:

Bild

Nach der Induktionsbasis gilt:

Q = {v1, v2, v3, v4, v5}
V0 = {s}
kv1 = 2
kv3 = 3
kv2 = kv4 = kv4 = Infinity


Nun bin ich beim Induktionsschritt, der mir aber Probleme bereitet:

1.) Ich nehme den ersten Knoten v aus Q. Da Q ein Heap ist, erhalte ich den Knoten mit dem kleinsten kv. Das ist v1.
2.) e ist laut Vorlesung die Kante von s nach v1.
3.) Für jedes w € V\Vi-1, also w € {v1, v2, v3, v4, v5} wird geprüft, ob eine noch kürzere Kante abgeht. Hier wird kv1 = 1 gesetzt, weil von v1 nur genau eine Kante abgeht, die auch noch kürzer ist.
4.) Ich füge die Kante zwischene e, also diejenige zwischen s und v1, meiner MST Kantenmeneg E hinzu und gleichzeit füge ich w, also v2 zu meiner MST Knotenmenge hinzu.

Das kann doch nicht sein. Ich müsste doch v1 hinzufügen. Es wird aber v2 gespeichert werden. Übersehe ich da etwas? Könnt ihr mir helfen?

Vielen Dank

Re: Wiki: Prim

Verfasst: 6. Jul 2012 13:37
von Prof. Karsten Weihe
null hat geschrieben:Nun bin ich beim Induktionsschritt, der mir aber Probleme bereitet:
Gemäß History hat Wiki-User Ruebensaft heute genau zu diesem Punkt Änderungen gemacht. Hat sich Ihr Problem damit gelöst? Ich finde Ihr Problem jedenfalls nicht in der aktuellen Version (meinen Dank an "Ruebensaft"!).

KW

Re: Wiki: Prim

Verfasst: 8. Jul 2012 21:00
von null
Hallo,

mit der Wikiänderung macht nun der Eintrag schon mehr Sinn. Trotzdem habe ich noch eine Frage zu folgendem Satz:

"Let e denote the edge stored as information for v in Q"

Aus der Vorlesung weiß ich, dass e wohl die Kante zwischen v und w bezeichnet, doch liest man nur den Wikieartikel, so wird nicht klar, welche Kante gemeint ist.

Außerdem habe ich noch eine Frage dazu:

"Set {v,w} as the new information for w in Q".

Jeder Knoten w, der von dem Knoten v im grünen Bereich erreicht werden kann, erhält nun die Kante e als Information!?

Habe ich das richtig verstanden?

Vielen Dank
null

Re: Wiki: Prim

Verfasst: 9. Jul 2012 09:01
von Prof. Karsten Weihe
null hat geschrieben: "Let e denote the edge stored as information for v in Q"

Aus der Vorlesung weiß ich, dass e wohl die Kante zwischen v und w bezeichnet, doch liest man nur den Wikieartikel, so wird nicht klar, welche Kante gemeint ist.
Im Wiki steht bei der Einführung von \(Q\): "... the information is one of the edges of \(G\) that is incident to \(v\)." Schritt 3.1 des Induction step lautet: "Set \(\{v,w\}\) as the new information for \(w\) in \(Q\)." Welche Information fehlt :?:

null hat geschrieben: Jeder Knoten w, der von dem Knoten v im grünen Bereich erreicht werden kann, erhält nun die Kante e als Information!?
Nein, nur jeder dieser Knoten, der die Bedingung \(\ell(\{v,w\})<k_v\) eine Zeile drüber erfüllt. :roll: :wink:

KW

Re: Wiki: Prim

Verfasst: 9. Jul 2012 10:37
von null
Hallo,

vielen Dank für die Antwort. Diese hilft mir schon weiter.

Heißt das also, dass e irgendeine Kante ist, an auf der v liegt? Sollte e nicht eine minimale Länge haben?

Vielen Dank

Re: Wiki: Prim

Verfasst: 9. Jul 2012 10:50
von Prof. Karsten Weihe
null hat geschrieben: Heißt das also, dass e irgendeine Kante ist, an dessen Ende v liegt.
Nein :!: :roll: :wink:

Die Kante \(e\) ist so gewählt, dass die dritte Invariante erfüllt ist. Dafür wird durch die Abfrage \(\ell(\{v,w\})<k_v\) gesorgt.

KW

Re: Wiki: Prim

Verfasst: 9. Jul 2012 10:54
von null
Aber bei der Initialisierung wurde diese Abfrage doch noch nicht gemacht. Trotzdem hat ja wohl jeder Knoten schon eine Information. e wird vor dieser Abfrage, nämlich im 2. Schritt des Induktionsschritts ausgelesen. Was ist denn hier dann e hier im ersten Schritt? Da gab es noch kein l(v,w) < kv

edit: Ich möchte einfach nur sagen, dass e nicht immer durch die Abfrage l(v,w) < kv gesetzt ist. Falls dies nicht der Fall ist, so ist e genau die Kante, das v der letzten Iteration mit dem aktuellen verbindet. Das finde ich nicht in der Wiki.

Warum speichern wir eigentlich Vi ab? Vi ist am Schluss sowieso wieder V.

Danke :)

Re: Wiki: Prim

Verfasst: 9. Jul 2012 12:01
von Prof. Karsten Weihe
null hat geschrieben:Aber bei der Initialisierung wurde diese Abfrage doch noch nicht gemacht.
Muss sie auch nicht, hier kann man die dritte Invariante einfacher erfüllen:

Es ist ja \(V_0=\{s\}\). Das heißt, es lässt sich sehr genau sagen, für welche Knoten \(v\in V\setminus V_0\;\) schon \(k_v<+\infty\) vor der ersten Iteration gilt, nämlich alle, die mit \(s\) durch eine Kante verbunden sind. Und es gibt nur maximal eine Kante , die \(v\) mit Knoten aus \(V_0\) verbindet, nämlich \(\{s,v\}\), also ist \(\{s,v\}\) die als Info zu speichernde Kante.

KW

Re: Wiki: Prim

Verfasst: 9. Jul 2012 12:07
von null
Ok. Das passt zu meinem edit-Beitrag, oder? Danke für Ihre Hilfe. Die Information, dass e genau die Kante der v der letzten Iteration mit dem aktuellen ist, falls e nicht expliziet gesetzt worden ist, sollte meines Erachtens noch einmal explizit in der Wiki aufgeführt werden. Auch wenn es so vielleicht schon formal richtig ist.....darauf kommen nicht viele.

Re: Wiki: Prim

Verfasst: 9. Jul 2012 12:22
von Prof. Karsten Weihe
null hat geschrieben: Warum speichern wir eigentlich Vi ab?
Wir speichern \(V_i\) nicht, sondern benutzen das Kürzel \(V_i\) nur, um über den Algorithmus zu sprechen. In \(Q\) speichern wir \(V\setminus V_i\) ab.

Nebenbemerkung: Wir könnten genauso gut auch nur diejenigen Knoten \(v\in V\setminus V_i\) abspeichern, für die \(k_v<+\infty\) gilt, damit würde der Algorithmus immer noch funktionieren.

KW

Re: Wiki: Prim

Verfasst: 3. Sep 2012 20:32
von sab
Prof. Karsten Weihe hat geschrieben:Die Kante \(e\) ist so gewählt, dass die dritte Invariante erfüllt ist. Dafür wird durch die Abfrage \(\ell(\{v,w\})<k_v\) gesorgt.
Edit 2:
Hat sich geklärt.

Re: Wiki: Prim

Verfasst: 3. Sep 2012 21:17
von sab
Sorry, mir wird es jetzt doch nicht klar: Warum habe ich als Bedingung im Induction Step \(\ell({v,w}) < k_{w}\) und nicht \(< k_{v}\)?

Re: Wiki: Prim

Verfasst: 3. Sep 2012 21:53
von Seldon
Der Knoten v ist derjenige, den du gerade aus der Queue herausgenommen hast; es sollen alle restlichen w aus Q bei Bedarf aktualisiert werden (wenn also eine Kante e(v, w) existiert und deren l kleiner als die gespeicherte, einem Knoten zugeordnete Kante).

Re: Wiki: Prim

Verfasst: 3. Sep 2012 22:05
von sab
Danke, Seldon, du hast gerade einen großen Knoten in meinem Kopf gelöst! So macht alles sind, mir war nicht ganz klar, dass es das \(k_{w}\) aus Q ist. Aber eigentlich steht das implizit in Aux. Data 2. :)

Re: Wiki: Prim

Verfasst: 3. Sep 2012 23:00
von mcdikki
Ganz einfach weil v nicht mehr in Q ist, sondern schon teil des Ergebnisses und damit kv nicht mehr interessant ist. Wir suchen ja eine Kante {v,w} für fixes v und unbekanntes w. Das heißt wir nehmen v aus Q und bringen w rein bzw. aktualiseren es. Ergo ist l(v,w) < kw interessant.

lg mcdikki

Update: Zu Spät ;-)