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

Ein t-ärer Baum () 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)Edit

Siehe Diskussion:Beispiel_209

Lösungsvorschlag von mnemetzEdit

Die Anzahl aller Knoten eines Baumes   (wobei V die Knotenmenge, E die Kantenmenge ist), umfasst:

 , m ... innere Knoten, x ... Endknoten

Für jeden endlichen Baum   gilt:

 

Somit können wir sagen:

 

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:

 
 

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

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   2 = 1 + 1
  

n   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   ist wieder ein Baum.

|V \ { }| = n   |V( )| = |E( )| - laut Induktionsvorraussetzung

|V \ { }| = |E \ { }| + 1

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

|V| = |E| + 1 QED

Lösungsvorschlag von neoEdit

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

 
Folglich hat ein t-ärer Baum mit n internet Knoten   Nachfolger.