跳转到内容

英文维基 | 中文维基 | 日文维基 | 草榴社区

奥尔定理

维基百科,自由的百科全书
满足奥尔定理条件的图,及图中的哈密顿环。在图形的中心有两个度数小于 n/2的顶点,因此它不满足狄拉克定理英语Dirac's theorem on Hamiltonian cycles的条件。但是,这两个顶点是相邻的,并且所有其他顶点对的总度数至少为 7(图的总顶点数)。

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

内容

[编辑]

G 为(有限的)简单无向图,其顶点数 n ≥ 3

奥尔定理表明,如果对每对 G 中的不相邻顶点对 vw,均有

deg v + deg wn,

那么 G哈密顿图

式中,deg v 表示 G 中顶点 v度数(即与 v 相连的边数)。

证明

[编辑]
奥尔定理的示意图。在图中,存在哈密顿路径 v1...vn ,但是没有哈密顿回路v1vivi − 1vn(如蓝色的虚线)兩者之中,最多只有連一條邊,因为如果两者都連邊,那么将它们添加到上述路径中,并删除红边 vi − 1vi ,就会产生一个哈密顿回路。

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

G 是一个頂點数 n ≥ 3 的非哈密顿图。考慮是否有邊不在 G 中,且加入 G 後,仍沒有哈密顿回路。若有此種邊,則選一條加入 G 中。如此重複,直到不能再加,得到的新图稱為 H。令 xyH 中任意一对非邻接顶点,此时若向 H 中加入边 xy ,则图中将有哈密顿回路(否則先前加邊的過程仍能繼續)。这个回路中,除 xy 以外的其他边将形成一條哈密顿路径 v1v2...vn,其中 x = v1y = vn。 对于 2 ≤ in 范围内的每个 i ,考虑两条可能的边:从 v1vi 和从 vi − 1vn,这两条边最多有一条存在於 H 中,否则 v1v2...vi − 1vnvn − 1...vi 会形成哈密顿回路。因此,v1vn 的度数之和最多等于 i 的可能取值数量,也就是 n − 1。这说明 H 不满足 (∗) ,因为 (deg v1 + deg vn) 小于 n

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

定理的充分性

[编辑]

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

例如,对于一个形如六边形的图(「6階循環圖」,为简单无向图),其任意两个不相邻的顶点度数之和为4(比6小),但显然该图是一个哈密顿图。

算法

[编辑]

1997年,帕爾默(E. M. Palmer)發表以下算法,只要一幅圖滿足奧爾定理的條件,就能從中構造一個哈密頓回路:[2]

  1. 任意將頂點排成一個環形,無視鄰接與否。
  2. 若環上任意連續兩個頂點皆已連邊,則得到哈密頓環,算法結束。否則,可以找到環上有連續兩個頂點 ,在圖中並不鄰接,此時執行下列步驟:
    • 搜尋下標,使得四個頂點兩兩互異,且圖上有兩條邊。
    • 將環一段弧(含兩端)倒轉次序。
  3. 回到2。

每次執行倒轉時,環形上的邊數必定增加(視乎過程中要拆散的是否已經是邊),所以至多執行次,算法就會停止,其中為頂點數。與上述證明類似,第2步若未得到哈密頓環,則所求的下標必定存在,否則頂點既不鄰接,其度數和又不夠大,不滿足奧爾定理的條件。皆可將全部頂點掃描一次找到,時間複雜度大O符號可以寫成,倒轉弧亦然。所以,乘上外層重複執行的次數,總時間複雜度為,與邊數吻合。

参考来源

[编辑]
  1. ^ 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). 
  2. ^ 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可免费查阅 (英语).