[科普中国]-哈密顿图

哈密顿通路（回路）与哈密顿图 （Hamilton图） 通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）。存在哈密顿回路的图就是哈密顿图。

美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈，含有图中所有顶点的路径称作哈密顿路径。1

哈密顿圈[Hamilton cycle]

图的哈密顿圈是指包含图的所有顶点的圈。类似地，包含图的所有顶点的路称为图的哈密顿路（Hamilton path）。一个图若包含哈密顿圈，则称这个图为哈密顿图（Hamiltonian graph）。这种路和圈之所以用哈密顿的名字命名，是因为哈密顿在1856年发明了正 12 面体数学游戏：从正 12 面体的一个顶点出发沿棱行走，能否经过每一个顶点恰好一次回到出发点。用图的语言即为：给定一个图 G ，G 是否有哈密顿圈。

判断条件与欧拉图的情形不同，到目前为止还未找到判断一个图是否是哈密顿图的非平凡的充要条件。事实上这是图论中尚未解决的主要问题之一。哈密顿图有很多充分条件，例如，

（1）若图的最小度不小于顶点数的一半，则图是哈密顿图；

（2）若图中每一对不相邻的顶点的度数之和不小于顶点数，则图是哈密顿图。

另外，还有很多用度序列、度和、图的坚韧度等参数给出的充分条件。2

哈密顿图的充分条件和必要条件

定理1： 设无向图G是哈密顿图，V1是V的任意的非空子集， p(G-V1)≤|V1| 其中，p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得到的图的连通分支。

定理2： 设G是n(n≥3)阶无向简单图，如果G中任何一对不相邻的顶点度数之和都大于等于n，则G是哈密顿图。

推论： 设G是n(n≥3)阶无向简单图，如果G中任何一对不相邻的顶点的度数之和都大于等于n，则G是哈密顿图。

定理3： 在n(n≥2)阶有向图D=中，如果所有有向边均用无向边代替，所得无向图中含生成子图Kn，则有向图中存在哈密顿图。

推论： n(n≥3)阶有向完全图为哈密顿图。

哈密顿路径也称作哈密顿链，指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全(NP-complete）问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP完全的。

算法级别一般地，寻找一个图的哈密顿圈问题是 NP 困难的。因此通常都是用穷举搜索的方法来判定一个图是否含有哈密顿路或圈。后来鲁宾（F.Rubin）利用推演的方法给出了一个好一点的搜索步骤来找出图里的一些或者全部的哈密顿路或圈，安格鲁因（D.Angluin）和瓦利安特（L.G.Valiant）设计的概率算法对哈密顿路或圈的寻找也是非常有用的。寻找哈密顿路的确定算法虽然很难有多项式时间的，但是这并不意味着只能进行时间复杂度为暴力搜索。利用状态压缩动态规划，我们可以将时间复杂度降低到，具体算法是建立方程f[i][S][j]，表示经过了i个节点，节点都是集合S的，到达节点j时的最短路径。每次我们都按照点j所连的节点进行转移。

哈密顿图及其判定方法可以解决中国邮路问题、旅行售货员问题、排座位问题、判定图是否可一笔画问题。1

本词条内容贡献者为:

尚华娟 - 副教授 - 上海财经大学