0 Daumen
3,6k Aufrufe

hallo, 

vielleicht kann mir ja hier jemand weiterhelfen...

gesucht ist der prüfercode für folgenden baum:

 

d

 

als zusatz soll der baum mit folgendem code gezeichnet werden: 2 3 3 7 2 5 3

 

hat jemand eine ahnung wie das geht?? ich wäre seeeehr dankbar!!

von
Hast du genauere Angaben dazu, wie ihr eure Graphen codieren sollt?

Vielleicht hilft auch ein Beispiel mit Code und zugehörigem Graph.
ein beispiel nicht..gefragt ist  nur nach einem "prüfer-code"

3 Antworten

+2 Daumen
 
Beste Antwort

hallo

 

zusatz:

 

erklärende worte zum zusatz findest du hier:

von
+2 Daumen

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:

Baum mit 2 Knoten

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:

Baum mit 4 Knoten

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:

Baum mit 5 Knoten

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:

Baum mit 7 Knoten

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:

Ergänzter Baum mit 7 Knoten

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:

Baum mit 8 Knoten

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:

Ergänzter Baum mit 8 Knoten

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:

Fertiger Baum mit 9 Knoten

Damit ist das Baumdiagramm fertig.

von
+1 Daumen
Wenn ich das bei http://de.wikipedia.org/wiki/Prüfer-Code nun richtig verstehe:

ist der Prüfer-Code hier: 2 4 5 6 8 1 73

Stimmt nicht!  2 4 5 6 8 1 7 3 ist die Reihenfolge in der die Blätter weggehen.

Man muss jeweils die 'Blattwurzel' angeben.

Daher 8113137

Jetzt kannst du die umgekehrte Aufgabe vermutlich auch.
von
Am Schluss des Prüfer Codes muss es 3 7 heißen.

Ein Versuch für den Zusatz:

Die korrigierte Variante:

Zum Schluss bleibt hier 3-9 übrig.

@JotEs: Besten Dank!
Schadet bestimmt nicht, wenn du die Zusatzfrage auch noch kontrollierst. ;)
Gerne: Die korrigierte Variante ist korrekt (jedenfalls entspricht sie meinem Ergebnis und auch dem von gorgar).

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community