|
Ein numerierter Baum der Ordnung n
ist eine Abbildung t : {2 , . . . , n} --> {1 , . . . , n}, so daß t(i) < i (i = 2 , . . . , n). o(t) sei die Ordnung von t. NB sei die Menge aller numerierten Bäume. Der Knoten mit der Nummer 1 heißt Wurzel. |
a.) Zwei numerierte Bäume t, u NB heißen äquivalent:
t ~ u, wenn gilt: 1. o(t) = o(u) 2. Es gibt eine Permutation s der Zahlen 1 , . . . , o(t), so daß s(1) = 1 und t(i) = s u s-1(i) (i = 2 , . . . , o(t)). b.) Ein Baum ist eine Äquivalenzklasse numerierter Bäume. B sei die Menge aller Bäume. |
Für die graphische Darstellung bedeutet dies: Ein Baum hat keine Numerierung der Knoten. |