TU Wien:Mathematik 1 UE (diverse)/Übungen SS10/Beispiel 31

Ein vollständiger Binärbaum ist ein Wurzelbaum, bei dem jeder interne Knoten genau zwei Nachfolger besitzt. Man zeige, dass ein Binärbaum mit m internen Knoten genau m + 1 Endknoten hat.

Wie viele Endknoten hat ein t-ärer Baum (t = 2,3,...) mit m internen Knoten, d.h. ein Wurzelbaum, bei dem jeder interne Knoten genau t Nachfolger besitzt? (Für t = 2 ergibt sich also ein vollständiger Binärbaum.)

Hilfreiches

Baum

Baum

Für einen Baum T gilt:

$|V(G)|=|E(G)|+1$

Lösungsvorschlag

Von jedem internen Knoten gehen $t$ Kanten weg. Das sind gleichzeitig alle Kanten, die der Baum besitzt. Die Gesamtanzahl aller Knoten ist die Summe aus internen Knoten (m) und Endknoten (n).

Es gilt daher $|E|=m\cdot t$ und $|V|=m+n$.

Für jeden Baum gilt folgendes:

${\begin{alignedat}{2}|V|&=|E|+1\\m+n&=m\cdot t+1\\n&=m\cdot t-m+1\\n&=m\cdot (t-1)+1\end{alignedat}}$

Für den Binärbaum ($t=2$) gilt $n=m\cdot (2-1)+1=m+1$.

Links

• TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel_209 (ähnliches Beispiel)