欧拉图 vs 哈密顿图
概述
欧拉图（Eulerian Graph）和哈密顿图（Hamiltonian Graph）是图论中两个经典的遍历问题，分别关注边和顶点的遍历。欧拉图要求经过每条边恰好一次，哈密顿图要求经过每个顶点恰好一次。二者在判定难度上存在本质差异：欧拉路径有多项式时间判定算法，而哈密顿路径是 NP 完全问题。
定义
欧拉图
图 中存在经过每条边恰好一次的回路，称为欧拉回路。存在欧拉回路的图称为欧拉图。若经过每条边恰好一次但起点和终点不同，则称为欧拉路径（Eulerian path/trail）。判定条件：连通图中所有顶点度数为偶数则有欧拉回路；恰好两个顶点度数为奇数则有欧拉路径。
哈密顿图
图 中存在经过每个顶点恰好一次的回路，称为哈密顿回路。存在哈密顿回路的图称为哈密顿图。若经过每个顶点恰好一次但起点和终点不同，则称为哈密顿路径（Hamiltonian path）。判定其存在性是 NP 完全问题，仅有充分条件（Dirac/Ore 定理）。
对比维度
| 维度 | 欧拉图 | 哈密顿图 |
|---|---|---|
| 遍历对象 | 每条边恰好一次 | 每个顶点恰好一次 |
| 充要条件 | 所有顶点度数为偶数（连通图） | 无已知充要条件 |
| 充分条件 | 度数条件即为充要条件 | Dirac：；Ore： |
| 判定复杂度 | ，多项式时间 | NP 完全，无多项式时间算法 |
| 必要条件 | 图必须是连通图 | 图必须是连通图 |
| 应用场景 | 一笔画问题、中国邮递员问题 | 旅行商问题（TSP）、调度问题 |
| 历史起源 | 欧拉（1736），柯尼斯堡七桥问题 | 哈密顿（1859），十二面体游戏 |
| 边的遍历 | 必须遍历所有边 | 不要求遍历所有边 |
| 顶点访问 | 顶点可重复访问 | 每个顶点恰好访问一次 |
关键区别
- 欧拉图关注”走遍所有边”，哈密顿图关注”访问所有顶点”——遍历对象完全不同
- 欧拉图有简洁的充要判定条件（所有顶点度数为偶数），哈密顿图仅有充分条件（Dirac/Ore），判定其存在性是 NP 完全的
- 欧拉路径的判定只需检查度数为奇数的顶点个数（0 个或 2 个），哈密顿路径的判定需要穷举或启发式算法
- 完全图 既是欧拉图（ 为奇数时）又是哈密顿图（ 时），但这两个性质独立——一个图可以只有其一
- 欧拉路径允许重复访问顶点（只要不重复走边），哈密顿路径不允许重复访问顶点
联系
- 二者都要求图是连通图，不连通的图既不可能有欧拉回路也不可能有哈密顿回路
- 二者都是图论中的经典遍历问题，分别对应”边的遍历”和”顶点的遍历”两个维度
- 欧拉路径和哈密顿路径分别是欧拉回路和哈密顿回路的”开路”版本
- 在实际应用中，欧拉问题对应路线优化（邮递员问题），哈密顿问题对应访问优化（旅行商问题）
- 二者都是 Rosen 第8版第10章的核心内容，并列讨论体现了”遍历”这一主题的两个不同维度