Hamiltonscher Graph, wieviele? < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
laut Skript gibt es [mm] \bruch{(n-1)!}{2} [/mm] hamiltonsche Kreise in Kn.
Also gibt es [mm] \bruch{(4-1)!}{2} [/mm] = 3 hamiltonsche Kreise in K4
Wenn man sich jetzt zu diesem K4:
[Dateianhang nicht öffentlich]
den Knoten links oben als a, rechts oben als b, links unten als c, rechts unten als d vorstellt gibt es meiner Meinung nach diese hamiltonschen Kreise:
abcda
bcdab
cbadc
dabcd
adcba
das sind aber 5, wo liegt der Fehler?
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:21 Di 13.12.2011 | | Autor: | felixf |
Moin!
> laut Skript gibt es [mm]\bruch{(n-1)!}{2}[/mm] hamiltonsche Kreise
> in Kn.
>
> Also gibt es [mm]\bruch{(4-1)!}{2}[/mm] = 3 hamiltonsche Kreise in
> K4
>
> Wenn man sich jetzt zu diesem K4:
>
> [Dateianhang nicht öffentlich]
>
> den Knoten links oben als a, rechts oben als b, links unten
> als c, rechts unten als d vorstellt gibt es meiner Meinung
> nach diese hamiltonschen Kreise:
>
> abcda
> bcdab
> cbadc
> dabcd
> adcba
>
> das sind aber 5, wo liegt der Fehler?
Du hast fuenfmal den gleichen Kreis aufgelistet 
Jeder Kreis kann auf verschiedene Wege beschrieben werden (du hast vier verschiedene Startpunkte und zwei verschiedene Richtungen, womit du acht Beschreibungen finden kannst - fuenf davon hast du bereits). Es geht hier aber um die Anzahl der Kreise, nicht um die Anzahl der Beschreibungen von Kreisen durch geschlossene Wege.
LG Felix
|
|
|
| |
|
> Du hast fuenfmal den gleichen Kreis aufgelistet
>
> Jeder Kreis kann auf verschiedene Wege beschrieben werden
> (du hast vier verschiedene Startpunkte und zwei
> verschiedene Richtungen, womit du acht Beschreibungen
> finden kannst - fuenf davon hast du bereits). Es geht hier
> aber um die Anzahl der Kreise, nicht um die Anzahl der
> Beschreibungen von Kreisen durch geschlossene Wege.
Ok, dann habe ich keine Idee wie die anderen beiden Kreise aussehen müssten.
Was bleibt einem denn übrig ausser die Reihenfolge der Knoten zu variieren?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:20 Di 13.12.2011 | | Autor: | felixf |
Moin!
> > Du hast fuenfmal den gleichen Kreis aufgelistet
> >
> > Jeder Kreis kann auf verschiedene Wege beschrieben werden
> > (du hast vier verschiedene Startpunkte und zwei
> > verschiedene Richtungen, womit du acht Beschreibungen
> > finden kannst - fuenf davon hast du bereits). Es geht hier
> > aber um die Anzahl der Kreise, nicht um die Anzahl der
> > Beschreibungen von Kreisen durch geschlossene Wege.
>
> Ok, dann habe ich keine Idee wie die anderen beiden Kreise
> aussehen müssten.
> Was bleibt einem denn übrig ausser die Reihenfolge der
> Knoten zu variieren?
Der offensichtlichste Kreis ist doch abdca: einmal aussen um das Quadrat herum.
LG Felix
|
|
|
| |
|
Das ist richtig, wie oben beschrieben soll K4 aber 3 hamiltonsche Kreise enthalten.
|
|
|
| |
|
> [mm] $\mbox{\Huge{?}}$
[/mm]
Na, du bist ja ziemlich kurz angebunden.
Um einen Hamiltonweg zu beschreiben, kannst du
immer z.B. beim Punkt a starten. Von da aus kannst
du entweder zu b, zu c oder zu d weiterschreiten:
ab...
ac...
ad...
Dann hast du nochmal die Wahl, ob du z.B. den
Anfang ab... mit c oder mit d fortsetzen willst:
abc... oder abd...
Der Rest ist dann aber jedenfalls eindeutig festgelegt:
abcda oder abdca
Nun machst du dies für die anderen möglichen Anfänge
ebenfalls, musst dann aber noch darauf achten, dass
jeweils 2 der notierten Wege nur als einer gelten, weil
sie denselben Weg nur in umgekehrter Durchlaufrichtung
beschreiben. Daher kommt auch der Nenner 2 in der Formel.
LG Al-Chw.
|
|
|
| |
|
Das werden ja dann 3 Kreise pro Startpunkt, also 12?
Warum benutzt du das Wort Weg in zusammenhang mit Hamiltonkreis?
Im Skript ist ein Weg(nicht zusammenhängend) etwas anders als ein Kreis.
Die Definition bei mir im Skript für Hamiltonkreis:
Ein Kreis in einem Graphen G = (V,E)
heißt Hamiltonkreis, wenn er jeden Knoten von G (genau einmal) enthält. Ein Graph wird Hamiltonsch genannt, wenn er einen Hamiltonkreis enthält.
|
|
|
| |
|
> Das werden ja dann 3 Kreise pro Startpunkt, also 12?
Nein, einen "Startpunkt" habe ich nur benützt, um die
Kreise zu beschreiben. Die Kreise
abcda, bcdab, cdabc, dabcd,
adcba, badcb, cbadc, dcbad
sind aber als identisch zu betrachten. Auch auf einem
(geometrischen) Kreis in der Ebene benützen wir ja
einen "Startpunkt" nur etwa zum Zweck einer Parametri-
sierung, also auch Beschreibung der Durchlaufung.
> Warum benutzt du das Wort Weg in zusammenhang mit
> Hamiltonkreis?
> Im Skript ist ein Weg(nicht zusammenhängend) etwas anders
> als ein Kreis.
Ein Kreis ist nur ein Spezialfall eines Weges: ![[]](/images/popup.gif) Pfade, Zyklen und Kreise
> Die Definition bei mir im Skript für Hamiltonkreis:
>
> Ein Kreis in einem Graphen G = (V,E)
> heißt Hamiltonkreis, wenn er jeden Knoten von G (genau
> einmal) enthält. Ein Graph wird Hamiltonsch genannt, wenn
> er einen Hamiltonkreis enthält.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:17 Di 20.12.2011 | | Autor: | studentxyz |
Danke für die Hilfe, irgendwann ist mir dann ein Licht aufgegangen.
|
|
|
|
