[informatik-bonn] Re: Info Blatt 4 Aufgabe 2
- From: Sebastian Bothe <sbothe@xxxxxx>
- To: informatik-bonn@xxxxxxxxxxxxx
- Date: Sat, 8 Feb 2003 22:51:41 +0100
Hallo Markus,
also Deine Abschätzung geht glaube ich schief, weil Du für die Wurzel nur k
Söhne als Maximum angenommen hast. Die Wurzel ist aber insbesondere ein
innerer Knoten und die haben alle maximal 2k-1 Söhne..
Davon ausgehend bekomme ich für die maximale Zahl auf:
$$ v_max(T)=1+\sum_{i=1}^{h-1} (2k-1)^i $$
Damit ist die Induktion dann glaube ich nicht mehr besonders schwer.. Hoffe
das hilft weiter..
Gruß
Sebastian
On Saturday 08 February 2003 22:29, you wrote:
> \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:
