Haus vom Nikolaus: Gerüste < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:47 Do 07.01.2010 | | Autor: | sl1m |
| Aufgabe | | Wie viele nicht isomorphe Spannbäume besitzt das Haus vom Nikolaus ? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo allerseits.
Ich bräuchte hier mal einen Tipp )
Satz von Cayley besagt, dass die Anzahl der Gerüste eines vollständigen(!) Graphen gleich [mm] $n^{n-2}$ [/mm] ist. Aber das Haus vom Nikolaus ist leider kein vollständiger Graph. Wie kann ich hier vorgehen ?
Danke im Voraus
|
|
| |
|
> Wie viele nicht isomorphe Spannbäume besitzt das Haus vom
> Nikolaus ?
> Satz von Cayley besagt, dass die Anzahl der Gerüste eines
> vollständigen(!) Graphen gleich [mm]n^{n-2}[/mm] ist. Aber das Haus
> vom Nikolaus ist leider kein vollständiger Graph. Wie kann
> ich hier vorgehen ?
Hallo sl1m,
zuerst sollte klar werden, welcher Graph mit dem
"Haus vom Nikolaus" genau gemeint ist. Ich habe
z.B. folgende Darstellungen gefunden:
![[]](/images/popup.gif) Version 1 Version 2
Soll der Graph also 5 Ecken und 8 Kanten oder
vielleicht 6 Ecken und 10 Kanten haben ?
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:26 Fr 08.01.2010 | | Autor: | sl1m |
die Frage bezieht sich auf dei "Haus vom Nikolaus" der ersten Version :) also 5 ecken.
Danke für die Antwort
|
|
|
| |
|
> die Frage bezieht sich auf dei "Haus vom Nikolaus" der
> ersten Version :) also 5 ecken.
... dann gibt es aber wirklich nur gaaanz wenige
nicht isomorphe Spannbäume bzw. Gerüste !
LG
|
|
|
| |
|
> Wie viele nicht isomorphe Spannbäume besitzt das Haus vom
> Nikolaus ?
> Satz von Cayley besagt, dass die Anzahl der Gerüste eines
> vollständigen(!) Graphen gleich [mm]n^{n-2}[/mm] ist. Aber das Haus
> vom Nikolaus ist leider kein vollständiger Graph. Wie kann
> ich hier vorgehen ?
Hallo,
ich habe einmal nachgeschaut, was für einen "Satz von Cayley"
du hier wohl meinst, denn es gibt verschiedene Sätze, die unter
dieser Bezeichnung laufen. Zum Thema passend habe ich dann
z.B. dies gefunden: Anzahl der Gerüste .
Für den Fall n=5 liefert dieser Satz eine Anzahl von 125. Dies
ist aber die Anzahl aller möglichen "Gerüste". Diese Gerüste
lassen sich aber aufgrund der Isomorphierelation in eine kleine
Anzahl von Äquivalenzklassen einteilen.
Im Falle n=5 (oder n=6 ?) und also auch für das "Haus vom
Nikolaus" bleibt jedenfalls nur eine ganz geringe Anzahl nicht
isomorpher Spannbäume übrig.
LG Al-Chw.
|
|
|
|
![[]](http://www.zahlendoktor.de/images/Nikolaus.gif){kind=small}
Version 1![[]](http://www.zdmka.uni-karlsruhe.de/Nikolaus.gif){kind=small}
Version 2