Definition 13.3.1 (directed graph, digraph). Ein gerichteter Graph G = 〈N,E〉, bestehend aus einer endlichen, nicht-leeren Menge N von Knoten (nodes) und einer Menge E von Kanten (edges): E ⊆ N × N.

Definition 13.3.2 (Verbindungen und Pfade). Ein Pfad ist eine endliche Folge von Knoten, welche paarweise durch Kanten verbunden sind. Z.B. 〈d,c,a,b〉.

Die Knoten n₁ und n₂ sind verbunden im Graphen G = 〈N,E〉, gdw. 〈n₁,n₂〉∈ E.

n₁ heisst Vorgänger von n₂. n₂ heisst Nachfolger von n₁.

Definition 13.3.3 (Einfacher Pfad). Ein einfacher Pfad ist ein Pfad, der einen Knoten höchstens einmal enthält.

Definition 13.3.4 (Zyklus). Ein Zyklus ist ein einfacher Pfad, an dessen Ende nochmals sein Anfangselement angefügt wird.

Zyklen der Form 〈n,n〉 heissen auch Schlaufen (loop).

Definitionsabhängig werden Schlaufen manchmal nicht als Zyklen aufgefasst.

Definition 13.3.5 (Zyklenfrei). Ein Graph, der keine Zyklen enthält, heisst zyklenfrei .

Definition 13.3.6 (Gerichteter Baum). Ein Baum ist ein zyklenfreier, gerichteter Graph mit den Eigenschaften:

• Es gibt genau einen Knoten n, der selbst keinen Vorgänger hat. Dieser Knoten heisst Wurzel .
• Jeder Knoten ausser der Wurzel hat genau einen Vorgänger .
• Von der Wurzel aus existiert ein Pfad zu jedem andern Knoten .

Definition 13.3.7 (Matrilineare Sprechweisen). Zwei Knoten sind Schwestern (Geschwister), wenn sie denselben Vorgänger (Mutter ) haben.

Definition 13.3.8 (Höhe eines Baums). Die Höhe eines Baumes bezeichnet den längsten Pfad von der Wurzel aus. Die Länge eines Pfads ist die Anzahl Knoten darin −1.

Definition 13.3.9. Ein Baum hat geordnete Knoten , wenn zwischen allen Geschwistern eine lineare Präzedenz festgelegt ist.