alle Bäume zu n Knoten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:34 Mi 11.06.2008 | | Autor: | cofriga |
| Aufgabe | | Hallo, ich muss zu einer gegebenen Knotenzahl alle nummerierten Bäume (also nach Cayley [mm] n^{n-2} [/mm] Bäume) finden. Bei drei sind es drei bei vier 16. bei 5 125. |
Ich tüftle schon Tage, aber ich habe noch keinen guten Algorithmus gefunden, um alle Bäume (keiner doppelt, keiner fehlt) zu finden.
Kann mir jemand helfen?
Vielen Dank im Voraus
EDIT: ich habe mich verklickt bei der Dringlichkeit, denn es wäre schon schön, wenn mir jemand heute noch oder morgen helfen könnte.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:39 Mi 11.06.2008 | | Autor: | Bastiane |
Hallo cofriga!
> Hallo, ich muss zu einer gegebenen Knotenzahl alle
> nummerierten Bäume (also nach Cayley [mm]n^{n-2}[/mm] Bäume) finden.
> Bei drei sind es drei bei vier 16. bei 5 125.
> Ich tüftle schon Tage, aber ich habe noch keinen guten
> Algorithmus gefunden, um alle Bäume (keiner doppelt, keiner
> fehlt) zu finden.
Hab' nur gerade kurz nochmal rumprobiert, aber geht das nicht rekursiv? Also wenn du alle für 3 Knoten hast, gibt es dann nicht für jeden diesen mehrere, wenn ein vierter Knoten hinzukommt? Allerdings scheint es dann teilweise welche doppelt zu geben, da müsste man dann evtl. noch vergleichen. Weiß nicht, ob dir das hilft, aber das fiel mir gerade so spontan ein...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:49 Mi 11.06.2008 | | Autor: | cofriga |
Ja das habe ich durchaus schon versucht, aber ich denke ich werde es jetzt einfach so machen, dass ich die zusammenhängenden graphen konstruiere und dann einfach alle zyklischen graphen weglasse, dann müßte auch die richtige lösungsmenge rauskommen. die idee hatte ich gerade ;)
vielen dank für die schnelle antwort.
falls jemand einfällt, dass mein weg falsch ist, bitte melden ;)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Fr 13.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
