Ermittlung des Prüfer-Codes des gegebenen Baumes:
Entferne das Blatt mit der kleinsten Beschriftung und nimm die Beschriftung seines Nachbarn in den Prüfer-Code auf. Wiederhole dies solange, bis nur noch 2 Blätter übrig sind.
Das Blatt mit der kleinsten Beschriftung ist das Blatt 2. Sein Nachbar hat die Beschriftung 8. Also:
Entferne Blatt 2 und schreibe 8 in den Prüfer-Code:
Prüfer-Code: 8, ...
Entferne das nun kleinste Blatt 4 und schreibe seinen Nachbarn 1 in den Prüfer-Code:
Prüfer-Code: 8, 1, ...
Entferne das nun kleinste Blatt 5 und schreibe seinen Nachbarn 1 in den Prüfer-Code:
Prüfer-Code: 8, 1, 1, ...
Setze fort, bis es nur noch zwei Blätter gibt. Man erhält den
Prüfer-Code: 8 , 1, 1, 3, 1, 3, 7
Der umgekehrte Weg (Prüfer-Code -> Baum) folgt morgen früh :-)
EDIT: Hier der versprochene umgekehrte Weg:
1) Schreibe den Prüfer-Code horizontal hin und darunter eine weitere noch leere Liste B:
P: 2 3 3 7 2 5 3
B:
2) Suche die kleinste Zahl, die weder in P noch in B auftritt (das ist vorliegend die 1) und schreibe sie in die Liste B:
P: 2 3 3 7 2 5 3
B: 1
Für das Baumdiagramm bedeutet das, dass die Knoten 1 und 2 miteinander verbunden sind. Zeichne dies in dein Baumdiagramm:
3 ) Streiche die "verbrauchte" 2 aus der Liste P (ich ersetze sie durch ein "-" ) :
P: - 3 3 7 2 5 3
B: 1
Suche nun wieder die kleinste Zahl, die weder in P noch in B auftritt (vorliegend die 4) und schreibe sie in die Liste B:
P: - 3 3 7 2 5 3
B: 1 4
Für das Baumdiagramm bedeutet das, dass die Knoten 3 und 4 miteinander verbunden sind. Zeichne dies in dein Baumdiagramm:
4 ) Streiche die "verbrauchte" 3 aus der Liste P:
P: - - 3 7 2 5 3
B: 1 4
Suche nun wieder die kleinste Zahl, die weder in P noch in B auftritt (vorliegend die 6) und schreibe sie in die Liste B:
P: - - 3 7 2 5 3
B: 1 4 6
Für das Baumdiagramm bedeutet das, dass die Knoten 3 und 6 miteinander verbunden sind. Zeichne dies in dein Baumdiagramm:
5 ) Streiche die "verbrauchte" 3 aus der Liste P:
P: - - - 7 2 5 3
B: 1 4 6
Suche nun wieder die kleinste Zahl, die weder in P noch in B auftritt (vorliegend die 8) und schreibe sie in die Liste B:
P: - - - 7 2 5 3
B: 1 4 6 8
Für das Baumdiagramm bedeutet das, dass die Knoten 7 und 8 miteinander verbunden sind. Zeichne dies in dein Baumdiagramm:
6 ) Streiche die "verbrauchte" 7 aus der Liste P:
P: - - - - 2 5 3
B: 1 4 6 8
Suche nun wieder die kleinste Zahl, die weder in P noch in B auftritt (vorliegend die 7) und schreibe sie in die Liste B:
P: - - - - 2 5 3
B: 1 4 6 8 7
Für das Baumdiagramm bedeutet das, dass die Knoten 2 und 7 miteinander verbunden sind. Zeichne dies in dein Baumdiagramm:
7 ) Streiche die "verbrauchte" 2 aus der Liste P:
P: - - - - - 5 3
B: 1 4 6 8 7
Suche nun wieder die kleinste Zahl, die weder in P noch in B auftritt (vorliegend die 2) und schreibe sie in die Liste B:
P: - - - - - 5 3
B: 1 4 6 8 7 2
Für das Baumdiagramm bedeutet das, dass die Knoten 2 und 5 miteinander verbunden sind. Zeichne dies in dein Baumdiagramm:
7 ) Streiche die "verbrauchte" 5 aus der Liste P:
P: - - - - - - 3
B: 1 4 6 8 7 2
Suche nun wieder die kleinste Zahl, die weder in P noch in B auftritt (vorliegend die 5) und schreibe sie in die Liste B:
P: - - - - - - 3
B: 1 4 6 8 7 2 5
Für das Baumdiagramm bedeutet das, dass die Knoten 3 und 5 miteinander verbunden sind. Zeichne dies in dein Baumdiagramm:
8) Nun ist die Liste P erschöpft. Im Baumdiagramm fehlt noch der Knoten 9. Dieser ist mit dem letzten noch verbliebenen Knoten in der Liste P, vorliegend also mit der 3 verbunden. Zeichne dies in dein Baumdiagramm:
Damit ist das Baumdiagramm fertig.
