Anzahl Hamiltonkreise in einem volständigen Graphen [Diskrete Mathematik] |
24.11.2010, 18:34 | Fetterchefkoch | Auf diesen Beitrag antworten » |
Anzahl Hamiltonkreise in einem volständigen Graphen [Diskrete Mathematik] Hallo zusammen, ich bin mal wieder an einer Aufgabe die ich nicht lösen kann. Es geht darum, dass wir für jeden vollständigen Graphen, die Anzahl Hamiltonkreise herausfinden müssen. Das erste Problem liegt schon einmal darin, ob es 2 verschiedene Hamiltonkreise sind wenn man ihn dreht. Ein Beispiel: Ich habe einen Graphen von K_4. Ein Hamiltonkreis ist dann der Umfang. Ein anderer ist wenn man von unten links startet nach rechts geht, dann nach schräg oben und dann nochmals nach rechts. Ist dies nun ein anderer Hamiltonkreis als wenn ich zuerst (wieder von unten links) nach oben gehe, dann schräg nach unten und dann wieder nach oben gehe. Meine Ideen: Da wir schon Grundlegendes nicht wissen haben wir keine Ahnung wie wir diese Aufgabe lösen sollen. Schonmal Danke im voraus |
||
25.11.2010, 23:30 | Abakus | Auf diesen Beitrag antworten » |
RE: Anzahl Hamiltonkreise in einem volständigen Graphen [Diskrete Mathematik] Hallo! Also ist ein vollständiger Graph mit 4 Knoten? Du betrachtest die Wege (1, 2, 4, 3) und (1, 4, 2, 3), wobei die Knoten bei mir gegen den Uhrzeigersinn nummeriert sind? Beide Wege sind verschieden, denke ich. Grüße Abakus |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|