哈密顿图

维基百科,自由的百科全书
跳转至: 导航搜索
十二面体中的哈密顿回路

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


哈密尔顿图的定义:

   G=(V,E)是一个图,若G中一条通路通过每一个顶点一次且一次,称这条通路为哈密尔顿通路。
                    若G中一个圈通过每一个顶点一次且仅一次,称这个圈为哈密尔顿圈。
                    若一个图存在哈密尔顿圈,就称为哈密尔顿图。

哈密尔顿图的必要条件:

                    若G=(V,E) 是一个哈密尔顿图,则对于V的每一个非空子集S,均有
                          W(G-S) ≤|S|                      
                    其中W(G-S)表示图G擦去属于S中的顶点后,剩下子图的连通分枝的个数。

哈密尔顿图的充分条件:

                    设G=(V,E)是一个无向简单图,
                         |V|=n.  n≥3. 
                    若对于任意的两个顶点u,v∊V,
                         d(u)+d(v) ≥n,
                    那么, G是哈密尔顿图 


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

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

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