hamilton · Dirac / Ore

Hamilton 圈：度数够高就一定绕得回来

一条 Hamiltonian path 恰好经过每个顶点一次；若它还能首尾相接，就是一个 Hamiltonian cycle。判断一张图有没有 Hamilton 圈是出了名的难（见下），但有一类极简洁的充分条件：只要每个顶点的度数足够大，图就必定含 Hamilton 圈。本页先看这两条经典定理（Dirac 与 Ore），再用 rotation–extension 的思想在一张满足条件的图上单步构造出一个 Hamilton 圈。

判定问题是 NP-完全的： 给定任意图问「是否存在 Hamilton 圈」，是经典的 NP-complete 问题——目前没有已知的多项式算法，最坏情况下只能近乎枚举。这与 Euler 回路（按边走、有简单的度数判据）形成鲜明对比。正因为一般判定如此困难，下面这些只看度数的充分条件才显得珍贵：它们以一个易验证的前提，直接保证答案为「是」。

Dirac 定理 (1952) 设图 G 有 $n \ge 3$ 个顶点。若每个顶点的度数都满足 $\deg (v) \ge n/2$ ，则 G 含 Hamilton 圈。

Ore 定理 (1960) 设图 G 有 $n \ge 3$ 个顶点。若对任意一对不相邻的顶点 u, v 都有 $\deg (u) + \deg (v) \ge n$ ，则 G 含 Hamilton 圈。

Ore 的前提比 Dirac 更弱（要求更宽松）：若每点 $\deg \ge n/2$ ，那么任意两点度数之和 $\ge n$ ，Dirac 条件自动蕴含 Ore 条件。换言之 Dirac ⟹ Ore，而 Ore 还能覆盖一些度数分布不均、但「不相邻的点彼此补足」的图。两条都只是充分条件：不满足并不意味着没有 Hamilton 圈（例如长圈 C_n 每点度数仅为 2）。

演示图满足 Dirac 条件： 这是一张 6 个顶点的 3-正则图（每点度数 = 3 = n/2），因此 Dirac 保证它含 Hamilton 圈。各顶点度数如下。

顶点	A	B	C	D	E	F	Σ / n
deg	3	3	3	3	3	3	n = 6, n/2 = 3

rotation–extension 方法（构造思路）： 维护一条简单路径，盯住它的一个端点 v，反复做两件事之一。其一，extension（延伸）： 若 v 有邻居还不在路径上，就把它接到末端，路径变长。其二，rotation（旋转）： 若 v 的邻居全在路径内，取其中一个内部点 u（它在路径里的后继记为 w），删去路径边 $u-w$ 、加上 $v-u$ ，并翻转 w 到 v 这一段——于是 w 成为新端点，路径长度不变但端点换了人。换了端点后往往又能继续 extension。

度数条件如何排除「走投无路」： 当一条最长路径的端点 v 无法 extension 时，它的邻居必然全落在路径内部；在 Dirac / Ore 的度数下界下，可证明此时总存在一次能改变端点的 rotation，或两端点恰好相邻可直接闭合——路径永远不会停滞在「既延伸不了、又旋转不出、还闭合不上」的僵局。这正是这两条定理证明的核心：度数足够高 ⟹ rotation–extension 必能把最长路径闭合成 Hamilton 圈。