TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 310

Aus VoWi
Zur Navigation springen Zur Suche springen

Ein t-ärer Baum (t \in \mathbb{N}, t \geq 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?

Überlegungen von mnemetz (war Holzweg)[Bearbeiten]

Siehe Diskussion:Beispiel_209

Lösungsvorschlag von mnemetz[Bearbeiten]

Die Anzahl aller Knoten eines Baumes T = \langle V,E \rangle (wobei V die Knotenmengem E die Kantenmenge ist), umfasst:

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

Für jeden endlichen Baum T = \langle V,E \rangle gilt:

|V| = |E| + 1

Somit können wir sagen:

|V| = |E| + 1 = t*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*m + 1
x = t*m - m + 1 = m*(t-1) + 1

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

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 \rightarrow 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 = \langle V \backslash \{v_1\}, E \backslash \{e_1\}\rangle 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