n阶完全图中哈密顿回路的条数为什么？

Question

如题所述

Answer 1

　哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.
n阶完全图中哈密顿回路的条数为：（n-1)!/2
选定一个点，从这点开始到每个点的走法，只要有三个点以上就是圈，因此只管走的方法，选定构成一个圈的点算了两次，所以要除以2。
若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n − 1) / 2条边，以Kn表示。它是(k − 1)-正则图。所有完全图都是它本身的团。
你算出的那个是无项完全图的条数吧。
设Kn的每一条哈密顿回路是v1,v2...vn,v1
v1,v2...vn对应完全图顶点的一个全排列
所以Kn中不同的哈密顿回路有N!条。