gerichteter Graph
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.
Wald
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.
azyklischer Graph
Baum
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.
Färbung
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.
Last changed3 months ago