概念

判断

算法级别

概念

哈密顿图

h哈密顿通路(回路)与哈密顿图 通过图G的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图.

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

判断

判断哈密顿图是较为困难的.

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

(1) 在无向简单图G=<V,E>中&frac12;V&frac12;&sup3;3,任意不同结点 ,则G是哈密顿图.(充分条件，定理4)

(2) 有向完全图D=<V,E>, 若 ，则图D是哈密顿图. (充分条件，定理5推论)

(3) 设无向图G=<V,E>,"V1&Igrave;V，则P(G－V1)&pound;&frac12;V1&frac12;(必要条件，定理3)

若此条件不满足，即$V1&Igrave;V，使得P(G－V!)>&frac12;V1&frac12;,则G一定不是哈密顿图(非哈密顿图的充分条件).

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

算法级别

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