Weitere Termini

Zu jedem Knoten v sind alle in- und out-Kanten als orientierte Kanten in einer Sequenz  $\Lambda(v)$angeordnet, die im folgenden als Folge der zum Knoten v inzidenten Kanten bezeichnet wird. In dieser Folge erscheinen in-Kanten mit der Orientierung in, out-Kanten mit der Orientierung out, also normalisiert. Schlingen treten doppelt, nämlich in beiden Orientierungen auf. Für jede  orientierte Kante $\vec e$ aus $\Lambda(v)$gilt $this(\vec e)=v$.

Formal ergibt sich für die Funktion $\Lambda$ die Signatur $\Lambda: V \tfun \seq (E\cross Dir)$. Bei gerichteten Graphen enthält $\Lambda(v)$ die Teilfolge aller in-Kanten $\Lambda^-(v)$ und die Teilfolge aller out-Kanten $\Lambda^+(v)$. Auch diese Folgen können mit den vom Labor definierten Makros  G_forAllIncidentEdges,  G_forAllInEdges und  G_forAllOutEdges durchlaufen werden. Ferner ist die Reihenfolge der Elemente der Sequenz $\Lambda(v)$ durch Laborfunktionen beeinflußbar.

Unter dem  Grad  $\delta(v)$ eines Knotens v versteht man die Anzahl der zum Knoten v  inzidenten Kanten: $\delta(v) = \vert \Lambda(v)\vert$. Für gerichtete Graphen definiert man analog noch den  Innengrad  $\delta^-(v)$ und  Außengrad  $\delta^+(v)$ eines Knoten v mittels $\delta^-(v)=\vert\Lambda^-(v)\vert$ und $\delta^+(v)=\vert\Lambda^+(v)\vert$.