奥尔定理

奥尔定理是挪威数学家奥斯丁·欧尔在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})$，與邊數吻合。