Wege und gerichtete Graphen
Wege in ungerichteten Graphen
Max und Tax laufen jeden Tag durch den Park zur Schule. Sie betreten ihn an der Brücke B und verlassen ihn am Ausgang A. Damit es nicht langweilig wird, nehmen sie gern verschiedene Wege.
Merke: Weg
Ein Weg in einem Graphen ist eine Folge von Knoten, bei der je zwei aufeinanderfolgende Knoten durch eine Kante verbunden sind. Wege schreibt man als Wörter über dem Alphabet der Knoten. Im Bild ist der Weg ABCE markiert.
Der erste und der letzte Knoten heißen Endknoten des Weges: A ist der Startknoten, E der Zielknoten. Alle anderen Knoten des Weges heißen innere Knoten.
Ein Knoten darf in einem Weg auch mehrfach vorkommen, z. B. ABDBCE.
G = (V, E)
V = {A, B, C, D, E}
E = {{A,B}, {B,C}, {A,D}, {D,C}, {C,E}, {B,D}}
Gerichtete Graphen
In der Innenstadt von St. Wendel gibt es Einbahnstraßen: Man darf sie nur in einer Richtung befahren. Ein Graph, der das abbilden soll, braucht Kanten mit Richtung.
Quelle: Google Maps
Definition: gerichteter Graph
Ein gerichteter Graph G = (V, E) besteht aus einer Menge V von Knoten und einer Menge E ⊆ V × V von Kanten. Jede Kante ist ein Tupel (v, w) – ein geordnetes Paar: Sie führt von v nach w und wird als Pfeil gezeichnet. (v, w) und (w, v) sind verschiedene Kanten.
G = (V, E)
V = {A, B, C, D}
E = {(A,B), (B,C), (C,B), (C,D), (D,A), (A,C)}
Merke
Ungerichtet: Kanten sind Mengen {A, B} – die Verbindung gilt in beide Richtungen. Gerichtet: Kanten sind Tupel (A, B) – „von A nach B“.