如何在完整的无向图中找到哈密顿环的周期数？

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个不同的哈密顿循环.