查看“︁奥尔定理”︁的源代码

{{Refimprove|time=2020-06-25T06:05:02+00:00}}
[[File:Ore_theorem_example.svg|缩略图|满足奥尔定理条件的图，及图中的哈密顿环。在图形的中心有两个度数小于 ''n''/2的顶点，因此它不满足{{le|狄拉克定理 (哈密頓圖)|Dirac's theorem on Hamiltonian cycles|狄拉克定理}}的条件。但是，这两个顶点是相邻的，并且所有其他顶点对的总度数至少为 7（图的总顶点数）。]]
'''奥尔定理'''是[[挪威]]数学家[[奥斯丁·欧尔]]在1960年证明的[[图论]]定理。它为判断图为[[哈密顿图]]提供了一个充分条件，并且从本质上说明了如果一个图具有足够多的边，则它必然包含[[哈密顿图|哈密顿环]]。具体来说，如果一个图中每一对[[图论术语#相邻|非相邻]][[顶点 (图论)|顶点]]的[[度 (圖論)|度数]]和都大于等于顶点总数，那么该图为哈密顿图。<ref>{{Cite journal|title=Note on Hamilton Circuits|url=https://www.jstor.org/stable/2308928?origin=crossref|last=Ore|first=Oystein|date=1960-01|journal=The American Mathematical Monthly|issue=1|doi=10.2307/2308928|volume=67|pages=55|access-date=2019-12-25|archive-date=2019-05-02|archive-url=https://web.archive.org/web/20190502003938/https://www.jstor.org/stable/2308928?origin=crossref|dead-url=no}}</ref>

== 内容 ==
设 {{Math|''G''}} 为（有限的）简单[[图 (数学)|无向图]]，其顶点数 {{Math|''n'' ≥ 3}}。

奥尔定理表明，如果对每对 {{math|''G''}} 中的[[图论术语#相邻|不相邻]]顶点对 {{math|''v''}} 和 {{math|''w''}}，均有 {{NumBlk|:|{{math|deg ''v'' + deg ''w'' ≥ ''n'',}} |∗}} 那么 {{Math|''G''}} 是[[哈密顿图]]。

式中，{{Math|deg ''v''}} 表示 {{Math|''G''}} 中顶点 {{Math|''v''}} 的[[度 (圖論)|度数]]（即与 {{Math|''v''}} 相连的边数）。

== 证明 ==
[[File:Ore_theorem_proof.svg|缩略图|奥尔定理的示意图。在图中，存在[[哈密顿路径]] {{Math|''v''<sub>1</sub>...''v''<sub>''n''</sub>}} ，但是没有[[哈密頓環|哈密顿回路]]。{{Math|''v''<sub>1</sub>''v''<sub>''i''</sub>}} 和 {{Math|''v''<sub>''i'' &minus; 1</sub>''v''<sub>''n''</sub>}}（如蓝色的虚线）兩者之中，最多只有連一條邊，因为如果两者都連邊，那么将它们添加到上述路径中，并删除红边 {{Math|''v''<sub>''i'' &minus; 1</sub>''v''<sub>''i''</sub>}} ，就会产生一个哈密顿回路。]]
此定理等价于：每个非哈密顿图 {{Mvar|G}} 都不满足 '''(∗)'''。

设 {{Mvar|G}} 是一个頂點数 {{Math|''n'' ≥ 3}} 的非哈密顿图。考慮是否有邊不在 {{Mvar|G}} 中，且加入 {{Mvar|G}} 後，仍沒有[[哈密頓環|哈密顿回路]]。若有此種邊，則選一條加入 {{Mvar|G}} 中。如此重複，直到不能再加，得到的新图稱為 {{Mvar|H}}。令 {{Math|''x''}} 、 {{Math|''y''}} 为 {{Mvar|H}} 中任意一对非邻接顶点，此时若向 {{Mvar|H}} 中加入边 {{Math|''xy''}} ，则图中将有哈密顿回路（否則先前加邊的過程仍能繼續）。这个回路中，除 {{Math|''xy''}} 以外的其他边将形成一條[[哈密顿路径]] {{Math|''v''<sub>1</sub>''v''<sub>2</sub>...''v''<sub>''n''</sub>}}，其中 {{Math|1=''x'' = ''v''<sub>1</sub>}} 且 {{Math|1=''y'' = ''v<sub>n</sub>''}}。 对于 {{Math|2 ≤ ''i'' ≤ ''n''}} 范围内的每个 {{Math|''i''}} ，考虑两条可能的边：从 {{Math|''v''<sub>1</sub>}} 至 {{Math|''v''<sub>''i''</sub>}} 和从 {{Math|''v''<sub>''i'' &minus; 1</sub>}} 至 {{Math|''v''<sub>''n''</sub>}}，这两条边最多有一条存在於 {{Mvar|H}} 中，否则 {{Math|''v''<sub>1</sub>''v''<sub>2</sub>...''v''<sub>''i'' &minus; 1</sub>''v''<sub>''n''</sub>''v''<sub>''n'' &minus; 1</sub>...''v''<sub>''i''</sub>}} 会形成哈密顿回路。因此，{{Math|''v''<sub>1</sub>}} 与 {{Math|''v''<sub>''n''</sub>}} 的度数之和最多等于 {{Math|''i''}} 的可能取值数量，也就是 {{Math|''n'' &minus; 1}}。这说明 {{Mvar|H}} 不满足 '''(∗)''' ，因为 ({{Math|deg ''v''<sub>1</sub> + deg ''v''<sub>''n''</sub>}}) 小于 {{Math|''n''}}。 

但是，{{Mvar|H}} 是由 {{Mvar|G}} 加邊（可能 {{Math|0}} 條）而成，故 {{Mvar|G}} 的顶点度不大于 {{Mvar|H}} 中的顶点度数，所以 {{Mvar|G}} 也不满足&nbsp;'''(∗)''' 性质，得证。

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

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

==算法==
1997年，帕爾默（{{lang|en|E. M. Palmer}}）發表以下算法，只要一幅圖滿足奧爾定理的條件，就能從中構造一個哈密頓回路：<ref>{{cite journal
 | last = Palmer | first = E. M.
 | doi = 10.1016/S0898-1221(97)00225-3
 | issue = 11
 | journal = Computers & Mathematics with Applications
 | mr = 1486890
 | pages = 113–119
 | title = The hidden algorithm of Ore's theorem on Hamiltonian cycles
 | url = https://archive.org/details/sim_computers-mathematics-with-applications_1997-12_34_11/page/113 | trans-title = 哈密頓圈的奧爾定理中，隱藏的算法
 | volume = 34
 | year = 1997| doi-access = free
 | language = en
 }}</ref> 

#任意將頂點排成一個環形，無視鄰接與否。
#若環上任意連續兩個頂點皆已連邊，則得到哈密頓環，算法結束。否則，可以找到環上有連續兩個頂點 <math>v_i, v_{i+1}</math>，在圖中並不鄰接，此時執行下列步驟：
#*搜尋下標<math>j</math>，使得四個頂點<math>v_i, v_{i+1}, v_j, v_{j+1}</math>兩兩互異，且圖上有<math>v_i v_j</math>與<math>v_{j+1}v_{i+1}</math>兩條邊。
#*將環<math>v_{i+1}</math>至<math>v_j</math>一段弧（含兩端）倒轉次序。
#回到2。

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

== 参考来源 ==
{{reflist}}

[[Category:图论]]
[[Category:数学定理]]