一、Hamilton轨迹（哈密顿路径）

定义

Hamilton轨迹是图中经过每个顶点恰好一次的开放路径（起点与终点不同）。

存在条件

• 必要条件：图是连通的；
• 充分条件（部分）：
  • Dirac定理：对$n \geq 3$的图，若每个顶点度数$\geq n/2$，则存在Hamilton轨迹；
  • Ore定理：对任意不相邻顶点$u$和$v$，满足$deg(u) + deg(v) \geq n$，则存在Hamilton轨迹。

二、Hamilton回路（哈密顿回路）

定义

Hamilton回路是图中经过每个顶点恰好一次且首尾闭合的环路。

存在条件

• 必要条件：图是连通的且无度为1的顶点；
• 充分条件：
  • Dirac定理（加强）：若每个顶点度数$\geq n/2$且$n \geq 3$，则存在Hamilton回路；
  • Bondy-Chvásal定理：对任意不相邻顶点$u$和$v$，满足$deg(u) + deg(v) \geq n$，则存在Hamilton回路。

三、Hamilton图

定义

Hamilton图是包含至少一条Hamilton回路的图。若图存在Hamilton轨迹但无Hamilton回路，则称为半Hamilton图。

典型特征

性质	Hamilton图	非Hamilton图
连通性	必须连通	可能不连通
顶点度数	常满足高度数条件	存在低度数顶点
边密度	通常较密集	可能稀疏

四、Hamilton图与Euler图对比

特征	Hamilton图	Euler图
遍历对象	顶点	边
闭合性	需闭合（回路）	可开放（轨迹）或闭合
判定难度	NP完全问题	多项式时间可判定

五、例题

例题1：判断Hamilton图

题目：判断下图是否为Hamilton图：

A —— B —— C
|   / \   |
|  D   E  |
| /     \ |
F ——————— G

解：

1. 顶点度数：所有顶点度数≥3（例如A(3), B(4), D(3)等）；
2. 应用Dirac定理：$n=7$，$n/2=3.5$，存在顶点度数<3.5（如A、D度数为3），不满足条件；
3. 构造回路：尝试找到回路A-B-D-F-G-E-C-A，覆盖所有顶点；
4. 结论：是Hamilton图。

例题2：验证Ore定理

题目：设图有5个顶点，边集为{AB, AC, AD, BE, CE, DE, BC, CD}，判断是否存在Hamilton回路。
解：

1. 顶点度数：A(3), B(2), C(3), D(3), E(2)；
2. Ore定理验证：对不相邻顶点B和E，$deg(B)+deg(E)=2+2=4 < 5$，不满足条件；
3. 实际构造：无法找到覆盖所有顶点的回路；
4. 结论：非Hamilton图。

更新日志

2025/3/16 17:14

查看所有更新日志

• 8739a-update于 2025/3/16

版权所有

版权归属：NateHHX

许可证：署名 4.0 国际 (CC-BY-4.0)