Bäume
Von: , Frage gestellt am Do, 3. Jun 2004
Hallo, mein Problem ist folgendes:
Wie viele Bäume lassen sich aus einem gegebenen Baum vom Grad m und mit n Knoten durch Anhängen eines neuen Knotens erzeugen?
Danke und Gruß
5 Antworten zu dieser Frage
-
Antwort von nach 4 Minuten 0 hilfreich
Idee
Mir fällt grad was ein:
(n-1)+m .... könnte sein oder? ;) [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
-
Antwort von nach 7 Stunden 0 hilfreich
Re: Bäume
Hallo,
ist der Baum vollständig und können gestaltlich gleiche (isomorphe) Bäume ignoriert werden ?
Gruss
Enno
-
Antwort von nach 12 Stunden 0 hilfreich
Re^2: Bäume
Hi Enno,
meines Wissen muss der Baum nicht vollständig sein.
Aber ich habe eine Lösung gefunden, die sich auch per Induktion beweisen läßt:
n(m-1)+1 [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
-
Antwort von nach 12 Stunden 0 hilfreich
Re^3: Bäume
Hallo,
nimm mal n=1 (der Baum, der nur aus der Wurzel besteht - ist das bei Euch ein zulässiger Baum ?) und z.B. m=5. Nach Deiner Formel lassen sich 5 neue Bäume bilden. Ist das beabsichtigt, d.h. wird bei dem Baum gewissermaßen vermerkt, das wievielte Kind der neue Knoten ist ? Dann wäre es ja sinnvoll die Bäume zu unterscheiden - ansonsten würde ich genau eine Möglichkeit sehen.
Gruss
Enno
-
-
-
Antwort von nach 5 Tagen 0 hilfreich
Re: Bäume
Hallo,
bei einem Baum gehe ich mal davon aus, daß rechts und links nicht vertauscht werden können.
Ein Baum der Tiefe t kann maximal 2^t viele Blätter haben.
Und dann hat man 2^t viele Möglichkeiten, an ein Blatt einen Knoten
zu hängen, der dann selbst zum Blatt wird.
Und damit wären es bei einem vollständigen Baum 2^t viele neue Bäume
- wenn man die anderen Ebenen nicht beachtet.
Falls man links und rechts vertauschen darf, ist vielleicht nur
noch die Tiefe interessant, weil wenn man in einer Ebene einen
Knoten einfügt, kann man durch Permutation alle anderen Bäume,
die in dieser Ebene einen neuen Knoten haben, erzeugen.
Und in dem Fall tippe ich mal, daß es dann nur t (oder t-1) viele
neue Bäume gibt.
Gruß
Thorsten