Schon in Abschnitt “Ein Anwendungsbeispiel: Breitensuche in einem Graphen” haben wir einen Graphen kennen gelernt. In Abbildung 3.2 haben wir vierbuchstabige Wörter als Knoten aufgefasst und diese durch eine Kante miteinander verbunden, wenn sie sich nur durch einen einzigen Buchstaben unterscheiden; in diesem Sinne sind sie „benachbart“. Ein solches Gebilde aus Knoten und Kanten wird als Graph bezeichnet. Wie wir dort schon angedeutet haben, treten solche Strukturen in der Informatik häufig auf, nämlich überall da, wo es um die Modellierung von Beziehungen zwischen einzelnen Objekten geht. Die Objekte entsprechen dabei den Knoten, die Beziehungen den Kanten eines Graphen. Bevor wir uns LEDAs Implementierung von Graphen zuwenden, wollen wir zunächst einige wichtige Grundbegriffe aus diesem Themengebiet kennen lernen.

Im Unterschied zu Abbildung 3.2 zeigt Abbildung 5.1 einen Graphen, bei dem die Kanten gerichtet sind. Der Graph selbst wird demgemäß als gerichteter Graph bezeichnet. Solche Graphen treten auf, wenn die Beziehung zwischen zwei Objekten nicht unbedingt symmetrisch ist, etwa bei Graphen, die Verwandtschaftsverhältnisse modellieren: Ist Anja ein Elternteil von Sibylle, so kann niemals Sibylle auch ein Elternteil von Anja sein. Die Beziehung „geht nur in eine Richtung“.

Formal gesehen ist ein solcher Graph G ein Paar (V,E), wobei V eine endliche Menge ist und E eine Menge von Paaren (v1,v2) mit v1 und v2 aus V. Die Elemente von V werden als Knoten (vertices, nodes) bezeichnet, die Elemente aus E als Kanten (edges). Eine Kante (v1,v2) wird als von v1 nach v2 gerichtet interpretiert; sie geht von v1 aus und ist zu v2 inzident. Der Knoten v1 wird dabei als Quelle (source) der Kante bezeichnet, der Knoten v2 als das Ziel (target). v2 ist adjazent zu v1; die Umkehrung muss nicht unbedingt gelten, da die umgekehrte Kante oder Rückwärtskante (reverse edge), also die Kante (v2,v1), nicht unbedingt existieren muss. v1 ist ein Nachbar (neighbor) von v2 und umgekehrt. Eine Kante (v1,v1), die von einem Knoten zu sich selbst zeigt, wird als Selbstschleife (self-loop) bezeichnet.

Abbildung 5.1. Ein gerichteter Graph

Ein gerichteter Graph mit der Knotenmenge V = {0,1,2,3,4,5,6} und der Kantenmenge E = {(0,1),(0,3),(1,1),(1,2),(2,3),(3,0),(4,5),(4,6)}. Die Quelle der Kante (0,1) ist der Knoten 0, das Ziel der Knoten 1. Die Kante (0,1) geht vom Knoten 0 aus und ist zum Knoten 1 inzident. 1 ist adjazent zu 0, aber nicht umgekehrt. 0 und 1 sind Nachbarn. Die Kante (1,1) ist eine Selbstschleife. Der Eingangsgrad von 0 ist 1, der Ausgangsgrad ist 2. Der Grad von 0 ist 1+2=3. Der Pfad (0,1,1,1,2,3) führt vom Knoten 0 zum Knoten 3; seine Länge ist 5; er ist nicht einfach. Der Pfad (0,1,2,3,0) ist ein Zyklus der Länge 4; der Graph ist also zyklisch. Er ist nicht stark zusammenhängend, weil z. B. 4 nicht von 1 aus erreichbar ist.

Im Gegensatz zu einem gerichteten Graphen haben die Kanten in einem ungerichteten Graphen keine Richtung. Formaler ausgedrückt ist bei einem ungerichteten Graphen die Menge E eine Menge von zweielementigen Teilmengen {v1,v2} von V. Eine Kante {v1,v2} ist sowohl zu v1, als auch zu v2 inzident. v1 ist adjazent zu v2 und umgekehrt. v1 und v2 sind Nachbarn. Da die Menge {v,v} dieselbe ist wie die Menge {v}, sind Selbstschleifen in ungerichteten Graphen verboten bzw. unmöglich.

Abbildung 5.2 zeigt einen ungerichteten Graphen. Solche Graphen treten auf, wenn die Beziehung zwischen je zwei Objekten symmetrisch ist, etwa bei Graphen, die die von den Fußballmannschaften einer Liga in der Hinrunde einer Saison schon gegeneinander gespielten Spiele modellieren: Wenn Mannschaft A schon gegen Mannschaft B gespielt hat, dann hat auch umgekehrt Mannschaft B schon gegen Mannschaft A gespielt.

