寻找哈密顿回路
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)