Graphen | MathePrisma

Graphen

Korrektheitsbeweis

Wege

Durchlaufen

Abstände

Gewichte

Richtungen

Arbeitsblatt

Aufgabe 1

Wie groß ist der Abstand von Colorado (CO) und Virginia (VA) im USA-Graph (Seite Wege 2)?

Aufgabe 2

Wie lange dauert die kürzeste Verbindung von King's Cross zu Earl's Court (Seiten Gewichte 1,3)?

Aufgabe 3

Eine neue Aufgabe für Graphen: Finde alle Knoten, die von einem gegebenen Knoten maximalen Abstand besitzen.
Diese Aufgabe kann man für gewichtete und für ungewichtete Graphen stellen.

Welche Staaten haben im USA-Graph (Seite Aufgaben 2) den größten Abstand von Florida?
Welche Stationen haben im Londoner U-Bahnnetz den größten (gewichteten) Abstand vom Piccadilly Circus?
Ist es richtig, dass man diesen größten Abstand mittels Tiefensuche bestimmen kann, wenn man dabei wie üblich d(u) (bzw. dg(u)) aufdatiert und dann den größten gefundenen Wert nimmt?

Aufgabe 4

In einem Graphen bilden alle die Knoten, welche miteinander verbindbar sind, eine Zusammenhangskomponente.

Finde den Graphen des Applets auf der Seite Durchlaufen 2, welcher mehr als eine Zusammenhangskomponente besitzt.
Entferne aus Graph 5 drei Kanten so, dass der entstandene Graph drei Zusammenhangskomponenten besitzt.
Formuliere, aufbauend auf dem Algorithmus 'Durchlaufen' einen Algorithmus, der alle Zusammenhangskomponenten eines Graphen dadurch findet, dass er diese durchnummeriert und jedem Knoten die Nummer seiner Zusammenhangskomponente zuweist.

Aufgabe 5

Man kann den Algorithmus von Dijkstra auch so formulieren, dass gleich zu Beginn alle Knoten in D eingefügt werden und dann nur noch aus D entnommen wird. Formuliere diese Variante im Detail.

Aufgabe 6

Gib für die folgenden Aufgaben jeweils an, wie sie mit Graphen modelliert werden können. Gib dazu an, was jeweils Knoten und Kanten darstellen, ob der Graph gewichtet oder gerichtet ist und um welche Art von Aufgabe es sich handelt.

Routenplaner für die Autobahn: kürzeste Verbindung zwischen zwei Ausfahrten.
Ausfallplanung des Stromversorgers: Werden die Kunden noch beliefert, wenn bestimmte Leitungen ausfallen?
Brunnenvergiftung: In ein Kanalnetz gelangt ein Schadstoff. Wo wird er überall auftauchen? Wann?

Aufgabe 7

Begründe, warum auch der folgende Algorithmus die gewichteten Abstände von v bestimmt.

Eingabe: gewichteter Graph G, Knoten v dieses Graphen
Ausgabe: Gewichte dg(w) von Kantenzügen, die w und v verbinden

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

Warum ist der Algorithmus von Dijkstra besser?

Drucken

Wir zeigen also

Korrektheit

Der Algorithmus von Dijkstra bestimmt die gewichteten Abstände dg(w) für alle Knoten w.

Vorüberlegungen

Auch der Algorithmus von Dijkstra realisiert eine mögliche Variante für das Durchlaufen eines Graphen. Wir haben wegen der Übersichtlichkeit diesmal keine Vorgängerknoten 'gemerkt'. Dies könnte man aber einfach (nämlich so wie in den anderen Algorithmen) ergänzen.
Deshalb ist Folgendes bereits klar:

Für jeden Knoten w ist dg(w) < $\infty$ genau dann, wenn w von v aus erreichbar ist.
Für jeden Knoten w mit dg(w) < $\infty$ ist dg(w) die gewichtete Länge eines Weges von v nach w.

Dass dg(w) wirklich kleinstmöglich ist, zeigen wir wieder mit geeigneten Assertions. Wir unterscheiden (zunächst) zwischen der berechneten Zahl dg(w) und dem tatsächlichen gewichteten Abstand ag(w) von Knoten w von v. Wir wollen also zeigen:

dg(w) = ag(w) für alle von v aus erreichbaren Knoten w,

und wissen bereits

ag(w) ≤ dg(w) für alle von v aus erreichbaren Knoten w.

bewege die Maus über die Assertions (bewege das Fenster zuerst so, dass du das gesamte gelbe Feld siehst)

Übrigens: Bei der Begründung von Assertion A2 ging wesentlich mit ein, dass alle Kantengewichte nicht negativ sind.