Kann jemand erklären, wie man die Anzahl der Hamilton-Zyklen in einem vollständigen ungerichteten Graphen findet?
Wikipedia sagt , dass die Formel (n-1)!/2 ist, aber wenn ich diese Formel berechnet habe, hat K3 nur ein Zyklus und K4 hat 5. War meine Berechnung falsch?
Da der Graph vollständig ist, gibt jede Permutation, die mit einem festen Eckpunkt beginnt, einen (fast) eindeutigen Zyklus (der letzte Eckpunkt in der Permutation hat eine Kante zurück zum ersten, festen Eckpunkt. Mit Ausnahme einer Sache: wenn du besuchst die Ecken im Zyklus in umgekehrter Reihenfolge, dann ist das wirklich der gleiche Zyklus (deshalb ist die Anzahl die Hälfte dessen, was Permutationen von (n-1) Knoten Ihnen geben würden).
z.B. Für Vertices 1,2,3, fixiere "1" und du hast:
123 132
aber 123 reversed (321) ist eine Rotation von (132), weil 32 23 reversiert ist.
Es gibt (n-1)! Permutationen der nicht-festen Ecken, und die Hälfte davon sind die Umkehrung einer anderen, so dass es (n-1)! / 2 verschiedene Hamilton-Zyklen im vollständigen Graphen von n Ecken gibt.
Als Antwort auf Ihren Google Code Jam-Kommentar finden Sie diese SO-Frage
Ich denke, wenn wir einen Hamilton-Zyklus haben, da jeder Eckpunkt im Hamilton-Zyklus liegt, wenn wir einen Eckpunkt als Anfangs- und Endzyklus betrachten. Wir sollten 2 Kanten dieser Ecke verwenden. Daher haben wir einen (n-1) (n-2) / 2-Hamilton-Zyklus, weil wir zwei Kanten von n-1 Kanten auswählen sollten, die mit dieser Ecke verbunden sind.