寻找哈密顿回路

May 1, 2011

前几天做sgu 122,结果官网给挂了,没提交上,今天已提交,竟然过了,哈哈,总结一下在图上找哈密顿回路的方法。

下面引用自wikipedia

哈密顿图英语:Hamiltonian path,或Traceable path)是一个无向图,由天文学家哈密顿提出,由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图,闭合的哈密顿路径称作哈密顿回路Hamiltonian cycle),含有图中所有顶的路径称作哈密顿路径

美国图论数学家奥勒1960年给出了一个图是哈密尔顿图的充分条件:对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密尔顿图。

寻找哈密顿路径是一个典型的NP-完全问题。后来人们也证明了,找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。

寻找哈密顿路的确定算法虽然很难有多项式时间的,但是这并不意味着只能进行时间复杂度为O(n!n)暴力搜索。利用状态压缩动态规划,我们可以将时间复杂度降低到O(2^nn^3),具体算法是建立方程f[i][S][j],表示经过了i个节点,节点都是集合S的,到达节点j时的最短路径。每次我们都按照点j所连的节点进行转移。”

其中Ore性质可以表示为:

对所有不邻接的不同点对,有deg(x)+deg(y)>=n

《组合数学》书上同时给出了一个满足Ore性质的稠密图的O(V^2)的算法,算法描述如下:

1)从任意一个顶点开始,在它的两端邻接一个顶点,构造一个越来越长的链,直到不能再长为止。设该链为

y1-y2-y3-…-ym

2)检查y1和ym是否邻接。

a)如果不邻接则转3),如果邻接,转b)

b)如果m=n,则停止构造,并输出链y1-y2-…-ym-y1;否则转c)

c)找一个不在链上的顶点z和在链上的顶点yk,满足yk和z邻接,则得到一条m+1的新链

z-yk-…ym-y1-y2-…y(k-1)

3)在链上找出一个yk,满足y1和yk邻接,y(k-1)和ym邻接,则将链转换为y1-…-y(k-1)-ym-…yk,则y1和yk邻接,转b)

寻找哈密顿回路 - May 1, 2011 -