algorithm - 完全な無向グラフでハミルトニアン サイクルの数を見つけるにはどうすればよいですか?

Question

完全な無向グラフでハミルトニアンサイクルの数を見つける方法を誰かが説明できますか?

ウィキペディアでは式は とあり(n-1)!/2ますが、この式を使って計算すると、K3 は 1 サイクルしかなく、K4 は 5 サイクルです。私の計算は間違っていましたか?

Answer 1

グラフが完成しているので、固定頂点から始まる順列は (ほぼ) 一意のサイクルを与えます (順列の最後の頂点は、最初の固定頂点に戻るエッジを持ちます。1 つのことを除いて:サイクルを逆の順序にすると、それは実際には同じサイクルになります (このため、数は (n-1) 個の頂点の順列で得られるものの半分です)。

たとえば、頂点 1,2,3 の場合、「1」を修正すると、次のようになります。

123 132

しかし、123 反転 (321) は (132) の回転です。32 は 23 反転しているためです。

(n-1)個あります！固定されていない頂点の順列、およびそれらの半分は別の順列の逆であるため、n 個の頂点の完全なグラフには (n-1)!/2 個の異なるハミルトニアン サイクルがあります。

Answer 2

Google Code Jam のコメントへの回答として、この SO の質問を参照してください

Answer 3

1 つの頂点を開始サイクルと終了サイクルと見なすと、各頂点がハミルトン サイクルにあるため、ハミルトン サイクルがあると思います。この頂点の 2 つのエッジを使用する必要があります。この頂点にリンクされた n-1 エッジの 2 つのエッジを選択する必要があるため、(n-1)(n-2)/2 ハミルトン サイクルがあります。