動機
恰好訪問每個頂點一次的路線,與恰好經過每條邊一次的歐拉(Euler)路線是不同問題。哈密頓(Hamilton)圈沒有類似度數奇偶性那樣簡單的完整判別法。但度數條件仍能保證其存在。我們證明兩個這樣的條件,並用反例防止把充分條件誤認為必要條件。
定義
定義 4.1.1
(哈密頓路徑與哈密頓圈)
本節 是有限簡單無向圖,。哈密頓路徑恰好訪問每個頂點一次。對 ,哈密頓圈是包含每個頂點的圈;寫成閉合序列時只在末尾重複起點。含哈密頓圈的圖稱為哈密頓圖。非空圖的最小度記為 。
這樣的度數界約束每個頂點,而不是平均度。簡單圖中頂點度數至多為 。下列定理排除 ;在本節的圈約定下,那些圖沒有哈密頓圈。
定理/命題
定理 4.1.2
(Ore 條件)
設圖有 個頂點。若每對不同且不相鄰的頂點 均滿足 ,則圖有哈密頓圈。
推論 4.1.3
(Dirac 條件)
設圖有 個頂點。若 ,則圖有哈密頓圈。
證明思路
證明
(邊極大的反例與兩條交叉邊)
先用反證法證明 Ore 條件。假設存在反例。只要添加缺邊後圖仍非哈密頓,就一次添加一條。可能的邊數有限,過程停在一個邊極大的非哈密頓圖 。它的度數不小於原圖,故仍滿足 Ore 條件。 不是完全圖,因為至少三個頂點的完全圖有哈密頓圈。選 中不相鄰的 。
由極大性,加入 後出現哈密頓圈。此圈必用到新邊,因為 本身沒有哈密頓圈。刪去新邊,留下 中從 到 的哈密頓路徑,記為
對 ,定義兩個指標集
它們的大小分別是 和 ,因為路徑恰好列出每個其他頂點一次。兩集合大小之和至少為 ,可用指標卻只有 個,因此必有交集。取交集中 :從 沿路徑走到 ,經邊 到 ,再沿路徑反向走到 ,最後經邊 回到起點。這在 中形成哈密頓圈,矛盾。指標集自動排除有問題的端點: 不屬於 , 不屬於 ,因為 不相鄰。
證明透視
指標交集如何閉合路徑
Ore 條件在兩個不同地方被使用。首先,它必須在由 過渡到邊極大圖 時保持成立;由於加邊永不降低度數,它確實保持,這正是「極大反例」論證得以成立的原因。其次,它只應用於一對頂點:加入其邊後便完成哈密頓圈的那對不相鄰頂點 。極大性提供了生成路徑 ,單憑度數假設永遠得不到這條路徑。
關鍵的一步是 與 中錯開一位的指標,使一個共同指標同時給出兩條交叉邊 與 ;計數 迫使這樣的指標存在。 不相鄰令 不屬於 、 不屬於 ,所以兩條交叉邊都確實是 的邊。論證以與「 不是哈密頓圖」的假設矛盾而完成。
證明
(由 Ore 推出 Dirac)
Dirac 條件蘊含 Ore 條件:任意不同且不相鄰的兩頂點度數和至少為 。若圖為完全圖,結論顯然;上述證明也涵蓋該情況,因為此時 Ore 條件真空成立。閾值可以不是整數,但度數是整數;當 為奇數時, 等價於 。
例題詳解
例題 4.1.4
(應用度數條件)
八頂點簡單圖最小度為 4。因為 ,Dirac 條件成立,所以存在哈密頓圈。定理證明存在,但沒有直接指出該圈;尋找具體圈是另一個算法任務。
例題 4.1.5
(條件失敗但圈存在)
六圈 按定義就是哈密頓圖,最小度為 2。Dirac 條件要求最小度至少為 3,因此不能應用。充分條件失敗不等於結論失敗。
例題 4.1.6
(刪除頂點的障礙)
兩個三角形僅共享一個頂點時,沒有哈密頓圈。刪去共享頂點會使圖不連通。如果存在哈密頓圈,刪去該頂點後,圈上其餘邊構成一條經過所有剩餘頂點的路徑;因此刪點後的圖仍連通。矛盾證明圈不存在。
常見錯誤
常見錯誤
(在 Ore 條件中檢查相鄰頂點對)
Ore 條件針對不相鄰的頂點對;不必檢查相鄰對。若不存在不相鄰的頂點對,條件真空成立。
常見錯誤
(以平均度代替最小度)
平均度高不代表最小度高。團 加一個孤立頂點有 ,平均度為 ,卻不可能有哈密頓圈;任何更大的團加一個孤立頂點也是如此。
常見錯誤
(推斷 Dirac 定理的逆命題)
圈本身構成一族無限多個哈密頓圖,最小度只有二;當 時小於 。充分度數條件也不會給出最短哈密頓圈,更不能直接解決加權旅行商問題。
總結
Ore 條件控制不相鄰頂點對的度數和;更強的 Dirac 最小度條件蘊含它。證明先把極大反例轉化為生成路徑,再利用兩個指標集的交集將路徑閉合。充分假設失敗時,結論仍未確定。
練習
快速檢查
(九頂點簡單圖最小度為 。Dirac 定理說明甚麼?)
解答 · 答案
因為 ,圖是哈密頓圖;定理沒有指出具體的圈。
快速檢查
(七圈最小度為 。Dirac 假設失敗是否意味著它沒有哈密頓圈?)
解答 · 答案
不是。給出的七圈本身恰好訪問每個頂點一次,是哈密頓圈。Dirac 定理不適用,但其逆命題不成立。
從刪點得到必要條件
哈密頓圈給出一族有用的必要條件。
命題 4.1.7
(從哈密頓圖中刪去頂點)
設 非空。若 是哈密頓圖,刪去 及其關聯邊得到的圖 至多有 個連通分支,孤立的剩餘頂點也算分支。
證明
(把圈切成若干段)
從一個圈刪去 個頂點至多留下 段路徑,每個剩餘頂點都屬於其中一段,而 的額外邊可以合併這些段,不能增加分支。若 ,剩餘圖有零個分支,不等式仍成立。
當 時,結論是刪去任一頂點後圖仍連通,所以哈密頓圖沒有割點。它的最小度也至少為二,因為圈上每個頂點有兩個不同的圈鄰點。這些都是必要條件,但單獨使用甚至同時使用一般都不充分。要證明圈不存在,可以找出使 的分支數大於 的集合 ,或找一個度至多為一的頂點;找不到這類集合並不能證明存在哈密頓圈。
例題 4.1.8
( 沒有哈密頓圈)
考慮完全二部圖 。刪去較小一側的兩個頂點,另一側三個頂點成為孤立點,留下三個分支,多於刪去的兩個頂點,所以它沒有哈密頓圈。也可用交替性證明:二部圖中的圈在兩側之間交替,因此哈密頓圈必須使用兩側相同數量的頂點。兩種證明都無需檢驗所有頂點排列。
即使二部圖兩側大小相差一,仍可能有哈密頓路徑。 中將較小一側記為 ,另一側記為 ,則 是哈密頓路徑。它不能閉合成圈,因為兩端在同一側,不相鄰。所以即使都經過所有頂點,路徑和圈也必須區分。
最小度閾值的緊性
Dirac 閾值的大小不只是取整產生的假象。
反例模式
最小度比閾值少一
聲稱:對偶數 ,最小度 已足以保證哈密頓圈。對偶數 ,取兩個大小為 的團,各選一個頂點,用單條邊連接。每個頂點度數至少為 ,但連接邊是橋。哈密頓圈不能包含橋,因為圈的其餘邊將給橋的端點提供另一條路徑;而圈若經過兩邊的頂點,又必須使用唯一連接邊。所以該圖非哈密頓。最小的非平凡情形 是兩個三角形 與 以邊 相連:度數為 ,刪去 便把 與 分開。閾值 不能降低一。
對奇數 ,取兩個大小為 的團,使它們恰共享一個頂點,其餘頂點互不相同。共享頂點是割點;刪除後剩兩個非空分支。每個非共享頂點的度數為 ,共享頂點度數為 ,故最小度為 。該圖同樣非哈密頓。這兩族圖說明,將整數閾值 降低一,不能對這些階數的所有圖保持定理結論。
橋不能在圈上是局部結論:圈上其餘邊給出繞過該邊的路徑。在偶數階構造中,若圈要覆蓋兩個團,連通結構迫使它跨越兩者之間的唯一邊。兩個步驟都不可缺少。
構造性解釋及其局限
Ore 的證明可以反向閱讀。加入缺邊 後出現哈密頓圈,刪去該邊得到從 到 的生成路徑。度數和條件保證存在指標 ,使重排路徑所需的兩條交叉邊都存在,從而構造不使用 的圈。對具體路徑可寫出兩個指標集並檢查交集。但上述證明假設能夠取得添加邊後圖中的哈密頓圈;就目前表述,它是存在性證明,本身沒有給出快速找到該圈的方法。
例如生成路徑為 ,且圖中有 和 。取 ,得到圈 。兩條交叉邊代替了缺失的閉合邊 ;返回 前六個頂點各出現一次。即便圖整體不滿足 Ore 條件,只要這些邊存在,這種局部重排仍然有效;全局條件的作用是保證證明中的路徑必有這樣一個指標。
目前未知有高效的一般算法:判定一個圖是否哈密頓圖是 NP 完全問題。
自然延伸的下一個問題
有沒有快速的一般哈密頓性檢驗?
目前未知有高效的一般算法:判定一個圖是否哈密頓圖是 NP 完全問題。
Ore 條件和 Dirac 條件容易檢查,但只適用於相當稠密的圖。對一般的圖,判定問題「 有沒有哈密頓圈?」是 NP 完全的;若它有多項式時間算法,NP 中每個問題都會有多項式時間算法。目前並無已知的這種算法。因此本節把充分條件與明確的障礙(例如刪點檢驗)配合使用,而不是給出完整的刻畫。
快速檢查
(圖中有度為一的頂點,它可能是哈密頓圖嗎?)
解答 · 答案
在 的圈約定下不能。哈密頓圈在每個頂點使用兩條不同的關聯邊,但度為一的頂點只有一條。
快速檢查
(證明兩側頂點數不相等的二部圖沒有哈密頓圈。)
解答 · 答案
每條邊都跨越兩側,故圈必須在兩側之間交替。回到起點時圈使用兩側的頂點數相等。哈密頓圈包含所有頂點,因而兩側大小必須相等。
快速檢查
(路徑 所在圖還含 和 。給出哈密頓圈。)
解答 · 答案
取 ,所需交叉邊正是 、。圈為 ;中間幾條邊沿原路徑反向走,兩條額外邊將其閉合。
比較兩個度數檢驗
Dirac 條件只需檢查一個數 ;即使某個頂點的度數較低,Ore 條件仍可能適用。例如從 中刪去共享一個端點 的兩條邊。 的度為 2,小於 ,所以 Dirac 不適用。它的兩個非鄰點各有度 3,度數和為 。這些是僅有的不相鄰頂點對,所以 Ore 條件成立,圖是哈密頓圖。可把 放在它的兩個鄰點之間,再沿剩餘兩個頂點連接成圈。
檢驗 Ore 條件需要檢查不相鄰頂點對及其度數和。若某一對違反不等式,定理只是沒有給出結論,哈密頓圈仍可能存在。反之,若所有相關頂點對均滿足條件,定理保證存在,但不計算不同圈的數目。應用時應說明圖的階數和所用度數,使讀者能核查所有相關頂點對。