我如何才能找到汉密尔顿的周期在一个完整的无向图的数量？ [英] How can I find the number of Hamiltonian cycles in a complete undirected graph?

问题描述

有人可以解释如何找到一个完整的无向图哈密尔顿周期数？

Can someone explain how to find the number of Hamiltonian cycles in a complete undirected graph?

维基百科说该公式是（N-1）！/ 2 ，但使用这个公式时，我算了算，K3只有一个周期，K4具有5是我的计算不正确？

Wikipedia says that the formula is (n-1)!/2, but when I calculated using this formula, K3 has only one cycle and K4 has 5. Was my calculation incorrect?

推荐答案

由于图完成后，从一个固定的顶点任何排列给出了一个（几乎）独特的循环（在置换最后的顶点将有一个边缘回，第一，固定顶点除了一件事：如果你访问的顶点在循环以相反的顺序，那么这真的是同一周期（这是因为，这个数字一半​​的的（N-1）的顶点排列会给你）。

Since the graph is complete, any permutation starting with a fixed vertex gives an (almost) unique cycle (the last vertex in the permutation will have an edge back to the first, fixed vertex. Except for one thing: if you visit the vertices in the cycle in reverse order, then that's really the same cycle (because of this, the number is half of what permutations of (n-1) vertices would give you).

例如。顶点1,2,3，修复1，你有：

e.g. for vertices 1,2,3, fix "1" and you have:

123 132

但123逆转（321）是（132）的旋转，因为32是23逆转。

but 123 reversed (321) is a rotation of (132), because 32 is 23 reversed.

有第（n-1）！非固定顶点置换和一半的是另一反向，所以有第（n-1）！/ n个顶点的完全图2不同的哈密顿周期。

There are (n-1)! permutations of the non-fixed vertices, and half of those are the reverse of another, so there are (n-1)!/2 distinct Hamiltonian cycles in the complete graph of n vertices.

这篇关于我如何才能找到汉密尔顿的周期在一个完整的无向图的数量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！