Hamilton 路与 Hamilton 圈

形式陈述 ​

在有限图 $G=(V,E)$ 中，Hamilton 路是包含 $V$ 中每个顶点恰好一次的路公理库路与圈Path and cycle in a graph由相邻顶点序列形成的路，以及首尾闭合的圈。。若这条路的两个端点相邻，加入连接它们的边便得到包含全部顶点的Hamilton 圈；含 Hamilton 圈的图称为 Hamilton 图。圈的起点与行走方向不构成新的圈，重要的是它选出的循环次序和边集。

端点受限问题会另外指定 Hamilton 路必须从 $s$ 到 $t$。有向图版本要求连续边都服从方向，并把首尾闭合成有向圈。这些定义只约束顶点：Hamilton 路用 $|V|-1$ 条边，Hamilton 圈用 $|V|$ 条边，图中其余边无需出现。

不存在像 Euler 判据那样只凭顶点度数就完整刻画一般图 Hamilton 性的简单局部条件。对 $n\ge 3$ 的简单图，Dirac 条件 $\delta (G)\ge n/2$ 与 Ore 条件“每对不相邻顶点 $u,v$ 都满足 $d(u)+d(v)\ge n$”都能保证 Hamilton 圈，但它们是充分条件，不是定义，也不是必要条件。

直觉 ​

Hamilton 问题寻找一种覆盖全体顶点的全局次序：每个顶点只有一次进入和一次离开的机会，局部选择会持续压缩后续可用的连接。Euler 迹公理库欧拉迹Eulerian trail · Eulerian path恰好一次经过每条边的迹。恰好相反，它消费每条边而允许重复顶点，因此顶点度数的进出配对能给出完整判据。把“边一次”换成“顶点一次”看似细小，却把局部平衡问题变成了难以由局部信息决定的整体排列问题。

例子与边界 ​

完全图 $K_n$ 在 $n\ge 3$ 时可按任意顶点排列首尾相接，因而有 Hamilton 圈。路径图 $P_n$ 自身是一条 Hamilton 路，却在 $n\ge 3$ 时没有 Hamilton 圈，因为两个端点度数为 $1$。星图 $K_{1,r}$ 在 $r\ge 3$ 时连 Hamilton 路也没有：一条简单路经过中心至多连接两个叶子，第三个叶子无法被纳入。Petersen 图则有 Hamilton 路而没有 Hamilton 圈，说明“存在覆盖路”严格弱于“存在覆盖圈”。

Hamilton 圈不要求使用全部边。$K_4$ 的任一四边形次序给出 Hamilton 圈，剩下两条对角边可以完全不用；因此不能因仍有未走边就否定 Hamilton 性。反过来，一个图可以有 Euler 回路却没有 Hamilton 圈，例如两个三角形只共享一个割点的“8”字图：每条边能在闭迹中恰走一次，但任何简单圈若穿过两个三角形就必须重复共享顶点。

有向图中忽略方向也会制造假解。若底层无向图存在覆盖圈，而某一条必经边只朝相反方向定向，相同顶点次序便不再是有向 Hamilton 圈。

推论与应用 ​

Hamilton 圈把排序、巡回和图的邻接约束放进同一模型。旅行商问题在此基础上给边赋成本，要求从所有 Hamilton 圈中选最便宜者；若只问是否存在，已是经典的 NP 完全判定问题。网格巡检、芯片布线和基因片段排序中也会出现相同的“每个位置一次”约束，但具体模型是否允许重复、缺边或代价，必须另外声明。

图公理库有限简单无向图Graph · Finite simple undirected graph · 图用有限顶点集合和无序二元边集合表示的简单无向图。与路和圈公理库路与圈Path and cycle in a graph由相邻顶点序列形成的路，以及首尾闭合的圈。提供对象语言，Euler 判定公理库Euler 道判定Euler trail criterion · Eulerian trail theorem有限无向图存在遍历每条边恰一次的道路，当且仅当非孤立部分连通且奇度顶点数为零或二。则构成最重要的反面对照。度数条件可以快速给出必要障碍或强充分保证，却不能替代全局构造；例如 Hamilton 圈要求每个顶点度数至少为 $2$，但满足这个必要条件的图仍可能被割点阻断。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, Chapter 10, Hamilton cycles.
• J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, 2008, Chapters 4 and 18, Hamiltonian graphs and sufficient conditions.