((()(())())((()())))
1 Intro
1.1 Bäume und Listen
1.2 Ein Wald

2 Wie funktioniert's?
2.1 Isomorphe Bäume
2.2 Pfropfen

3 Sonst was?
3.1 Bäume im Netz
3.2 Literatur
3.3 Dank

English version

© Johannes Becker

Eine Baumschule

1.1 Bäume und Listen

Eine Folge von zueinander passenden Klammern wird Liste genannt, wenn ein Klammernpaar alle anderen Klammern umfasst. Eine Liste wie die folgende

kann zu einem Busch aufgeblasen werden. Und der Busch vertrocknet dann zu einem Baum.

() ()() ()( )() ( ) ( )( ) ( )
 
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
 
O O O | \ / O O O O \|/ | O O \ / O
 
((()(())())((()())))

Natürlich kann man umgekehrt jeden Baum in eine Liste verwandeln


1.2 Ein Wald

O
()
1: [,]
O | O
(())
2: [1,1]
O O \ / O
(()())
3: [1,2]
O | O | O
((()))
4: [2,1]
O O O \|/ O
(()()())
5: [1,3]
O | O O \ / O
(()(()))
6: [1,4]
O O \ / O | O
((()()))
7: [3,1]
O | O | O | O
(((())))
8: [4,1]
O O O O \\ // O
(()()()())
9: [1,5]
O | O O O \|/ O
(()()(()))
10: [1,6]
O O \ / O O \ / O
(()(()()))
11: [1,7]
O | O | O O \ / O
(()((())))
12: [1,8]
O O | | O O \ / O
((())(()))
13: [2,4]
O O O \|/ O | O
((()()()))
14: [5,1]
O | O O \ / O | O
((()(())))
15: [6,1]
O O \ / O | O | O
(((()())))
16: [7,1]
O | O | O | O | O
((((()))))
17: [8,1]

Ok, Bäume!

2.1 Isomorphe Bäume

Der Wald im ersten Abschnitt enthält nicht alle Bäume sondern nur die, die "wirklich" verschieden sind. (Erstaunlicherweise finden das Leute interessant, die sich mit Differentialgleichungen beschäftigen.)

Die beiden folgenden Bäume

O O O O O O \ / | | \ / O O O O O O O O | \|/ \|/ | O O O O \ / \ / O O
sind nicht "wirklich" verschieden, weil man bloß ein paar Zweige verdrehen muss, um aus dem einen den anderen zu machen. Sie heißen deshalb isomorph.

Wie schafft man viele Bäume aus dem Wald, so dass im aufgeräumten Wald keine isomorphen Bäume mehr stehen?

Der Vorschlag, erst alle Bäume wachsen zu lassen und dann alle isomorphen Bäume auszureißen, wird natürlich wegen Grausamkeit strikt zurückgewiesen. Wir ziehen die Bäume deshalb durch gezieltes Propfen heran.

2.2 Pfropfen

Aus zwei Bäumen

O O \ / O
+
O O O \|/ O | O
erzeugen wir einen neuen, indem wir den linken Baum auf die unterste Gabelung des rechten Baumes pfropfen:
O O \ / O \
O O O \|/ O / O
Für die dazugehörenden Listen heißt das, dass die erste Liste am Anfang der zweiten Liste eingesetzt wird:
(()()) + ((()()())) = ((()())(()()()))
Um den ganzen gewünschten Wald aufzuforsten, muss man jetzt noch darauf aufpassen, dass man auf einen Stamm niemals einen Pfropf setzt, der größer als derjenige Teilbaum ist, der sein rechter Nachbar werden würden.

Nach dieser Regel ist das obige Pfropfen erlaubt. Aber wenn man die beiden Bäume vor dem Pfropfen vertauscht, kriegt man

O O O \|/ O | O O O \|/ 0
Dieser Baum wäre im Wald unerwünscht. (Sein Spiegelbild würde aber regelgemäß dort wachsen.)

Man braucht noch eine zusätzliche Regel: Auf den ersten und einfachsten Baum () darf jeder andere Baum gepfropft werden.

Bemerkungen

Um sich im Dschungel aller Bäume zurechtzufinden, kann man die Bäume nummerieren, indem man den dazugehörenden Listen wie folgt eine Nummer gibt:
((()(())())((()())))
11101100100111010000
Zu jeder Liste kann man auch eine Menge wie folgt betrachten
((()(())())((()())))
{{{}{{}}{}}{{{}{}}}}
und bemerken, dass isomorphe Bäume zu gleichen derartigen Mengen gehören - was erst mal nicht viel zur Herstellung des gewünschten Waldes nützt.

3.1 Bäume im Netz

Arboretum Mustila
Arboretum de Villardebelle
Arboretum Trompenburg
Arboretum Göttingen

3.2 Literatur

[1] Becker,J.: Checking Quickly the Order of a Runge-Kutta-Nyström Method for y''=f(x,y). Z. angew. Math. Mech. 71 (1991) 3, 190.
[2] Filippi,S.; Gräf,J.: Ein Programm zur Aufstellung und Überprüfung der Bedingungsgleichungen für Runge-Kutta-Nyström-Verfahren unter Verwendung der Theorie von Hairer-Wanner. Mitt. Math. Sem. Gießen 173 (1986), 42-57.

3.3 Dank

an Josef Gräf, der mir solche Bäume vorstellte.


Baum