Ein (endlicher) gerichteter Graph G ist ein Paar G=< K,E > aus einer endlichen Menge von Knoten K und einer Relation E⊂K×K, den Kanten.
Beispiel: E= {< a,b >,< b,c >,< c,d >,< b,b >}, K= {a,b,c,d}.
Ein Pfad der Länge n in einem Graphen ist eine Folge von Knoten ki, so dass < ki,ki+1 >∈E für alle 1 ≤i < n (es werden also n+ 1 Knoten besucht).
Ein Pfad der Länge n heißt Zyklus, wenn k1 = kn.
Statt < ki,kj >∈E schreibt man auch ki →kj.
Ein Baum ist ein Graph mit
- Genau ein Knoten hat keinen Vorgänger, der Wurzelknoten
- Alle anderen Knoten haben genau einen Vorgänger
- In einem Baum existieren keine Zyklen
Üblicherweise fordert man noch eine Ordnung auf der Menge {< ki,kj >} der Kanten ab einem gegebenen Knoten ki .
Knoten ohne Nachfolger heißen Blätter.
