奧爾定理

奧爾定理是挪威數學家奧斯丁·歐爾在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})$，與邊數吻合。