|
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 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.
WALD sei die Menge aller Bäume.
|
|
|
Das bedeutet: Ein Baum wird ohne Numerierung der Knoten dargestellt. Die numerierten Bäume einer bestimmten Äquivalenzklasse werden durch denselben Graphen dargestellt, unterscheiden sich aber in der Numerierung der Knoten. |