哈密顿路径问题

图论中的经典问题哈密顿路径问题（台湾作漢米頓路徑問題）（Hamiltonian path problem）与哈密顿环问题（台湾作漢米頓環問題）（Hamiltonian cycle problem）分别是来确定在一个给定的图上是否存在哈密顿路径（一条经过图上每个顶点的路径）和哈密顿环（一条经过图上每个顶点的环）。两个问题皆为NP完全。^[1]

正十二面体上的哈密顿环（红色）。

哈密顿环问题与哈密顿路径问题之间的关系

哈密顿环问题与哈密顿路径问题之间有着很简单的关系：

• 给定图${\displaystyle G}$ ,通过加入新顶点${\displaystyle v}$ 并将新顶点与所有其他顶点连接起来，我们得到了图${\displaystyle H}$。 在图${\displaystyle G}$ 之上的哈密顿路径问题与在${\displaystyle H}$之上的哈密顿环问题等价。因此寻找哈密顿路径的速度不可能比寻找哈密顿环的速度快很多。
• 从另一个方向来看，给定图${\displaystyle G}$，给定图上一个顶点${\displaystyle v}$，通过加入新顶点给定图${\displaystyle v'}$,并且让${\displaystyle v'}$的邻居等于${\displaystyle v}$的邻居，再增加两个度为1的新顶点，并让他们分别与${\displaystyle v}$和${\displaystyle v'}$相连，得到图${\displaystyle H}$，则图${\displaystyle G}$上的哈密顿环问题与图${\displaystyle H}$上的哈密顿路径问题等价。^[2]

算法

在一个阶数为${\displaystyle n}$的图中，可能成为哈密顿路径的顶点序列最多有有${\displaystyle n}$!个（在完全图的情况下恰好为${\displaystyle n}$!个)，因此暴力搜索所有可能的顶点序列是非常慢的。 一个早期的在有向图上寻找哈密顿环的算法是Martello的枚举算法^[3] 由Frank Rubin^[4] 提供的搜索过程将图的边分为3种类型：必须在路径上的边、不能在路径上的边和未定边。在搜索的过程中，一个决策规则的集合将未定边进行分类，并且决定是否继续进行搜索。这个算法将图分成几个部分，在它们上问题能够被单独地解决。

另外，Bellman, Held, and Karp 的动态规划算法可以在O(n² 2ⁿ)时间内解决问题。在这个方法中，对每个顶点集${\displaystyle S}$和其中的每一个顶点${\displaystyle v}$ ，均做出如下的判定：是否有一条经过${\displaystyle S}$中每个顶点，并且在${\displaystyle v}$结束的路径，对于每一对${\displaystyle S}$和${\displaystyle v}$，当且仅当存在${\displaystyle v}$的邻居${\displaystyle w}$满足存在一条路径经过${\displaystyle S-v}$的所有顶点，并在${\displaystyle w}$上结束的路径时，存在路径经过${\displaystyle S}$中每个顶点，并且在${\displaystyle v}$结束。这个充要条件已经可以之前的动态规划计算中确认。^[5][6]

Andreas Björklund通过容斥原理将哈密尔顿环的计数问题规约成一个更简单，圈覆盖的计数问题，后者可以被通过计算某些矩阵的行列式解决。通过这个方法，并通过蒙特卡洛算法，对任意${\displaystyle n}$阶图，可以在O(1.657ⁿ)时间内解决。对于二分图，这个算法可以被进一步提升至O(1.415ⁿ)。^[7]

对于最大度小于等于3的图，一个回溯搜索的方法可以在 O(1.251ⁿ)时间内找到哈密顿环。^[8]

哈密顿环和哈密顿路径也可以通过SAT 求解器找到。

复杂度

哈密顿环和哈密顿路径问题是FNP问题，它的决定性问题是检测是否存在一条哈密顿环或哈密顿路径。有向图和无向图上的哈密顿环问题是卡普的二十一个NP-完全问题中的其中两个。对于一些特殊类型的图来说，它们仍然是NP完全的。例如：

• 二分图^[9]
• 最大度为3的无向平面图^[10]
• 入度和出度最大为2的有向平面图^[11]
• 无桥的无向的平面3-正则二分图
• 3-顶点连通，3-正则的二分图^[12]
• square grid graph的子图^[13]
• square grid graph的3-正则子图^[14]

然而，对于某些类型的图，哈密顿环和哈密顿路径问题可以在多项式时间内解决：

• 根据威廉·湯瑪斯·圖特的结论，4-顶点连通 平面图总是存在哈密顿环，并且可以在线性时间内找到哈密顿环。^[15] by computing a so-called Tutte path.
• 圖特通过证明2-正则平面图包含圖特路径，证明了以上的结论。对2-正则平面图来说，其圖特路径可以在平方时间内找到，^[16]这可能可以被用来寻找一般平面图上的哈密顿环和较长的环。

将以上提供的条件汇总起来，3-正则，3-定点连通的二分图是否总是存在哈密顿环这一问题仍然是开放的，在这个情况下这一问题不是NP完全的，详见Barnette猜想（英语：Barnette's conjecture）。

在所有顶点的度都是奇数的途中，一个与握手引理有关的结论说明对于任意一条边来说，经过它的哈密顿环的个数总是偶数，因此如果存在一条哈密顿环，则一定存在另一条 ^[17] 然而，找到第二条哈密顿换并不是一个简单的计算问题。Papadimitriou定义了一个复杂性类 PPA来描述这一类问题。 ^[18]