Abbildung 5.2. Ein ungerichteter Graph

Ein ungerichteter Graph mit der Knotenmenge V={0,1,2,3,4,5,6} und der Kantenmenge {{0,1},{0,3},{1,2},{2,3},{4,5},{4,6}}. Die Kante {0,1} ist zu den Knoten 0 und 1 inzident. 0 und 1 sind adjazent zueinander. Der Grad von 0 ist 2. Der Graph ist zyklisch und nicht zusammenhängend.

Die ungerichtete Version eines gerichteten Graphen entsteht dadurch, dass alle Kanten ihre Richtung verlieren und Selbstschleifen entfernt werden. Umgekehrt entsteht die gerichtete Version eines ungerichteten Graphen dadurch, dass für jede ungerichtete Kante {u,v} zwei zueinander umgekehrte Kanten (u,v) und (v,u) erzeugt werden.

	Anmerkung
	Schon an dieser Stelle wollen wir darauf hinweisen, dass LEDA ein etwas anderes Verständnis der Begriffe „gerichtet“ und „ungerichtet“ hat. Wir werden näher darauf in Abschnitt 5.2.3 eingehen.

Der Grad (degree) eines Knotens in einem ungerichteten Graphen ist die Anzahl der zu ihm inzidenten Kanten. In einem gerichteten Graphen dagegen unterscheidet man zwischen dem Eingangsgrad (in-degree) und dem Ausgangsgrad (out-degree) eines Knotens v; ersterer ist die Anzahl der Kanten, die zu v inzident sind, letzterer die Anzahl der Kanten, die von v ausgehen. Der Grad eines Knotens in einem gerichteten Graphen ist die Summe aus seinem Eingangsgrad und seinem Ausgangsgrad.

Ein Pfad (path) in einem gerichteten bzw. ungerichteten Graphen von einem Knoten v₀ zu einem Knoten v_k ist eine Folge (v₀, v₁, ..., v_k) von Knoten, bei der jeweils zwei hintereinander liegende Knoten v_i und v_i+1 durch eine Kante (v_i, v_i+1) bzw. {v_i, v_i+1} verbunden sind. Die Anzahl k der Kanten des Pfades wird als dessen Länge (length) bezeichnet. Wenn es einen Pfad P von einem Knoten u zu einem Knoten v gibt, so heißt v erreichbar über P von u aus (reachable). Ein Pfad heißt einfach (simple), wenn alle Knoten darauf verschieden sind. Ein Pfad, der zum Startknoten v₀ zurückführt, d. h. v_k = v₀, und der mindestens eine Kante enthält, d. h. k > 0, heißt Zyklus. Ein Graph, der einen Zyklus enthält, heißt zyklisch.

Ein ungerichteter Graph, in dem jedes Paar von Knoten durch einen Pfad verbunden ist, heißt zusammenhängend. Ein gerichteter Graph, in dem jeder Knoten von jedem anderen aus durch einen Pfad erreichbar ist, heißt stark zusammenhängend.

I. Allg. wird mit n die Anzahl der Knoten und mit m die Anzahl der Kanten in einem Graphen bezeichnet.

Übungen

Übung 45.

In Abbildung 2.26 haben wir einen Baum kennen gelernt. Wir wir an dieser Abbildung sehen, ist jeder Baum insbesondere ein Graph; auch er besteht aus Knoten und Kanten. Tipp LEDA besitzt demgemäß keine gesonderte Klasse für Bäume, da solche immer durch die im nächsten Abschnitt vorgestellte Klasse graph verwaltet werden können. Es ist aber nicht jeder Graph auch ein Baum; ein Baum darf z. B. keinen Zyklus enthalten. Abbildung 5.3 gibt weitere Beispiele für Bäume und solche, die keine sind. Abbildung 5.3. Graph oder Baum? Arbeiten Sie genau den Unterschied zwischen einem Baum und einem Graphen aus. Unterscheiden Sie dabei zwischen dem gerichteten und dem ungerichteten Fall. Beachten Sie dabei, dass Graphen und Bäume nicht unbedingt zusammenhängend sein müssen. Definieren Sie intuitiv die Begriffe Vater, Kind, Vorfahre, Nachfahre, Wurzel, Blatt, Teilbaum, Teilgraph, Wald und Zusammenhangskomponente.

Übung 46.

Das Handshaking-Lemma besagt, dass in einem ungerichteten Graphen die Summe der Grade aller Knoten immer genau doppelt so groß ist wie die Anzahl der Kanten. Überlegen Sie sich, warum dies immer der Fall ist. Woher hat das Lemma seinen Namen? Warum gilt darüber hinaus, dass die Anzahl der Knoten mit ungeradem Grad immer gerade ist? In einem gerichteten Graphen dagegen ist die Summe aller Eingangsgrade immer gleich der Summe aller Ausgangsgrade, und beide gleich der Anzahl der Kanten. Warum gilt dies?