奥尔定理
此條目需要补充更多来源。 (2020年6月25日) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f9/Ore_theorem_example.svg/220px-Ore_theorem_example.svg.png)
奥尔定理是挪威数学家奥斯丁·欧尔在1960年证明的图论定理。它为判断图为哈密顿图提供了一个充分条件,并且从本质上说明了如果一个图具有足够多的边,则它必然包含哈密顿环。具体来说,如果一个图中每一对非相邻顶点的度数和都大于等于顶点总数,那么该图为哈密顿图。[1]
内容
[编辑]设 G 为(有限的)简单无向图,其顶点数 n ≥ 3。
奥尔定理表明,如果对每对 G 中的不相邻顶点对 v 和 w,均有
deg v + deg w ≥ n, | ∗ |
那么 G 是哈密顿图。
式中,deg v 表示 G 中顶点 v 的度数(即与 v 相连的边数)。
证明
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Ore_theorem_proof.svg/220px-Ore_theorem_proof.svg.png)
此定理等价于:每个非哈密顿图 G 都不满足 (∗)。
设 G 是一个頂點数 n ≥ 3 的非哈密顿图。考慮是否有邊不在 G 中,且加入 G 後,仍沒有哈密顿回路。若有此種邊,則選一條加入 G 中。如此重複,直到不能再加,得到的新图稱為 H。令 x 、 y 为 H 中任意一对非邻接顶点,此时若向 H 中加入边 xy ,则图中将有哈密顿回路(否則先前加邊的過程仍能繼續)。这个回路中,除 xy 以外的其他边将形成一條哈密顿路径 v1v2...vn,其中 x = v1 且 y = vn。 对于 2 ≤ i ≤ n 范围内的每个 i ,考虑两条可能的边:从 v1 至 vi 和从 vi − 1 至 vn,这两条边最多有一条存在於 H 中,否则 v1v2...vi − 1vnvn − 1...vi 会形成哈密顿回路。因此,v1 与 vn 的度数之和最多等于 i 的可能取值数量,也就是 n − 1。这说明 H 不满足 (∗) ,因为 (deg v1 + deg vn) 小于 n。
但是,H 是由 G 加邊(可能 0 條)而成,故 G 的顶点度不大于 H 中的顶点度数,所以 G 也不满足 (∗) 性质,得证。
定理的充分性
[编辑]需要注意的是,奥尔定理给出的是判定一幅图为哈密顿图的一个充分条件而非充要条件。换言之,一幅不满足奥尔定理条件的图仍有可能为哈密顿图。
例如,对于一个形如六边形的图(「6階循環圖」,为简单无向图),其任意两个不相邻的顶点度数之和为4(比6小),但显然该图是一个哈密顿图。
算法
[编辑]1997年,帕爾默(E. M. Palmer)發表以下算法,只要一幅圖滿足奧爾定理的條件,就能從中構造一個哈密頓回路:[2]
- 任意將頂點排成一個環形,無視鄰接與否。
- 若環上任意連續兩個頂點皆已連邊,則得到哈密頓環,算法結束。否則,可以找到環上有連續兩個頂點 ,在圖中並不鄰接,此時執行下列步驟:
- 搜尋下標,使得四個頂點兩兩互異,且圖上有與兩條邊。
- 將環至一段弧(含兩端)倒轉次序。
- 回到2。
每次執行倒轉時,環形上的邊數必定增加或(視乎過程中要拆散的是否已經是邊),所以至多執行次,算法就會停止,其中為頂點數。與上述證明類似,第2步若未得到哈密頓環,則所求的下標必定存在,否則頂點與既不鄰接,其度數和又不夠大,不滿足奧爾定理的條件。和皆可將全部頂點掃描一次找到,時間複雜度用大O符號可以寫成,倒轉弧至亦然。所以,乘上外層重複執行的次數,總時間複雜度為,與邊數吻合。
参考来源
[编辑]- ^ Ore, Oystein. Note on Hamilton Circuits. The American Mathematical Monthly. 1960-01, 67 (1): 55 [2019-12-25]. doi:10.2307/2308928. (原始内容存档于2019-05-02).
- ^ Palmer, E. M. The hidden algorithm of Ore's theorem on Hamiltonian cycles [哈密頓圈的奧爾定理中,隱藏的算法]. Computers & Mathematics with Applications. 1997, 34 (11): 113–119. MR 1486890. doi:10.1016/S0898-1221(97)00225-3
(英语).