Anzahl von Bäumen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 17:12 Mo 10.12.2007 | | Autor: | Norman |
| Aufgabe | Seien a, b e N mit a [mm] \le [/mm] b. Geben Sie in Abhängigkeit von der Knotenzahl n exakte
obere und untere Schranken für die Höhe und die Anzahl der Blätter von Bäumen
an, deren innere Knoten mindestens a und höchstens b Kinder haben. |
Ich habe Probleme damit die Anzahl der Knoten in abhängigkeit von a, b zu bestimmen.
Es ist ja klar das wenn ich n Knoten habe die maximale höhe n-1 sein muss, da die Wurzel die höhe null hat.
Im schlechtesten Fall habe ich die Höhe 1 , weil ich alles an die Wurzel anhänge. Bei der Anzahl der Blätter ist es ja so das ich bei n Knoten im bestem fall n-1 Blätter habe, weil ich wiederrum alles an die Wurzel hänge und im schlechtesten Fall 1 Blatt da ich an jeden Knoten einen neuen hänge.
Aber wie kann ich das denn in abhängigkeit von a,b machen?
In abhängigkeit von einer der beiden wäre es ja schon etwas einfacher. Da ich bei z.B. n = 6 und b = 3 .
An die Wurzel hänge ich 3 ran und habe dann noch 2. Diese hänge ich wieder an eine der Knoten und habe somit die Höhe 2. Wenn aber a=b ist es in dem Beispiel ja nicht möglich diesen Baum zu konstruieren. Muss ich diese Fälle weglassen?
Vielleicht kann mir ja jemand einen Gedankenanschub geben.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:57 Mi 12.12.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
