跳至內容

奧爾定理

維基百科,自由的百科全書
滿足奧爾定理條件的圖,及圖中的哈密頓環。在圖形的中心有兩個度數小於 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可免費查閱 (英語).