text: 奧爾定理是挪威數學家奧斯丁·歐爾在1960年證明的圖論定理。它為判斷圖為哈密頓圖提供了一個充分條件，並且從本質上說明了如果一個圖具有足夠多的邊，則它必然包含哈密頓環。具體來說，如果一個圖中每一對非相鄰頂點的度數和都大於等於頂點總數，那麼該圖為哈密頓圖。內容.設 "n" ≥ 3。奧爾定理表明，如果對每對 "w"，均有那麼 "G" 是哈密頓圖。式中，"v" 相連的邊數）。證明.此定理等價於：每個非哈密頓圖 G 都不滿足 (∗)。設 "n"。但是，G 也不滿足 (∗) 性質，得證。定理的充分性.需要注意的是，奧爾定理給出的是判定一幅圖為哈密頓圖的一個充分條件而非充要條件。換言之，一幅不滿足奧爾定理條件的圖仍有可能為哈密頓圖。例如，對於一個形如六邊形的圖，但顯然該圖是一個哈密頓圖。演算法.1997年，帕爾默發表以下演算法，只要一幅圖滿足奧爾定理的條件，就能從中構造一個哈密頓迴路：每次執行倒轉時，環形上的邊數必定增加formula_8或formula_9，所以至多執行formula_11次，演算法就會停止，其中formula_11為頂點數。與上述證明類似，第2步若未得到哈密頓環，則所求的下標formula_2必定存在，否則頂點formula_14與formula_6既不鄰接，其度數和又不夠大，不滿足奧爾定理的條件。formula_16和formula_2皆可將全部頂點掃描一次找到，時間複雜度用大O符號可以寫成formula_18，倒轉弧formula_6至formula_7亦然。所以，乘上外層重複執行的次數，總時間複雜度為formula_21，與邊數吻合。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 奧爾定理
metadata: https://zh.wikipedia.org/wiki?curid=6847965