奥尔定理是挪威数学家奥斯丁·欧尔在1960年证明的图论定理。它为判断图为哈密顿图提供了一个充分条件，并且从本质上说明了如果一个图具有足够多的边，则它必然包含哈密顿环。具体来说，如果一个图中每一对非相邻顶点的度数和都大于等于顶点总数，那么该图为哈密顿图。
内容
设 为（有限的）简单无向图，其顶点数 。
奥尔定理表明，如果对每对 中的不相邻顶点对 和 ，均有 那么 是哈密顿图。
式中， 表示 中顶点 的度数（即与 相连的边数）。
证明
，但是没有哈密顿回路。 和 （如蓝色的虚线）兩者之中，最多只有連一條邊，因为如果两者都連邊，那么将它们添加到上述路径中，并删除红边 ，就会产生一个哈密顿回路。]]
此定理等价于：每个非哈密顿图 都不满足 (∗)。
设 是一个頂點数 的非哈密顿图。考慮是否有邊不在 中，且加入 後，仍沒有哈密顿回路。若有此種邊，則選一條加入 中。如此重複，直到不能再加，得到的新图稱為 。令 、 为 中任意一对非邻接顶点，此时若向 中加入边 ，则图中将有哈密顿回路（否則先前加邊的過程仍能繼續）。这个回路中，除 以外的其他边将形成一條哈密顿路径 ，其中 且 。 对于 范围内的每个 ，考虑两条可能的边：从 至 和从 至 ，这两条边最多有一条存在於 中，否则 会形成哈密顿回路。因此， 与 的度数之和最多等于 的可能取值数量，也就是 。这说明 不满足 (∗) ，因为 () 小于 。
但是， 是由 加邊（可能 條）而成，故 的顶点度不大于 中的顶点度数，所以 也不满足 (∗) 性质，得证。
定理的充分性
需要注意的是，奥尔定理给出的是判定一幅图为哈密顿图的一个充分条件而非充要条件。换言之，一幅不满足奥尔定理条件的图仍有可能为哈密顿图。
例如，对于一个形如六边形的图（「6階循環圖」，为简单无向图），其任意两个不相邻的顶点度数之和为4（比6小），但显然该图是一个哈密顿图。
算法
1997年，帕爾默（）發表以下算法，只要一幅圖滿足奧爾定理的條件，就能從中構造一個哈密頓回路：
#任意將頂點排成一個環形，無視鄰接與否。
#若環上任意連續兩個頂點皆已連邊，則得到哈密頓環，算法結束。否則，可以找到環上有連續兩個頂點 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一段弧（含兩端）倒轉次序。
#回到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)，與邊數吻合。
参考来源
评论 (0)