algorithm - 如何在完整的无向图中找到哈密顿循环的数量？

Question

有人可以解释如何在完整的无向图中找到哈密顿循环的数量吗？

维基百科说公式是(n-1)!/2，但是当我用这个公式计算时，K3 只有一个周期，K4 有 5 个。我的计算不正确吗？

Answer 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 question

Answer 3

我认为当我们有一个哈密顿循环时，如果我们将一个顶点视为开始和结束循环，那么每个顶点都位于哈密顿循环中。我们应该使用这个顶点的 2 条边。所以我们有 (n-1)(n-2)/2 哈密顿循环，因为我们应该选择连接到这个顶点的 n-1 条边的 2 条边。