0 Daumen
295 Aufrufe

Aufgabe:

Bestimmen Sie im Baum mit Prüferkode (2 , 3, 1, 5, 3, 3) alle Nachbarn der Ecke 3.

von

1 Antwort

0 Daumen

Hallo Alex,

der Prüfer-Code ist doch hier ganz gut erklärt. Die Tabelle für die Reproduktion des Baums entwickelt sich wie folgt: die kleinste Zahl, die nicht in der Liste vorkommt, ist die \(4\) - also:$$\begin{array}{} 2& 3& 1& 5& 3& 3 \\ \hline 4 \end{array}$$daraufhin wird die Zahl, die über der \(4\) steht, durchgestrichen. Und da die \(2\) jetzt nicht mehr auftaucht, ist sie die nächste kleinste Zahl

$$\begin{array}{} \cancel 2 & 3& 1& 5& 3& 3 \\ \hline 4& 2 \end{array}$$Wir streichen wieder die Zahl darüber - die \(3\) - und die nächst kleinere Zahl, die nicht mehr in der Tabelle steht, wäre die \(6\):

$$\begin{array}{} \cancel 2 & \cancel 3& 1& 5& 3& 3 \\ \hline 4& 2& 6 \end{array}$$Die \(1\) über der \(6\) wird wieder gestrichen, und da sie \(1\) damit aus der Tabelle verschwunden ist, taucht sie unter der \(5\) wieder auf; usw.:

$$\begin{array}{} \cancel 2 & \cancel 3& \cancel 1& \cancel 5& \cancel 3& 3 \\ \hline 4& 2& 6& 1& 5& 7 \end{array}$$ Für den letzten Schritt (die 8.Ecke) werden die beiden Zahlen, die nicht in der zweiten Zeile stehen - also die 3 und die 8 - mit einer Kante verbunden.

Die Nachbarn der Ecke \(3\) sind die Knoten, deren Nummern über oder unter der \(3\) stehen und die nicht enthaltene 8. Also die Knoten 2, 5, 7 und 8.

und so sieht der Graph aus:

blob.png   

von 45 k

Korrektur: hatte die 8.Ecke nicht berücksichtigt

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community