Graphentheorie

Ein gerichteter Graph ist ein Paar (N, E), wobei

– N eine Menge von Knoten (nodes) und – E eine Menge von Kanten (edges) ist mit

E = {(x, y) | x, y ∈ N}, d.h. E ist eine Teilmenge aus N2

Wir schreiben x E y, gdw. eine gerichtete Kante (x, y) von einem Knoten x zu einem Knoten y verläuft.

Ein Wald ist ein Graph, für den folgendes gilt:

– Aus x E z und y E z folgt, dass x = y. („E ist aufwärts eindeutig“)

Abwärtige Eindeutigkeit ist idR. jedoch nicht gegeben, denn es darf x E y und x E z sein auch wenn z ≠ y.

Ein Wald ist ein Baum, falls es einen Knoten r gibt

mit r E+ x für alle x verschieden von r.

Bezeichnungen für Knoten:

• –  y heißt Kind von x, wenn x E y

• –  y heißt Elter von x, wenn y E x – y heißt Nachfahre von x, wenn x E+ y. – y heißt Vorfahre von x, wenn y E+ x.

Es sei F eine Menge von Farben.

Wir nennen eine Kantenfärbung mit Farben w aus F eine Funktion f: E → F. x ∈ E hat die Farbe w, falls f(x) = w.

Entsprechend nennen wir eine Knotenfärbung (mit Farben aus F) eine Funktion f : N → F. x ∈ N hat die Farbe w, falls f(x) = w.