Graphen

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

In diesem Modul behandeln wir Algorithmen, welche die Zusammenhangsaufgabe und verschiedene Abstandsaufgaben systematisch und effizient lösen.
Dabei wirst du häufig interaktiv mit Graphen arbeiten.

Notation

Wir notieren die Knoten mit v (engl.: vertex) und die Kanten mit e (engl.: edge).

Eine formale Definition ist dann:

Definition

Ein Graph ist ein Paar (V,E) aus einer Menge V von Knoten, V= {v1,...,vn}, und einer Menge E von Kanten, E = {e1,...,em}. Jede Kante ek verbindet zwei (verschiedene) Knoten vi, vj. Sie wird durch das Knotenpaar dargestellt, ek = {vi,vj}.

üben

Kontrollaufgaben