Graph/Baum < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei A ein Baum mit Wurzel, bei dem die Kanten von der Wurzel zu den Blättern gerichtet sind. So ein Baum heißt q-närer Baum, wenn von jedem inneren Knoten genau q Kanten abgeben. Berechne die Anzahl i von inneren Knoten. Was ist die Anzahl a der Blätter in einem q-nären Baum mit ingesamt n Knoten? |
Hallo,
bei der Aufgabe habe ich keinen blassen Schimmer.
Was ich mir für die Blätter a überlegt habe:
Blätter a = [mm] q^{h}
[/mm]
h soll die Höhe sein. Ich weiß aber nicht , wie man die Höhe berechnen soll.
Könnte mir jemand bitte einen Ansatz geben ?
Vielen Dank im Voraus.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:56 Mo 20.01.2014 | | Autor: | felixf |
Moin!
> Sei A ein Baum mit Wurzel, bei dem die Kanten von der
> Wurzel zu den Blättern gerichtet sind. So ein Baum heißt
> q-närer Baum, wenn von jedem inneren Knoten genau q Kanten
> abgeben. Berechne die Anzahl i von inneren Knoten. Was ist
> die Anzahl a der Blätter in einem q-nären Baum mit
> ingesamt n Knoten?
Geht es hier um einen vollen Baum, also einem Baum bei dem alle Blaetter den gleichen Abstand von der Wurzel haben? Du scheinst davon auszugehen.
Wenn dem nicht so ist, dann ist die Aufgabenstellung so nicht komplett.
> h soll die Höhe sein. Ich weiß aber nicht , wie man die
> Höhe berechnen soll.
Wieso willst du die denn berechnen? Und vor allem: woraus?
Was genau ist gegeben?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:35 Mo 20.01.2014 | | Autor: | pc_doctor |
Hallo,
das war die komplette Aufgabenstellung. Soll.wohl ein vollständiger Baum sein. Mehr als diese Informationen in der Aufgabenatellung ist leider nicht gegeben.
|
|
|
| |
|
> Hallo,
> das war die komplette Aufgabenstellung. Soll wohl ein
> vollständiger Baum sein. Mehr als diese Informationen in
> der Aufgabenatellung ist leider nicht gegeben.
Hallo pc_doctor,
kann es sein, dass das Phänomen unvollständiger
oder sonst nicht ganz klarer Aufgabenstellungen
da, wo du lernst, ein wiederkehrendes ist ?
LG , Al-Chw.
https://matheraum.de/read?i=1005234
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:42 Di 21.01.2014 | | Autor: | pc_doctor |
Hallo Al,
also die Aufgabe , die ich gepostet hatte , war die komplette. Als Voraussetzung ist IMMER ein ungerichteter zusammenhängender Baum ohne Kreise.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:38 Di 21.01.2014 | | Autor: | felixf |
Moin,
> Sei A ein Baum mit Wurzel, bei dem die Kanten von der
> Wurzel zu den Blättern gerichtet sind. So ein Baum heißt
> q-närer Baum, wenn von jedem inneren Knoten genau q Kanten
> abgeben. Berechne die Anzahl i von inneren Knoten. Was ist
> die Anzahl a der Blätter in einem q-nären Baum mit
> ingesamt n Knoten?
diese Aufgabenstellung inkl. einer Loesung kann man uebrigens recht leicht ueber Google finden. Man muss nur beachten, dass die Variablen mal anders heissen koennen.
Der Loesung kann man entnehmen, dass gemeint ist, $i$ und $a$ in Abhaengigkeit von $n$ zu bestimmen.
Das ist jetzt schonmal etwas konkreter. Und apropos, die Wurzel zaehlt auch als innerer Knoten. Jeder Knoten ist also entweder ein Blatt oder ein innerer Knoten.
Und nun noch ein Tipp: du musst eine Beziehung zwischen $n$, $i$ und $q$ herstellen. Weiterhin eine zwischen $N$, $i$ und $a$. Damit kannst du $i$ und $q$ durch $a$ durch $n$ und $q$ darstellen.
LG Felix
|
|
|
|
