---备忘--- 

       哈密顿图由天文学家哈密顿提出。

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

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

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

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

 已同步至 风树的微博