哈密顿图

经过每个顶点恰好一次的图结构;含哈密顿回路的图称为哈密顿图,一般图判定是 NP 完全的,Dirac 与 Ore 条件给出充分判定。

标签 图论 / 哈密顿图 / 哈密顿回路 / 哈密顿路径

定义

设 𝐺=(𝑉,𝐸) 是 无向图。经过每个顶点恰好一次的路径称为哈密顿路径;经过每个顶点恰好一次的简单环称为哈密顿回路。存在哈密顿回路的图称为哈密顿图。

存在哈密顿路径的图称为可迹图。哈密顿路径的端点不要求相邻,因此可迹图不一定是哈密顿图。

对有向图可以同样定义有向哈密顿路径和有向哈密顿回路;本页的 Dirac、Ore 条件只适用于简单无向图。

必要条件

设 𝐺 有 𝑛≥3 个顶点。若 𝐺 是哈密顿图,则:

  • 𝐺 是 2-连通的,即删去任意一个顶点后仍连通;
  • 对任意非空真子集 𝑆⊂𝑉,𝑐(𝐺−𝑆)≤|𝑆|,其中 𝑐(𝐻) 表示 𝐻 的连通分量数;
  • 若 𝐺 是二分图,则它的两部大小相等。

2-连通不是充分条件。例如完全二分图 𝐾2,3 是 2-连通的,但两部大小为 2 和 3,不可能有哈密顿回路。

充分条件

设 𝐺 是 𝑛≥3 个顶点的简单无向图,𝛿(𝐺) 为最小度。

  • Dirac 条件:若 𝛿(𝐺)≥𝑛2,则 𝐺 是哈密顿图。
  • Ore 条件:若对任意两个不相邻顶点 𝑢,𝑣 都有 𝑑(𝑢)+𝑑(𝑣)≥𝑛,则 𝐺 是哈密顿图。

Dirac 条件是 Ore 条件的推论。它们只给出充分条件:例如 𝐶5 的 𝛿(𝐺)=2<52,但 𝐶5 是哈密顿图。

与欧拉图的区别

欧拉图要求每条边恰好经过一次,判定只依赖度数和连通性;哈密顿图要求每个顶点恰好经过一次,一般图的判定是 NP 完全的。两者约束的对象不同,不能互相替代。

常见误解

  • 认为 Dirac 或 Ore 条件是必要条件:它们只充分;𝐶5 不满足 Dirac 条件,但仍是哈密顿图。
  • 认为 2-连通就一定是哈密顿图:𝐾2,3 是 2-连通的非哈密顿图。
  • 认为有哈密顿路径就有哈密顿回路:路径的两个端点不一定相邻,例如一条长链只有哈密顿路径。
  • 认为哈密顿图一定也是欧拉图:𝐾4 是哈密顿图,但所有顶点度为 3,不是欧拉图。
  • 认为哈密顿回路唯一:一个图可以有多条不同的哈密顿回路。
源码位置