TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 317

Ein t-ärer Baum ($t\in \mathbb{N},t\ge 2$) ist ein ebener Wurzelbaum, bei dem jeder Knoten entweder 0 Nachfolger (Endknoten) oder genau t Nachfolger (interner Knoten) hat. Für t = 2 ergeben sich also genau die Binärbäume. Wieviele Endknoten hat ein t-ärer Baum mit n internen Knoten?

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Überlegungen von mnemetz (war Holzweg)

Siehe Diskussion:Beispiel_209

Lösungsvorschlag von mnemetz

Die Anzahl aller Knoten eines Baumes $T=⟨V,E⟩$ (wobei V die Knotenmenge, E die Kantenmenge ist), umfasst:

$|V|=m+x$, m ... innere Knoten, x ... Endknoten

Für jeden endlichen Baum $T=⟨V,E⟩$ gilt:

$|V|=|E|+1$

Somit können wir sagen:

$|V|=|E|+1=t\ast m+1$

Begründung: von jedem inneren Knoten führen t Kanten weg. 1 steht für den Startknoten (Wurzelknoten).

Somit ergibt sich, wenn ich nun gleichsetze:

$m+x=t\ast m+1$ $x=t\ast m-m+1=m\ast (t-1)+1$

Ergänzung: Beweis für |V| = |E| + 1

Siehe auch Skriptum, S.32

Beweis durch vollständige Induktion nach |V| = n.

  n = 1       |V| = 1 = |E| + 1 = 0 + 1
  n = 2       |V| = 2, |E| = 1 $\Rightarrow$ 2 = 1 + 1
  

n $\to$ n + 1: sei T ein Baum mit |V(T)| = n + 1

Wir entfernen einen Endknoten (Knoten v mit d(v) =1; existiert stets!) samit zugehöriger Kante $e_1,T_1=⟨V\mathrm{\setminus }\{v_1\},E\mathrm{\setminus }\{e_1\}⟩$ ist wieder ein Baum.

|V \ {$v_1$}| = n $\Rightarrow$ |V($T_1$)| = |E($T_1$)| - laut Induktionsvorraussetzung

|V \ {$v_1$}| = |E \ {$e_1$}| + 1

|V| - 1 = |E| - 1 + 1

|V| = |E| + 1 QED

Lösungsvorschlag von neo

Bei einem t-ären Baum hat jeder interne Knoten t Nachfolger. D.h bei jeder Ebene des Baumes kommen $t^k$ (k sei in dem Fall die Tiefe des Baumes) Knoten dazu. Also $t^0=1,t^1=t,t^2=t\ast t\mathrm{...},t^k$. Dabei ist die null-te Ebene, also $t^0=1$ der Wurzelknoten. Aus dieser Überlegung folgt, dass n eine Potenz von t sein muss, da es n interne Knoten gibt ($\to n=t^k$). Auf der nächsthöheren Ebene, also bei der k+1. Ebene muss es $t^k\ast t=t^{k+1}$ Knoten geben. Da die Variable $k$ nicht gegeben ist, hab ich ein wenig umformen müssen.

$n=t^k\to lo{g}_t(n)=k\to t^{k+1}=t^{lo{g}_t(n)+1}$
Folglich hat ein t-ärer Baum mit n internet Knoten $t^{lo{g}_t(n)+1}$ Nachfolger.