TU Wien Diskussion:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 315

Überlegungen, die Holzweg waren

Ich überlege mir zuerst einmal, wie die Anzahl der Gesamtknoten in einem solchen Wurzelbaum aussieht.

Die Anzahl der Gesamtknoten wäre dann definiert als:

$G=t^{0}+t^{1}+t^{2}+t^{3}+...+t^{m}$

Wobei mit m die "Ebene" des Graphen gemeint ist, z.B. bei t = 3 und m gleich 3 wäre die Gesamtsumme aller Knoten $3^{0}+3^{1}+3^{2}+3^{3}=40$

Gegeben aber die Anzahl aller internen Knoten und gefragt ist die Anzahl der Endknoten.

Unschwer zu ersehen ist, dass die Zahl der Endknoten im 3-er-Beipiel $3^{4}=81$ betragen würde.

Versuchen wir es allgemeiner zu formulieren: Die Anzahl aller internen Knoten sei gegeben als

$n=\sum _{i=0}^{j}t^{j}\qquad \forall j\in \mathbb {N}$

Offensichtlich ist dann $t^{j+1}$ die Anzahl der Endknoten.

Da wir jedoch nicht die Anzahl der "Ebenen" kennen, können wir o.g. Formel nicht verwenden, oder? Oder bin ich am Holzweg?

Offensichtlich bin ich am Holzweg, Man gucke ins Skriptum, S. 33. --Mnemetz 18:24, 8. Dez 2005 (CET)

Wenn n die Knoten und e(n) die Endknoten sind, dann ergibt sich e(n) = (n+1)/2. Da binaerbaum nimmt n die Werte 1,3,5,... ein, ich kann also sagen n=1+2b, b=0,1,2,3.... Also e(1+2b) = ((1+2b) + 1)/2. Dass ist dann schon meine Induktionsvorraussetzung, Induktionbeginn ist b=0, also e(1) = (1+2)/2, passt. Induktionsbehauptung: e(1+2(b+1)) = ((1+2b) + 1)/2 + 1. Und beim Induktionsschluss stehe ich gerade auf der Leitung ... ev so: Induktionsvorraussetzung: e(2b+1) = b + 1 Induktionsbehauptung: e(2b+1+1) = b + 1 + 1, also e(2b+2) = b+2 Induktionsbegin: b=0, e(1) = 1. Passt. Induktionsschluss: Nein, stehe auf der Induktionsleitung, wie geht da der schei** schlusss???

Lg, AXEL.