Graphen
"In der Kürze liegt die Würze"
Autor(en): Timo Bergenthal, Andreas Frommer, Dieter Paulerberg - Oktober 2019
Kapitelübersicht
Mit einem einführenden Beispiel motivieren wir die Abstands- und die Zusammenhangsaufgabe.
Wir besprechen die Standard-Techniken zum Durchlaufen eines Graphen, insbesondere die Breiten- und die Tiefensuche. Damit wird auch die Zusammenhangsaufgabe gelöst.
Wir besprechen den Algorithmus von Moore für kürzeste Wege bei Einheitsgewichtung
Wir motivieren Entfernungsaufgaben mit Kantengewichten am Beispiel von U-Bahn-Verbindungen und behandeln dann den Algorithmus von Dijkstra für kürzeste Wege bei (positiven) Kantengewichten
Wir übertragen die Algorithmen auf gerichtete Graphen
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) = 
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
sind.)