哈密顿路径(Hamiltonian path)和欧拉路径的定义有些相似。
哈密顿路径(通路): 仅且经过图中每个顶点一次的路径
哈密顿环(回路): 起始顶点和终止顶点相同的哈密顿路径
哈密顿图: 存在哈密顿环的图
哈密顿路径问题和哈密顿环问题
哈密顿路径问题和哈密顿环问题是图论中的经典
该问题现有的一些成果如下:
在一个阶数为n的图中，可能成为哈密顿路径的顶点序列最多有有n!个（在完全图的情况下恰好为n!个)，因此暴力搜索所有可能的顶点序列是非常慢的。 一个早期的在有向图上寻找哈密顿环的算法是Martello的枚举算法[3] 由Frank Rubin[4] 提供的搜索过程将图的边分为3种类型：必须在路径上的边，不能在路径上的边，和未定边。在搜索的过程中，一个决策规则的集合将未定边进行分类，并且决定是否继续进行搜索。这个算法将图分成几个部分，在它们上问题能够被单独地解决。
另外，Bellman, Held, and Karp 的动态规划 算法可以在O(
)时间内解决问题。在这个方法中，对每个顶点集S和其中的每一个顶点v ，均做出如下的判定：是否有一条经过S中每个顶点，并且在v结束束的路径，对于每一对S和v，当且仅当存在v的邻居w满足存在一条路径经过S-v所有顶点，并在上w结束的路径时，存在路径经过中S每个顶点，并且在v结束。这个充要条件已经可以之前的动态规划计算中确认。[5][6] Andreas Björklund通过inclusion–exclusion principle将哈密尔顿环的计数问题规约成一个更简单，圈覆盖的计数问题，后者可以被通过计算某些矩阵的行列式解决。通过这个方法，并通过蒙特卡洛算法，对任意 n阶图，可以在O(
)时间内解决。对于二分图，这个算法可以被进一步提升至o( ).[7] 对于最大度小于等于3的图，一个回溯搜索的方法可以在 O(
)时间内找到哈密顿环.[8] 哈密顿环和哈密顿路径也可以通过SAT solver找到.
问题的充分条件
哈密顿路径存在的充分条件:对于
哈密顿环存在的充分条件: 对于
推论:假设
相关证明可见:Hamilton 通路和回路的充分条件 - imbiansl’s space (gitee.io)
参考
哈密顿路径问题 - 维基百科，自由的百科全书 (wikipedia.org)
Hamilton 通路和回路的充分条件 - imbiansl’s space (gitee.io)