奥尔定理

奥尔定理是挪威数学家奥斯丁·欧尔在1960年证明的图论定理。它为判断图为哈密顿图提供了一个充分条件，并且从本质上说明了如果一个图具有足够多的边，则它必然包含哈密顿环。具体来说，如果一个图中每一对非相邻顶点的度数和都大于等于顶点总数，那么该图为哈密顿图。

满足奥尔定理条件的图，及图中的哈密顿环。在图形的中心有两个度数小于 n/2的顶点，因此它不满足狄拉克定理的条件。但是，这两个顶点是相邻的，并且所有其他顶点对的总度数至少为 7（图的总顶点数）。

内容

设 G 为（有限的）简单无向图，其顶点数 n ≥ 3。

奥尔定理表明，如果对每对 G 中的不相邻顶点对 v 和 w，均有

deg v + deg w ≥ n,

∗

那么 G 是哈密顿图。

式中，deg v 表示 G 中顶点 v 的度数（即与 v 相连的边数）。

证明

奥尔定理的示意图。在图中，存在哈密顿路径 v₁...v_n ，但是没有哈密顿回路。v₁v_i 和 v_{i − 1}v_n（如蓝色的虚线）两者之中，最多只有连一条边，因为如果两者都连边，那么将它们添加到上述路径中，并删除红边 v_{i − 1}v_i ，就会产生一个哈密顿回路。

此定理等价于：每个非哈密顿图 G 都不满足 (∗)。

设 G 是一个顶点数 n ≥ 3 的非哈密顿图。考虑是否有边不在 G 中，且加入 G 后，仍没有哈密顿回路。若有此种边，则选一条加入 G 中。如此重复，直到不能再加，得到的新图称为 H。令 x 、 y 为 H 中任意一对非邻接顶点，此时若向 H 中加入边 xy ，则图中将有哈密顿回路（否则先前加边的过程仍能继续）。这个回路中，除 xy 以外的其他边将形成一条哈密顿路径 v₁v₂...v_n，其中 x = v₁ 且 y = v_n。 对于 2 ≤ i ≤ n 范围内的每个 i ，考虑两条可能的边：从 v₁ 至 v_i 和从 v_{i − 1} 至 v_n，这两条边最多有一条存在于 H 中，否则 v₁v₂...v_{i − 1}v_nv_{n − 1}...v_i 会形成哈密顿回路。因此，v₁ 与 v_n 的度数之和最多等于 i 的可能取值数量，也就是 n − 1。这说明 H 不满足 (∗) ，因为 (deg v₁ + deg v_n) 小于 n。

但是，H 是由 G 加边（可能 0 条）而成，故 G 的顶点度不大于 H 中的顶点度数，所以 G 也不满足 (∗) 性质，得证。

定理的充分性

需要注意的是，奥尔定理给出的是判定一幅图为哈密顿图的一个充分条件而非充要条件。换言之，一幅不满足奥尔定理条件的图仍有可能为哈密顿图。

例如，对于一个形如六边形的图（“6阶循环图”，为简单无向图），其任意两个不相邻的顶点度数之和为4（比6小），但显然该图是一个哈密顿图。

算法

1997年，帕尔默（E. M. Palmer）发表以下算法，只要一幅图满足奥尔定理的条件，就能从中构造一个哈密顿回路：

1. 任意将顶点排成一个环形，无视邻接与否。
2. 若环上任意连续两个顶点皆已连边，则得到哈密顿环，算法结束。否则，可以找到环上有连续两个顶点 $v_{i},v_{i+1}$，在图中并不邻接，此时执行下列步骤：
   • 搜寻下标$j$，使得四个顶点$v_{i},v_{i+1},v_{j},v_{j+1}$两两互异，且图上有$v_{i}v_{j}$与$v_{j+1}v_{i+1}$两条边。
   • 将环$v_{i+1}$至$v_{j}$一段弧（含两端）倒转次序。
3. 回到2。

每次执行倒转时，环形上的边数必定增加$1$或$2$（视乎过程中要拆散的$v_{j}v_{j+1}$是否已经是边），所以至多执行$n$次，算法就会停止，其中$n$为顶点数。与上述证明类似，第2步若未得到哈密顿环，则所求的下标$j$必定存在，否则顶点$v_{i}$与$v_{i+1}$既不邻接，其度数和又不够大，不满足奥尔定理的条件。$i$和$j$皆可将全部顶点扫描一次找到，时间复杂度用大O符号可以写成$O(n)$，倒转弧$v_{i+1}$至$v_{j}$亦然。所以，乘上外层重复执行的次数，总时间复杂度为$O(n^{2})$，与边数吻合。