[informatik-bonn] Info Blatt 4 Aufgabe 2
- From: "Markus Dunkel" <markusdunkel@xxxxxxxxxx>
- To: <informatik-bonn@xxxxxxxxxxxxx>
- Date: Sat, 8 Feb 2003 22:29:36 +0100
\section*{Aufgabe 2}
\subsection*{a)}
Also, die untere Abschätzung hab ich jetzt bewiesen, aber die obere krieg
ich irgendwie nicht hin.
Mein Ansatz für die obere Abschätzung:
Sei v(T) die Anzahl der inneren Knoten.
Die Anzahl der inneren Knoten in T ist maximal, wenn die Wurzel genau k
Söhne und jeder andere innere Knoten genau 2k-1 Söhne hat.
\leftarrow v(T) \leq 1+k \cdot \sum_{i=0}^{h-2} {(2k-1)^i}
[Die 1 ist die Wurzel und in der Ebene h-1 - von den Söhnen der Wurzel aus
gesehen - stehen nur die Blätter]
Wollte dann mit vollst. Induktion die Gleichheit mit der auf dem Blatt
angegebenen Formel zeigen. Ging schon bei der Induktionsverankerung
schief...
Wo liegt der Fehler?
Danke schonmal.
Markus
Other related posts:
