Inhaltsverzeichnis
Graphen
Graphen bestehen aus Knoten und Kanten. Kanten verbinden jeweils zwei Knoten. Kanten können gerichtet sein (d.h. sie können nur in einer Richtung durchlaufen werden, ähnlich wie eine Einbahnstraße) oder ungerichtet und sie können Gewichte besitzen (z.B. Länge einer Strecke). Die Gewichte werden an den Kanten notiert. Graphen, deren Kanten keine Gewichte besitzen, heißen ungewichtet (auch: unbewertet).
Folgen von Kanten, die zwei Knoten verbinden heißen Pfad. Ein Pfad, dessen Anfangs- und Endknoten übereinstimmt heißt geschlossener Pfad. Ein Knoten A heißt von einem anderen Knoten B aus erreichbar, wenn es von B nach A einen Pfad gibt. Ein geschlossener Pfad, der keine Kante zweimal enthält, heißt Zyklus. Ein Graph, der mindestens einen Zyklus besitzt, heißt zyklisch.
Ein ungerichteter Graph heißt zusammenhängend, wenn von jedem Knoten zu jedem anderen ein Pfad existiert.
Ein gerichteter Graph heißt
- stark zusammenhängend, wenn von jedem Knoten zu jedem anderen ein Pfad existiert
(damit ist natürlich insbesondere gemeint, dass die Kanten in der vorgegebenen Richtung durchlaufen werden), - schwach zusammenhängend, wenn er als ungerichteter Graph zusammenhängend wäre und
- ansonsten unzusammenhängend (auch bei ungerichteten Graphen).
Beispiel 1
Dieser Graph ist gewichtet (die Kantengewichte geben die Straßen-Distanz in Kilometern an), ungerichtet, zyklisch und nicht zusammenhängend.
Knoten wie Helgoland in Beispiel 3, die zu keinem anderen Knoten eine Kante besitzen, heißen isoliert.
Aufgabe 1
Aufgabe 2
Derselbe Graph kann auf unterschiedliche Weise als Diagramm dargestellt werden. Welche der Diagramme im Bild rechts stellen denselben Graph dar?
Lösung
Aufgabe 3
Nennen Sie je zwei Anwendungsbeispiele, die als gerichtete, ungerichtete oder gewichtete Graphen dargestellt werden können.