Graphen

Durchlaufen

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 präzisieren die Begriffe.

Neue Begriffe

Zwei Knoten v1, v2 heißen benachbart, wenn die Kante {v1,v2} existiert.
Ein Kantenzug (v1,v2,...,vk) von v1 nach vk ist eine Folge von Kanten{v1,v2}, {v2,v3},...
Zwei Knoten v1, vk heißen verbindbar, wenn es einen Kantenzug von v1 nach vk gibt.
Ein Knoten v ist stets mit sich selbst verbunden, und zwar durch den leeren Kantenzug ( ).
Die Menge aller mit einem Knoten verbindbaren Knoten heißt eine Zusammenhangskomponente des Graphen.

Wir sagen also ab jetzt 'Kantenzug' statt 'Weg', weil das in der Graphentheorie so üblich ist.

ein Beispiel

	Ein Graph mit 8 Knoten und 7 Kanten
	v1 und v2 sind benachbart
	der Kantenzug (v8,v5,v4,v6)
	v8 und v6 sind verbindbar
	der Graph besitzt zwei Zusammenhangskomponenten

ung0

ung1

ung2

ung3

ung4