Prolog:

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.


© 11. August 2000, Josef Gräf, Prolog