哈密顿图

哈密顿图是一個無向圖，由哈密顿爵士提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（英語：，或）。

十二面体中的哈密顿回路

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

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

哈密尔顿图的充分条件： 设 ${\displaystyle G=(V,E)}$ 是一个无向简单图，${\displaystyle |V|=n}$，${\displaystyle n\geq 3}$。若对于任意的两个顶点 ${\displaystyle u,v\in V}$，那么 ${\displaystyle u}$ 和 ${\displaystyle v}$ 的度，即 ${\displaystyle d(u)}$ 与 ${\displaystyle d(v)}$ 满足 ${\displaystyle d(u)+d(v)\geq n}$，那么，${\displaystyle G}$ 是哈密尔顿图。此条件由美国图论数学家奥勒在1960年给出。

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

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