Anzahl Hamiltonkreise nicht vollständiger Graphen

Aufrufe: 352     Aktiv: 17.09.2021 um 13:00
0
Hallo, 

es geht um folgender Graph: 



Ich soll die Anzahl der Hamiltonkreise bestimmen. Dabei sind zwei Hamiltonkreise gleich, 

wenn sie sich nur durch den Startpunkt oder die Laufrichtung unterscheiden.

Meine Frage: ich habe angefangen, "zu Fuß" alle möglichen Kreise aufzuschreiben, die mir auffallen. Aber gibt es irgendein Satz, die Anzahl nicht vollständiger Graphen zu zählen? Weil da steht ja "Bestimme die Anzahl..." ? Sonst hätte da doch "Gib alle möglichen Hamiltonkreise an..." gestanden. 
Falls es keinen Satz gibt, jedoch einen anderen Weg, um die Kreise zu zählen: Kann mir jemand ohne die Lösung zu sagen, Tipps geben?

Danke für jede Antwort!

Diese Frage melden
gefragt

Punkte: 40

 
Kommentar schreiben
1 Antwort
0
1. Ein Hamiltonkreis ist ein geschlossener Pfad, der alle Knoten einmal durchläuft.
2. Zwei Hamiltonkreise sind gleich, wenn sie sich nur durch den Startpunkt oder die Laufrichtung unterscheiden.

Meiner Meinung nach gibt es hier nur einen Kreis. Einmal aussen herum. Alles andere kann nicht mehr 1. erfüllen. Und wenn du woanders startest oder andersherum läuftst, bist du immer auf dem selben Hamiltonkreis (2.).
Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 3.96K

 
Weißt du, wie ich das beweisen kann?   ─   einmaleins 16.09.2021 um 19:47
Ich würde so vorgehen, dass du die Punkte irgendwie eindeutig bestimmst (also z.b. durch Buchstaben). Dann gibt es ja einen Hamiltonkreis, den du angeben kannst. Dann müsstest du halt 2. nutzen, dass alle anderen Hamiltonkreise auf diesem Pfad sich nur durch Startpunkt oder Laufrichtung unterscheiden und somit gleich sind. Jetzt hast du noch 3 Punkte, an denen du anders laufen kannst. Dann erhälst du aber keinen geschlossenen Pfad mehr -> kein Hamiltonkreis. Insgesamt folgt daraus, dass es nur einen Hamiltonkreis gibt.   ─   lernspass 17.09.2021 um 08:42
Das macht Sinn, vielen Dank!   ─   einmaleins 17.09.2021 um 13:00

Kommentar schreiben