R1 Grundlagen der Graphentheorie
Definitionen und Begriffe
Eine Bemerkung vorweg, in Zusammenhang mit Graphen gibt es viele Begrifflichkeiten, die zumeist recht intuitiv verständlich sind. Dabei weichen die Definitionen in der Literatur allerdings teilweise voneinander ab. Meist ist dies aber erfreulicherweise für das Verständnis unerheblich. Im Zweifelsfall empfiehlt es sich, die Definition in der jeweiligen Veröffentlichung nachzulesen.
Knoten
Kanten
adjazent
benachbart
Definition von Graph
G=(V;E)
Ein Graph G besteht aus einer Menge Knoten V und einer Menge Kanten E. Eine Kante wird durch zwei Elemente (i;j) der Menge V beschrieben.
Grafisch werden Knoten häufig als Kreise und Kanten als Linien dargestellt. Beide Enden der Kanten befinden sich an einem Knoten, d.h. sie verbindet zwei verschiedene Knoten oder ggf. einen Knoten mit sich selbst. Man sagt auch, die Kante inzidiert mit den beiden Knoten, die durch die Kante verbunden werden. Die verbunden Knoten werden als adjazent oder auch benachbart bezeichnet.
Beispiel
G=(V;E)
V= {1;2;3;4}
E={(1;3);(1;4);(2;3);(3;4)
Die Kante (1;3) inzidiert mit den Knoten 1 und 3, die Kante (1;4) inzidiert mit Knoten 1 und 4, … . Die Knoten 1 und 3 sind adjazent. Die Knoten 1 und 4 ebenso, …. )
Kanten werden dazu benutzt, um auszudrücken, dass die Elemente in einer Beziehung zueinander stehen.
Gezeichnet sieht der Graph so aus:
Beispiel
In einem sozialen Netzwerk gibt es 5 Mitglieder.
V= {Anna; Leonie; Niklas; Sarah; Finn}
Eine Kante gibt an, dass die beiden Mitglieder befreundet sind, z.B.
E={(Anna; Niklas); (Anna; Sarah};(Leonie; Niklas);(Leonie;Sarah);(Leonie;Finn);(Niklas;Finn)}
Hinweis:
Eine Kante (i;j) wird nachfolgend gelegentlich auch kurz als Kante ij bezeichnet, wenn dadurch keine Unklarheiten entstehen.
Charakterisierung von Graphen
Ungerichteter Graph
Die Kanten setzen die Knoten in eine Beziehung, ohne eine Richtung anzugeben. Das obige Beispiel eines sozialen Netzwerks ist Beispiel für einen ungerichteten Graphen. Schließlich beruht Freundschaft in sozialen Netzwerken auf Gegenseitigkeit. Ein anderes Beispiel ist ein Straßennetz ohne Einbahnstraßen.
Pfeile
Digraph
Gerichteter Graph
Die Kanten, in diesem Kontext auch als Pfeile bezeichnet und dargestellt, führen von einem Knoten i zu einem anderen Knoten j. In diesem Zusammenhang kann auch von einem Anfangsknoten an dem der Pfeil beginnt und einem Endknoten an dem der Pfeil endet gesprochen werden.
Beispiele sind z.B. ein Graph der zeigt, wer eine Freundschaftsanfrage an jemand anderes geschickt hat oder ein Netzwerk von Einbahnstraßen.
Ein ungerichteter Graph kann meistens in einen gerichteten Graphen überführt werden, indem eine Kante durch zwei gegenläufige Pfeile ersetzt wird.
Im angelsächsischen Raum wird der Begriff Graph ausschließlich für einen ungerichteten Graphen verwendet und die Bezeichnung Digraph für einen gerichteten Graphen.
Schlinge
Eigenkante
Pseudograph
Mehrfachkanten
Multigraph
schlichter Graph
einfacher Graph
Weitere Charakterisierungen
Eine Schlinge oder Eigenkante ist eine Kante (i;i) oder ein Pfeil (i;i) die bzw. der den Knoten mit sich selbst verbindet. Ein Graph der Schlingen enthält wird als Pseudograph bezeichnet.
Man spricht von Mehrfachkanten, wenn es mehrere Kanten oder Pfeile gibt, die dasselbe Knotenpaar (i;j) verbinden. Ein Graph der Mehrfachkanten enthält, wird als Multigraph bezeichnet.
Ein Graph, der keine Schlingen und keine Mehrfachkanten enthält, wird als schlichter Graph oder auch einfacher Graph bezeichnet.
a.) Ist sowohl ein Multigraph als auch ein Pseudograph
b.) Ist ein einfacher Graph
c.) Ist ein einfacher Graph
Weg
Kette
Kreis
Wege in Graphen
Eine Folge von Knoten, die jeweils durch Kanten miteinander verbunden sind, wird im Folgenden als Weg bezeichnet. In gerichteten Graphen dürfen dabei die Pfeile nur in Pfeilrichtung benutzt werden. Werden auch Pfeile gegen die Richtung benutzt, wird dies im Folgenden als Kette definiert.
Sind der Anfangs- und Endknoten eines Weges identisch und auch nur diese, wird dies als Kreis bezeichnet.
Hinweis: Die Bemerkung, dass die Definitionen in der Graphentheorie uneinheitlich sind, gilt an dieser Stelle in besonderem Maß!
Ein ungerichteter Graph heißt zusammenhängend, wenn zwischen allen Knoten ein Weg existiert. Ein gerichteter Graph heißt stark zusammenhängend, wenn von jedem Knoten i zu jedem anderen Knoten j ein Weg existiert. Das bedeutet, dass zwischen zwei Knoten sowohl ein Hinweg als auch ein Rückweg existiert.
Ein gerichteter Graph heißt einseitig zusammenhängend, wenn zwischen jedem Knotenpaar ij mindestens ein Weg von i nach j oder ein Weg von j nach i existiert. Ein gerichteter Graph heißt schwach zusammenhängend, wenn nur eine Kette zwischen allen Knoten existiert.
