動機
哈密頓(Hamilton)路徑恰好訪問每個頂點一次。哈密頓圈則把這樣的訪問首尾相接成一個環。兩者的定義很接近,但歸約必須保持每一個「是」例子與「否」例子的答案,包括端點和邊的方向。旅行推銷員問題中也出現類似的問題:把圖中缺失的邊設為高成本可以編碼哈密頓圈,但度量的三角不等式限制了這些邊的成本可以取多大。
我們將證明若干顯式的圖變換,並由此推出判定問題與近似方面的後果。作為已聲明的前置結論,我們使用至少有兩個頂點的簡單無環有向圖上有向哈密頓圈問題的標準 NP 完全性。本章不從 SAT 出發證明該前置結論,但會證明由它推出的每一個變換,並給出目標判定問題的證書。
定義
定義 4.5.1
(哈密頓路徑與哈密頓圈)
有向哈密頓圈是全體頂點的一個循環排列,其中每一對相鄰的有序頂點(包括首尾閉合的那一對)都是有向邊。有向哈密頓路徑是訪問每個頂點恰好一次且遵守邊方向的頂點序列。在無向簡單圖中,相應的路徑與圈使用無向邊。對於無向圈,我們只考慮至少三個頂點的情形,並要求它是簡單圈。
定義 4.5.2
(旅行推銷員例子、巡迴與度量成本)
這裏的對稱旅行推銷員例子是 個頂點上的完全無向圖,各邊帶有非負整數成本。巡迴是一個哈密頓圈,其成本是各邊成本之和。度量例子還要求對任意三個互異頂點都有 。判定版本詢問是否存在成本不超過某個整數閾值的巡迴。
定理 4.5.3
(路徑與無向圈)
有向哈密頓圈可在多項式時間內歸約到有向哈密頓路徑,也可歸約到無向哈密頓圈。下面的構造把「是」例子映到「是」例子,把「否」例子映到「否」例子。
定理 4.5.4
(成本為一和二的巡迴)
個頂點上的無向哈密頓圈可歸約到成本取值於 、閾值為 的度量旅行推銷員判定問題。對任意固定的有理數 ,若對任意非負對稱巡迴成本存在多項式時間的 -近似算法,則無向哈密頓圈存在多項式時間算法。
兩個定理的證明分別見下面各構造部分。
有向圈到有向路徑
在有向圖中選定一個頂點 。用新的起點 和新的終點 取代它。把每條原有邊 改為 ,把每條邊 改為 。保留其他頂點之間的所有邊。不添加任何進入 的邊,也不添加任何離開 的邊。
證明
(拆分一個頂點不改變是否存在哈密頓圈)
若原圖有哈密頓圈,則從 開始遍歷該圈,把開頭的 換成 ,把結尾處的閉合換成 ,便得到新圖中的一條哈密頓路徑。反之,新圖中的任意哈密頓路徑必以 開頭,因為 沒有入邊;也必以 結尾,因為 沒有出邊。把兩個端點合併為單一頂點 即閉合成原圖中的有向哈密頓圈。其他頂點各被訪問恰好一次,且每條被改向的邊都對應一條原有邊。
新圖只增加一個頂點,被改向的邊至多線性多條。該構造並不假定原圖中的任意哈密頓路徑都能閉合;它構造的是代表同一個原頂點兩側的兩個端點。
概念視角結構
哈密頓圈是置換的單一循環
以後繼映射 記錄有向哈密頓圈, 把每個頂點送到緊隨其後的頂點。這樣 是頂點集上的雙射,對每個 都有 為邊,而且 只有一個穿過所有頂點的循環;反過來,滿足這些條件的 就是哈密頓圈。去掉「只有一個循環」的條件,便得到覆蓋所有頂點的若干不相交有向圈,這只是一個普通的二分圖完美匹配問題。困難完全在於迫使它只有一個循環。
有向圈到無向圈
對每個有向頂點 ,建立三個無向頂點 ,以及內部邊 和 。對每條有向邊 ,添加一條無向邊 。不添加其他邊。
證明
(構件構造的正確性)
有向哈密頓圈給出無向哈密頓圈:把每個構件從入頂點經中間頂點走到出頂點,並取表示每次有向轉移的那條邊。反之,所構造無向圖中的任意哈密頓圈必須在每個中間頂點處同時使用它的兩條內部邊,因為該頂點的度為二。因此它把每個構件作為連續的「入—中—出」路徑走過,方向可以是正向或反向。
每條外部邊都連接一個出頂點和一個入頂點。若某個構件被正向(由入頂點到出頂點)遍歷,圈便從它的出頂點經外部邊離開,並在下一個構件的入頂點進入,所以下一個構件也被正向遍歷。同一論證說明反向遍歷之後接著的也是反向遍歷。因此所有構件的遍歷方向一致,必要時把整個圈反轉,便可假定全部都是正向。
此時所用的每條外部邊都形如 ,對應原圖的有向邊 。收縮各構件便得到有向哈密頓圈。構件共含 個頂點和 條邊,因此該變換是多項式的。有向環已被排除;反平行的有向邊會產生連接不同構件端點的兩條互異的無向外部邊。
證明透視
度數為二與出入配對用在哪裏
這個證明有兩個互相獨立的強制步驟。第一,中間頂點的度數為二,所以哈密頓圈必須使用它的兩條內部邊;這使每個構件成為連續的「入—中—出」路徑,並防止圈從同一個端點進入又離開構件。第二,外部邊只連接出頂點和入頂點,所以由某個構件的出頂點離開,下一次進入必然是在入頂點,遍歷方向不可能在構件之間翻轉。
兩個步驟缺一不可。若去掉中間頂點,圈可以在同一個入頂點使用兩條外部邊,而這種走法沒有對應的有向邊。論證最後把圈上每條外部邊讀作有向邊 ,便得到一個恰好經過每個原有頂點一次的有向圈。
兩個目標問題都屬於 NP:給定的頂點序列是否包含所需頂點、是否互異、相鄰頂點之間是否有邊,都可在多項式時間內檢驗。結合所聲明的有向圈前置結論,這些歸約證明了在上述約定下,有向哈密頓路徑和無向哈密頓圈都是 NP 完全的。
從哈密頓圈到度量巡迴
給定 的無向簡單圖 ,在同一頂點集上構造完全圖。原有的邊成本為一,非邊成本為二。三角不等式成立:每個成本至多為二,而經過另一個不同中間頂點的路線含兩條邊,每條成本至少為一。
證明
(成本一和二保持答案不變)
若 有哈密頓圈,則該圈作為巡迴的成本為 。反之,每個巡迴恰有 條邊,每條成本至少為一。成本至多為 的巡迴只能使用成本為一的邊,因此它是 的哈密頓圈。所以閾值 同時保持了兩種答案。給定的巡迴及其成本總和可在多項式時間內檢驗,結合前述前置結論與歸約,得到該度量判定問題是 NP 完全的。
即使輸入圖不連通,這些成本仍是度量的。此時完全巡迴例子依然存在;高成本的邊連接原圖中不相鄰的頂點。這些邊使巡迴成為可能,但當不存在僅由原有邊構成的圈時,它們會把巡迴成本推高到 以上。
任意巡迴成本下的間隔
證明
(常數倍近似算法會判定哈密頓圈)
固定有理常數 。這次給原有邊賦成本一,給非邊賦成本 。若存在哈密頓圈,則最優值恰為 。若不存在,則每個巡迴都使用某條成本為 的邊,其成本至少為 。
設有一個多項式時間算法,對這些非負例子總是返回成本至多為最優值 倍的巡迴。運行它,並把返回的整數成本與 比較。在「是」例子中,輸出成本至多為 ;在「否」例子中,每個可行輸出的成本都大於 。這就在多項式時間內判定了無向哈密頓圈。對固定的有理數 ,整數 的編碼長度是多項式的,且圖是完全圖,因此該變換是多項式的。
反例模式
間隔構造並不是度量例子
聲稱:以大成本 構造的例子是度量的,所以這個間隔也能排除度量巡迴的常數倍近似。在路徑 上取 來驗證。此時 ,故 ,而 。但 ,三角不等式不成立。只要兩個不相鄰的頂點有共同鄰點,對每個 都會出現同樣的失敗。因此間隔論證只適用於任意非負成本;成本一和二的例子是度量的,但它的「否」例子巡迴成本只保證至少為 。
結論是有條件的:除非 ,否則對任意對稱非負巡迴成本,不存在多項式時間的固定常數近似算法。這與度量巡迴的正面近似保證並不矛盾,後者的抄捷徑證明用到了三角不等式。
例題詳解
例題 4.5.5
(拆分有向圈)
對有向圈 ,把 拆分為 。新邊包括 、 和 ,給出哈密頓路徑 。把它的兩個端點合併回 ,便恢復原來的圈。
例題 4.5.6
(兩個頂點的有向圈)
設頂點 之間同時有有向邊 和 ,則無向構件構造給出六元圈 。方向相反的兩條有向邊變成兩條不同的外部邊,所構造的無向圖仍是簡單圖。
例題 4.5.7
(路徑圖上的度量成本)
設輸入圖為三個頂點的路徑 。其完全成本圖給 賦成本一,給 賦成本二。唯一的無向巡迴成本為四,大於閾值三,這與路徑圖沒有哈密頓圈相符。三角不等式在 上經由 取等號。
例題 4.5.8
(「是」例子的間隔)
對四個頂點的四元圈,成本為一的圈總成本為四。在取大 的構造中取 ,則 ,滿足所述因子的算法在這個「是」例子上必須返回成本至多為八的巡迴。在同樣規模的「否」例子中,每個巡迴的成本至少為十二。
常見錯誤
常見錯誤
(把歸約的方向讀反)
歸約的方向很重要。從問題 到問題 的多項式歸約,把 的求解器變成 的求解器;它本身並不能把 的求解器變成 的求解器。上面每個證明都給出了兩個方向的見證變換,使「是/否」等價性是顯式的。
常見錯誤
(沒有嚴格區分兩種情形的閾值)
判定閾值必須嚴格區分兩種情形。對於度量構造,每個巡迴有 條邊且成本至少為 ,所以閾值 恰好成立。對於近似間隔,僅僅選一個很大的數而不與 比較是不夠的。所選的 使「否」例子的下界嚴格大於「是」例子容許的最大輸出。
常見錯誤
(把閉合頂點算作兩次)
圈的證書按循環順序列出頂點,並可對照相應的邊或成本表示進行檢驗。它不需要把起點作為另一個頂點再列一次;回到第一個頂點的最後一條邊單獨檢驗。這樣可避免把重複書寫的閉合記號誤當作訪問了某個頂點兩次。
歸約的適用範圍
無向構件的證明依賴於中間頂點恰有兩條關聯邊這一事實。哈密頓圈必須使用這兩條邊,這就排除了從同一端點進入並離開構件的可能。外部邊的模式隨後使整個巡迴上各構件的方向同步。若只是為每個有向頂點畫三個頂點,而不證明這兩個事實,就無法排除虛假的無向圈。
旁註
先用度數檢驗構件
信任一個構件之前,先列出哈密頓圈在構件每個頂點上被迫採取的走法,從度數為二的頂點開始。固定了被迫使用的邊之後,才去問餘下的選擇在原圖中代表甚麼。
度量歸約只使用成本一和二,因此其二進制編碼特別小。然而這並不能給出常數因子的困難間隔:「否」例子中的巡迴成本可能只比 多一,比值 趨近於一。它證明的是精確判定的困難性。任意成本歸約之所以能產生更大的間隔,恰恰是因為它容許不滿足三角不等式的成本。
本章以有向哈密頓圈的 NP 完全性作為前置結論。這裏的證明建立的是下游的歸約和成員性證書,而不是從 SAT 出發的原始歸約。配套單元中針對哈密頓路徑的指數級子集動態規劃仍是有效的精確算法;NP 完全性僅在通常的複雜度假設下排除多項式時間算法。
總結
把指定的有向頂點拆分為被強制的路徑端點,或把每個有向頂點替換為三個頂點的無向構件。成本為一的原有邊與成本為二的非邊給出度量巡迴判定問題的歸約。更大的非度量間隔給出有條件的常數因子不可近似性結論,並明確指出三角不等式所帶來的限制。
練習
快速檢查
(在有向圖到路徑的變換中,為甚麼每條哈密頓路徑必須以 開始、以 結束?)
留意哪些邊進入 、哪些邊離開 。
解答 · 答案
沒有邊進入 ,所以它不能出現在其他路徑頂點之後;沒有邊離開 ,所以它不能出現在其他頂點之前。哈密頓路徑包含這兩個頂點。
快速檢查
(為甚麼無向構件圖中的任何哈密頓圈都必須包含 的兩條關聯邊?)
數一數 有幾個鄰點。
解答 · 答案
中間頂點恰好只有這兩個鄰點,而圈在其每個頂點上使用兩條不同的關聯邊。
快速檢查
(對於沒有哈密頓圈的五頂點圖,在成本一/成本二的構造中,每個巡迴的成本有甚麼下界?)
巡迴恰有五條邊。
解答 · 答案
每個巡迴有五條邊。原圖沒有哈密頓圈,所以這些邊中至少一條成本為二,其餘至少為一,故每個巡迴的成本至少為六。精確的最優值可以更大。
快速檢查
(對 、,在大間隔構造中計算 以及「否」例子的下界。)
用 ,並數一數巡迴的其餘邊。
解答 · 答案
。「否」例子中的任何巡迴都要用一條昂貴的邊,以及另外兩條成本至少為一的邊,所以成本至少為 ,大於 。