Graphen | MathePrisma

Graphen

Wege

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

Joes Problem ist ein typisches Wege-Problem auf einem Graphen.

der USA-Graph

	Die Nachbarschaften der Staaten der USA ...
	... werden durch einen Graphen beschrieben.
	Big Bad Joe muss vom linken blauen Knoten zum rechten.

Anschaulich besteht ein Graph aus Knoten und aus Kanten, welche jeweils zwei Knoten verbinden.

Unser Beispiel

Im USA-Graph gilt:

Knoten: die 48 Staaten der USA (ohne Alaska und Hawaii)
Kanten: Zwei Knoten sind durch eine Kante verbunden, wenn die zugehörigen Staaten eine gemeinsame Grenze haben.

Joes Problem lautet also:

Finde einen Weg von Kalifornien nach Pennsylvania mit möglichst wenig Kanten.

Dies ist eine Abstandsaufgabe für den USA-Graph.

Abstandsaufgabe

Gegeben: Ein Graph und zwei Knoten des Graphen.
Gesucht: Ein Weg mit möglichst wenig Kanten, der die beiden Knoten verbindet. Die Anzahl der Kanten dieses Weges ist der Abstand der beiden Knoten.

eine Lösung für Joe

Bewege die Maus über das Bild.

Gibt es noch andere Lösungen?

usa0

usa1

usa2