哈密顿图
经过每个顶点恰好一次的图结构;含哈密顿回路的图称为哈密顿图,一般图判定是 NP 完全的,Dirac 与 Ore 条件给出充分判定。标签 图论 / 哈密顿图 / 哈密顿回路 / 哈密顿路径
定义
设 是 无向图。经过每个顶点恰好一次的路径称为哈密顿路径;经过每个顶点恰好一次的简单环称为哈密顿回路。存在哈密顿回路的图称为哈密顿图。
存在哈密顿路径的图称为可迹图。哈密顿路径的端点不要求相邻,因此可迹图不一定是哈密顿图。
对有向图可以同样定义有向哈密顿路径和有向哈密顿回路;本页的 Dirac、Ore 条件只适用于简单无向图。
必要条件
设 有 个顶点。若 是哈密顿图,则:
- 是 2-连通的,即删去任意一个顶点后仍连通;
- 对任意非空真子集 ,,其中 表示 的连通分量数;
- 若 是二分图,则它的两部大小相等。
2-连通不是充分条件。例如完全二分图 是 2-连通的,但两部大小为 和 ,不可能有哈密顿回路。
充分条件
设 是 个顶点的简单无向图, 为最小度。
- Dirac 条件:若 ,则 是哈密顿图。
- Ore 条件:若对任意两个不相邻顶点 都有 ,则 是哈密顿图。
Dirac 条件是 Ore 条件的推论。它们只给出充分条件:例如 的 ,但 是哈密顿图。
与欧拉图的区别
欧拉图要求每条边恰好经过一次,判定只依赖度数和连通性;哈密顿图要求每个顶点恰好经过一次,一般图的判定是 NP 完全的。两者约束的对象不同,不能互相替代。
常见误解
- 认为 Dirac 或 Ore 条件是必要条件:它们只充分; 不满足 Dirac 条件,但仍是哈密顿图。
- 认为 2-连通就一定是哈密顿图: 是 2-连通的非哈密顿图。
- 认为有哈密顿路径就有哈密顿回路:路径的两个端点不一定相邻,例如一条长链只有哈密顿路径。
- 认为哈密顿图一定也是欧拉图: 是哈密顿图,但所有顶点度为 ,不是欧拉图。
- 认为哈密顿回路唯一:一个图可以有多条不同的哈密顿回路。