Graphen | MathePrisma

wir helfen Joe

Wir kommen jetzt zum Abstandsproblem. Dazu betrachten wir die Aufgabe

Finde den Abstand aller Knoten von einem gegebenen Knoten v und die zugehörigen Wege.

Joe weiß dann nicht nur, wieviele Grenzen er bis nach PA überqueren muss, sondern auch bis nach NY und nach TX und nach FA und ... und ... und ... .

Breitensuche: Schnappschüsse

	Bei Breitensuche von v aus ...
	... findet man zuerst alle Knoten mit Abstand 1
	von denen aus dann die mit Abstand 2
	dann Abstand 3
	usw.

Wir ergänzen also die Breitensuche so, dass der Abstand d(w) zwischen jedem Knoten w und v ausgerechnet wird. Außerdem merken wir uns jeweils den Vorgänger vorg(w) im zugehörigen Kantenzug. Auf diese Weise werden die Kantenzüge mit konstruiert. Es ergibt sich der Algorithmus von Moore (1959).

Abstände

Algorithmus von Moore:

Eingabe: Graph G, Knoten v dieses Graphen
Ausgabe: Abstand d(w) aller Knoten w von v und Vorgängerknoten vorg(w) im zugehörigen Kantenzug. Knoten mit d(v) = $\infty$ sind nicht mit v verbindbar und haben keinen Vorgänger.

für alle Knoten w
     setze d(w) = $\infty$ , vorg(w) = { }
füge v in eine (zunächst leere) Queue D ein
setze d(v) = 0
solange D nicht leer ist
     entnehme einen Knoten w aus D
     für alle Kanten {w,u}
          falls d(u) = $\infty$
               setze d(u) = d(w)+1, vorg(u) = w
               füge u in D ein

Welche der folgenden Beziehungen gelten für jeden besuchten Knoten w $\neq$ v?

d(w) $\neq \infty$
vorg(w) = { }
d(w) = 1
vorg(w) $\neq$ { }
vorg(w) = v

Moore

Hier kannst du den Algorithmus von Moore ausführen. Es gibt diesmal zwei interaktive Modi.

Im ersten Modus sollst du nur jeweils den richtigen Knoten auswählen.
Im zweiten Modus sollst du auch noch die aktuellen Entfernungen berechnen und eintragen.

Unsere Empfehlung: Modus 'interaktiv 2'.

im eigenen Interesse:
gut nachdenken!

Bearbeite zum Abschluss diesen Fragebogen zum Algorithmus von Moore.

Es sei d(vorg(w)) = 3. Wie groß ist d(w)?

Was trifft zu?

wenn vorg(w) = v ist, so ist d(w) = 1
Für alle w mit vorg(w) $\neq$ { } ist d(vorg(w)) = d(w) -1.
Das Ganze geht doch auch, wenn D ein Stack ist (Tiefensuche).
Die d(w) sind für alle Knoten in D gleich.
Für alle Knoten in D unterscheiden sich die d(w) höchstens um 1.
Weil D Queue ist, wird stets ein Knoten w entnommen, für den
d(w) minimal ist.
Das Verfahren ist auch dann korrekt, wenn D irgendeine
Datenstruktur ist, aus welcher man stets einen Knoten w
mit minimalem d(w) entnimmt.

Beweis?

Wir haben den Algorithmus von Moore anschaulich eingeführt und motiviert. Eine mathematisch strenge Begründung für seine Richtigkeit erfordert wieder einen Korrektheitsbeweis.