TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 310
< TU Wien:Algebra und Diskrete Mathematik UE (diverse) | Übungen SS19(Redirected from TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 310)
Jump to navigation
Jump to search
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 mnemetz[edit]
Die Anzahl aller Knoten eines Baumes
(wobei V die Knotenmenge, E die Kantenmenge ist), umfasst: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| + 1[edit]
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| = 12 = 1 + 1
n
n + 1: sei T ein Baum mit |V(T)| = n + 1Wir 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 neo[edit]
Bei einem t-ären Baum hat jeder interne Knoten t Nachfolger. D.h bei jeder Ebene des Baumes kommen
Folglich hat ein t-ärer Baum mit n internet Knoten Nachfolger.