Nyström-Bäume
BNy ist die Menge aller Nyström-Bäume. Das spezielle Symbol 
möge fürderhin die Rolle eines Buchstabens spielen, ähnlich wie der
Buchstabe t in der Formulierung:
"Es sei t  B " .
Es sei 
BNy .
Dann ist o()
die Ordnung von ,
d.h. die Anzahl aller Knoten.
|
|
Ein numerierter Nyström-Baum
ist ein numerierter Baum zusammen mit der Unterscheidung seiner Knoten in dicke und dünne, so daß 1. die Wurzel stets dünn ist, 2. ein Dünner keine Verzweigungen hat, 3. der Nachfolger eines Dünnen dick ist. 
Im Beispiel links sind die Knoten 2, 8 und 9 dick und alle anderen dünn. |
|
|
Ein Nyström-Baum ist eine Äquivalenz-
klasse numerierter Nyström-Bäume.
Zwei numerierte Nyström-Bäume heißen äquivalent (oder "isomorph"), wenn sie äquivalente numerierte Bäume sind und die dicken und dünnen Knoten sich an denselben Stellen befinden. |
|
|
Beispiel 1: Identische numerierte Nyström-Bäume |
|
Die beiden graphischen Symbole rechts
stellen ein und denselben numerierten
Nyström-Baum dar.
Die Numerierung ist dieselbe, nur die Teilbäume, die aus dem dicken Knoten 2 herauswachsen, sind vertauscht. Für die graphische Darstellung eines numerierten Nyström-Baumes spielt es keine Rolle, in welcher Reihenfolge man die aus einem dicken Knoten herauswachsenden numerierten Teilbäume auf das Papier zeichnet. |
|
|
Beispiel 2: Verschiedene numerierte Nyström-Bäume einer Äquivalenzklasse |
|
Rechts sind drei verschiedene numerierte
Nyström-Bäume dargestellt, die alle derselben
Aquivalenzklasse (ganz rechts) angehören.
Diese Äquivalenzklasse ist per definitionem ein Nyström-Baum. Der Nyström-Baum macht sozusagen die "Struktur" sichtbar. |
|