如何在完全无向图中找到哈密顿回路的数量？

Question

请问如何在完全无向图中找到哈密顿回路的数量？

维基百科 表示其公式为 (n-1)!/2，但按照此公式计算时，K3 只有一个回路，而 K4 有五个。我的计算是否错误？

- avd

---

在计算总循环次数时，您犯了错误。哈密顿回路必须包括所有的边。k4只有3个这样的循环，总共有5个循环，因此公式是正确的。 - Anubhav

Anubhav 是不正确的，哈密顿回路并不需要包括所有边，它需要包括所有节点/顶点。 - Milan Donhowe

Answer 1

由于该图是完全图，以固定顶点开头的任何排列都会形成一个（几乎）唯一的循环（排列中的最后一个顶点将有一条边回到第一个固定顶点）。除了一件事：如果你按相反的顺序访问循环中的顶点，那么这实际上是同一个循环（因此，该数量是比（n-1）个顶点的排列数量少了一半）。

例如，对于顶点1、2、3，固定“1”则有：

123 132

但是123颠倒过来（321）是（132）的旋转，因为32是23颠倒的。

在完整图中，无法移动的顶点有(n-1)个！非固定顶点的排列方式有（n-1）！种，其中一半是另一个排列的逆序。因此，在具有n个顶点的完全图中，存在（n-1）！/2个不同的哈密顿回路。

- Jonathan Graehl

---

我问了一个关于去年Code Jam问题的问题。但是我仍然无法找出算法。你能否请解释一下这个Code Jam问题？http://code.google.com/codejam/contest/dashboard?c=32004#s=p2 - avd

我将生成2...n的所有排列，其中2位于前半部分，并跳过那些给出任何禁止边缘的排列，即如果您的排列是4235（表示循环142351...），则跳过14、42、23、35或51被禁止的排列。您可以在生成排列时执行此操作，例如，如果14被禁止，则您将在“4...”处停止。 - Jonathan Graehl

但如果顶点数非常大，比如30个，那么生成所有排列，即29！/2，在计算上是非常昂贵的。 - avd

还有一件事，为什么你说“2在前半部分出现了”？这是什么意思？ - avd

你说得对，我提出的30或300个节点图的建议是不切实际的。这似乎是一个棘手的问题。你知道吗，你可以下载那些已经解决它的人的源代码吗？ - Jonathan Graehl

Answer 2

针对你在Google Code Jam评论中的问题，可以参考这个SO问题

- xan

Answer 3

我认为当我们有一个哈密顿回路时，由于每个顶点都位于哈密顿回路中，如果我们将一个顶点视为起始和结束循环，则应该使用此顶点的2条边。因此，我们有(n-1)(n-2)/2个哈密顿回路，因为我们应该选择与此顶点相连的n-1条边中的2条边。

- user3591890