Wie finde ich die Anzahl der Hamilton-Zyklen in eine vollständige ungerichtete Graphen?

Kann mir jemand erklären, wie man die Anzahl der Hamilton-Zyklen in eine vollständige ungerichtete graph?

Wikipedia sagt , daß die Formel (n-1)!/2aber wenn ich berechnet mit Hilfe dieser Formel K3 hat nur einen Takt-und K4-5. War meine Berechnung falsch?

InformationsquelleAutor der Frage avd | 2009-09-07

  1. 24

    Da der graph vollständig ist, jede permutation beginnend mit einem festen Eckpunkt gibt eine (fast) einzigartige Zyklus (der Letzte Eckpunkt in der permutation wird ein edge-zurück zu den ersten, festen Eckpunkt. Außer für eine Sache: wenn du die Scheitelpunkte in den Zyklus in umgekehrter Reihenfolge, dann ist das wirklich der gleiche Zyklus (weil das die Zahl ist die Hälfte von dem, was Permutationen, (n-1) Eckpunkte geben würde).

    z.B. für die Eckpunkte 1,2,3, - fix "1" und Sie:

    123
    132

    aber 123 Umgekehrt (321) ist eine rotation von (132), da 32 23 Umgekehrt.

    Gibt es (n-1)! Permutationen der nicht-festen Ecken, und die Hälfte von denen sind das Gegenteil des anderen, so gibt es (n-1)!/2 verschiedene Hamilton-Zyklen der vollständige graph mit n Ecken.

    InformationsquelleAutor der Antwort Jonathan Graehl

  2. 2

    Antwort auf deine Google Code Jam Kommentar, siehe diese Frage ALSO

    InformationsquelleAutor der Antwort xan

  3. -1

    Ich denke, wenn wir einen Hamilton-Zyklus, da jeder Knoten liegt in der Hamilton-Zyklus, wenn wir betrachten einen Knoten als Start-und End-Zyklus . wir verwenden sollten, 2 Kanten von diesem Knoten.So haben wir (n-1)(n-2)/2 Hamilton-Zyklus, da sollten wir wählen 2 Kanten von n-1 Kanten, die verbunden mit diesem vertex.

    InformationsquelleAutor der Antwort user3591890

Schreibe einen Kommentar