Gerichtete Graphen

  Ein  gerichteter Graph (kurz auch nur  Graph) umfaßt eine endliche Menge von  Knoten V und eine endliche Menge von  gerichteten Kanten (kurz auch nur  Kanten) E. Dabei verbindet jede  Kante $e\in E$ genau einen  Anfangsknoten (oder  Startknoten) $v\in V$ mit genau einem  Endknoten (oder  Zielknoten) $w\in V$. Man sagt auch, Kante e führt von Knoten v nach Knoten w. Falls v=w gilt, heißt e auch  Schlinge.

Die Beziehungen zwischen Kanten und ihren Anfangs- und Endknoten werden durch die Funktionen  $\alpha:E\tfun V$ und  $\omega:E\tfun V$ ausgedrückt. $\alpha(e)$ ist der Anfangsknoten der Kante e, $\omega(e)$ der Endknoten. Zwei verschiedene Kanten dürfen durchaus denselben Anfangs- und denselben Endknoten haben und werden dann als  Mehrfachkanten bezeichnet.

Eine Kante e heißt  inzident zu einem Knoten v, wenn v Anfangs- oder Endknoten dieser Kante ist. Eine Kante, deren Anfangsknoten bzw. Endknoten ein Knoten v ist, heißt auch  out-Kante bzw.  in-Kante bezüglich Knoten v. Ein Knoten, der weder Anfangsknoten noch Endknoten irgendeiner Kante ist, heißt  isoliert. Ein Graph kann wie in Abbildung graphisch dargestellt werden.

  

Abbildung: Ein Beispielgraph

Die Knotenmenge V ist hier $\{\textit{v1},\textit{v2},\textit{v3},\textit{v4}\}$, die Kantenmenge E ist $\{\textit{e1},\textit{e2},\textit{e3},\textit{e4}, \textit{e5},\textit{e6},\textit{e7}\}$. Kanten $\textit{e2}$ und $\textit{e3}$ sind Mehrfachkanten, Kanten $\textit{e1}$ und $\textit{e7}$ sind Schlingen. Knoten $\textit{v3}$ ist isoliert. Die Funktionen $\alpha$ und $\omega$ sind in Tabelle dargestellt.

 

e1 e2 e3 e4 e5 e6 e7

$$\alpha$$ v1 v1 v1 v2 v4 v4 v4

$$\omega$$ v1 v2 v2 v1 v1 v2 v4

Das Graphenlabor repräsentiert die Menge aller Knoten und die Menge aller Kanten als (injektive) Folgen. Vseq bezeichnet die Folge aller Knoten, Eseq die Folge aller Kanten. Diese Folgen können mittels der Makros  G_forAllVertices und  G_forAllEdges durchlaufen werden. Die Reihenfolge, in der das Labor die Werte zurückliefert, ist durch das Programm beeinflußbar. Weitere Details findet man bei den Beispielen in Abschnitt und unter der Beschreibung der Methoden in Abschnitt.

Den Knoten und Kanten werden eindeutige natürliche Zahlen als Identifikationsnummern zugeordnet. Diese werden evtl. nach dem Löschen eines Knotens oder einer Kante für andere, neu erzeugte Knoten oder Kanten wiederverwendet. Zur Identifikation von Knoten und Kanten werden Variablen verwendet.