Anzahl der Hamiltonkreise im Km,m

Neue Frage »

Luxa-kun Auf diesen Beitrag antworten »
Anzahl der Hamiltonkreise im Km,m
Meine Frage:
wie viele Hamiltonkreise gibt es in einem vollständigen bipartiten Graphen Km,n für beliebig fixiertes m=n?

Meine Ideen:
wäre es (n!)^2? Da n Möglichkeiten auf der einen Seite, mal n auf der anderen, mal n-1 auf der ersten und so weiter?
HAL 9000 Auf diesen Beitrag antworten »

Wenn sich mal der Graphentheorie-Laie äußern darf: So wie ich das verstehe, gibt es in dem Hamiltonkreis doch keinen herausgehobenen Anfangspunkt, oder?

Wenn dem so ist, dann hast du dadurch schon mal einen Faktor zuviel drin.

Außerdem gibt es doch auch keine Vorzugsrichtung, in der der Kreis durchlaufen wird, oder?

Das ergibt im Fall eine weitere Halbierung, so dass man insgesamt wohl nur auf kommen dürfte.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »