動機
添上一條缺失的邊,可能令哈密頓(Hamilton)圈更容易被看出來,卻並不改變哈密頓圈是否存在。如果這條邊的兩個端點的度之和已經足夠大,那麼一個使用了新邊的圈可以被修補成只使用舊邊的圈。反覆進行這種安全操作,就得到一個閉包圖。
閉包亦解釋了一個透過排序度序列表述的、不那麼明顯的充分條件。一個封閉的非完全圖必然在互補的位置上顯露出一對度數不足。如果原圖的度序列排除了每一種這樣的不足,那麼閉包就是完全圖,原圖是哈密頓圖。
下文的判據都是充分性證書;閉包不完全,或度檢驗失敗,都不被當作哈密頓性的完整否定判定。
定義
定義 4.2.1
(安全加邊與閉包)
設 是 個頂點上的有限簡單無向圖。哈密頓圈恰好訪問每個頂點一次,然後回到起點。對於不相鄰的一對頂點 ,當它們的當前度滿足 時,可進行一次合資格的閉包加邊,即連接 。
重複進行合資格的加邊,直至不再有可加的邊為止。處於此停止點的圖稱為閉的:每一條剩餘的非邊,其端點度之和至多為 。度數和合資格性是在演化中的圖裏重新計算的,而不是固定在初始值上。
定義 4.2.2
(度序列條件)
把原圖的度按非遞減次序寫成 。本筆記中的度序列條件是:對每個滿足 的整數 ,
這兩個選項屬於同一個指標檢驗;要求兩者同時成立,會是比定理所用條件更強的條件。該序列只記錄度數,而不記錄哪些頂點具有這些度數。
定理/命題
引理 4.2.3
(合資格的邊在兩個方向上都保持哈密頓性)
若 不相鄰且 ,則 是哈密頓圖當且僅當 是哈密頓圖。使用新邊的哈密頓圈,可以沿所得的生成路徑透過兩條交叉邊顯式地轉化為 中的哈密頓圈。
定理 4.2.4
(閉包與加邊次序無關)
所有極大的合資格加邊序列都得到同一個最終圖,即 的閉包。圖與其閉包同為哈密頓圖或同不為哈密頓圖。特別地,完全的閉包證明了哈密頓性,並可由此還原原圖中的一個圈。
用鄰接矩陣的直接構造需要 次初等運算;一旦給出閉包中的一個圈,保存加邊歷史即可在額外 的工作量內還原原圖中的圈。這些是初等界,並不是最快實現的斷言。
定理 4.2.5
(度序列條件保證存在哈密頓圈)
每個階數至少為三且滿足上述排序度條件的有限簡單圖都是哈密頓圖。該條件在加邊下是單調的,並且迫使其閉包為完全圖。
作為推論,最小度至少為 蘊含哈密頓性,因為它使第一個選項在每個所需指標上都成立。度序列條件不成立,並不一定意味著哈密頓性不成立。
概念視角結構
閉包強化了表示,同時保持一個是非性質不變
安全加邊可能改變圖的許多特徵,但保持哈密頓性。度序列提供了一個單調的充分檢驗,迫使這一被強化的表示變為完全圖。正面的閉包證書可透過局部修補轉移回原圖;而否定性的結果沒有可與之相比的、通向非哈密頓性的一般轉移。
證明思路或證明
證明
(兩條交叉邊把生成路徑閉合)
加邊引理的一個方向是顯然的:舊的哈密頓圈在擴大後的圖中仍然存在。對於逆命題,取 中的一個圈。若它不含新加的邊,則無需修補。否則去掉該邊,得到一條生成路徑
其所有的邊都屬於 。
在指標集 中,令 由使 與 相鄰的指標 組成, 由使 與 相鄰的指標組成。它們的大小分別是 和 :路徑列出了所有頂點,而缺失的邊使相對的端點不出現在任一鄰點列表中。
它們的總大小至少為 ,超過了可用的 個指標,所以必有某個指標同時屬於兩者。該指標不可能是 或 ,否則就需要用到缺失的邊。因此序列
是 中的哈密頓圈。它的兩條交叉邊來自這個交集,其餘每條邊都屬於該生成路徑。所有頂點在返回之前恰好出現一次。這樣便構造性地證明了局部等價。
證明透視
鄰點指標集必須在生成路徑上重疊
度的假設只在從圈中去掉新加的邊之後才被使用。剩下的是一條生成路徑 ,其邊都屬於 ;只有沿這樣的路徑,鄰點才能轉化為指標。關鍵的一步是錯開一位: 的鄰點 記在指標 , 的鄰點 也記在指標 。於是一個共同指標同時給出兩條交叉邊 與 ,再把 這一段反轉,圈便閉合。
抽屜計數 正是門檻發揮作用之處。 不相鄰這一點,用來排除共同指標為 或 ,因為兩者都需要缺失的邊。門檻不能降到 :在路徑 中,兩端點的度之和為 ,加入 得到三角形,但路徑本身沒有哈密頓圈。
為甚麼最終的閉包不依賴於選擇
證明
(每個閉的母圖都包含每次合資格的加邊)
每次加邊都使度增加,而缺失的邊只有有限條,所以每個合資格加邊序列都會終止。每一步由引理都保持哈密頓性。
設 是任意與原圖同頂點且包含其全部邊的閉圖。任何合資格序列中所加的每條邊都必須屬於 。沿該序列用歸納法證明這一點。較早加入的邊由歸納假設屬於 ,因此 中的度至少與下一條邊變為合資格時的度相同。若該下一條邊不在 中,則它在 中的端點度之和仍然至少為 ,這與 是閉的矛盾。
把此結論應用於取 為另一序列的最終圖。每個最終閉包都包含於另一個之中,從而相等。這亦證明了閉包是一個良定義的圖運算,而不僅僅是某一次任意執行的結果。
維護度數和鄰接矩陣。對至多 個頂點對作一次完整掃描,可找到一條合資格的非邊,或證明不再有這樣的邊。加入它,更新它兩個端點的度,然後重複。至多有 次加邊,包括最後一次掃描在內總共需要 的工作量。矩陣使用 的儲存,加邊歷史的大小量級相同。
如果閉包是完全圖,則從其頂點的任一循環排列出發。按相反次序處理各次加邊。在每一步,從當前圖中刪去記錄的那條邊。若當前的圈不含它,則保留該圈。否則,在剛好加入該邊之前的圖中,應用引理中的路徑修補。之後所有的加邊都已被刪去,因此修補只使用當前合法的邊。藉助矩陣查詢,檢驗並重建一個圈及其交叉指標需要 的工作量,在整個歷史上總共為 。
封閉的非完全圖顯露出被禁止的度模式
證明
(度之和最大的非邊令兩個選項都不成立)
首先,加邊時排序度條件得到保持。每個頂點的度都增加或保持不變,因此每個排序後的次序統計量也是如此。例如,若新的第 小度小於舊的,則至少有 個頂點的新度低於該舊的閾值,而其中沒有任何度減小;這與舊的排序矛盾。因此條件中的每個析取式仍然成立。
假設閉包 不是完全圖。若它有孤立點,則每個度至多為 。在指標 處,第一個選項不成立,所要求的 同樣不成立。因此滿足該條件的圖不可能出現這種情形。
否則,選取度之和最大的一對不相鄰頂點 ,並標記使得 。不存在孤立點,所以 。閉性給出 ,從而 。
的每個非鄰點(不含 自身)的度至多為 。若度更大,就會產生一條度之和比所選頂點對更大的非邊。這樣的頂點有 個。因此 中第 小的度至多為 。
同樣, 的每個非鄰點的度至多為 。這樣的頂點有 個;再加上 自身,其度 同樣至多為 。我們至少有 個度至多為 的頂點,所以第 小的度小於 。
度檢驗的兩個選項在被允許的指標 處都不成立。這與原條件在取閉包下的保持性相矛盾。因此閉包必為完全圖,再由局部等價定理,得到原圖中的哈密頓圈。
最小度推論現在直接得出:若每個度都至少為 ,則對每個 ,連第 小的度也大於 。這樣便透過更強的排序序列論證還原了該充分條件,而不必把它當作未經證明的前提。
證明透視
為甚麼要在閉包中找矛盾
證明從不在原圖中尋找不合格的指標。它先說明條件在每次加邊後都保持,因此在閉包 中仍成立,而 具有閉性可用。真正的想法是選取度之和最大的非邊 :極大性把非鄰點轉化為度的上界, 的非鄰點度至多為 , 的非鄰點度至多為 。
閉性 一式兩用:它保證 至少有 個非鄰點;配合 ,又得到 ,所以 正是條件要檢驗的指標。另行處理孤立點的情況,只是為了保證 。
例題詳解
例題 4.2.6
(初始非邊和檢驗失敗時,閉包仍可成功)
取 上的五頂點團,刪去邊 ,再添加第六個頂點 ,它只與 相鄰。排序後的度為 。非邊 的初始度之和為五,低於階數六,所以要求每條原有非邊都滿足該界的條件不成立。
然而 是合資格的,因為它的度之和為六。加入它之後, 的度為三,所以 和 可以加入;最後 也變為合資格。閉包是完全圖。度序列檢驗同樣成功:僅有的指標是一和二,相應的度都大於這些指標。原圖的一個哈密頓圈是 。
例題 4.2.7
(孤立點給出明確的早期序列失敗)
取五個頂點上的團加一個孤立點,總階數為六。其序列為 。在指標一處,第一個選項不成立,因為零不大於一;第二個選項也不成立,因為第五個度是四而不是至少為五。
每條非邊都連接孤立點與一個度為四的頂點,所以沒有一條是合資格的。閉包仍不完全,並且該圖不是哈密頓圖,因為孤立點不可能位於生成圈上。在這裏,兩個否定性檢驗與另一個直接的障礙一致;這種一致並不是一般的逆定理。
例題 4.2.8
(把某一條具體的新加邊修補回原圖)
在第一個圖中,只添加 。擴大後的圖有圈 ,它使用了該新邊。去掉它得到生成路徑 ,其端點為 ,另一端點按引理的記號為 。
沿該帶指標的路徑,首端點的鄰點指標集為 ,末端點的為 。它們共有的指標三給出修補後的圈 。所列的每條邊都屬於原圖;新加的邊 已經消失。
對於更長的加邊歷史,把同樣的修補按相反次序逐邊應用。所維護的圈始終屬於當前的圖,所以最終輸出只使用原有的邊,而不會把閉包中的邊當作一直存在的邊。
常見錯誤
反例模式
非完全的閉包本身也可能是哈密頓的
五圈的每個頂點的度都是二。每條非邊的度之和為四,低於五,所以其閉包不變且不完全。然而該圖本身就是一個哈密頓圈。它的度序列檢驗在指標二處同樣失敗:第二個度不大於二,且第三個度低於三。兩個檢驗都是充分的,而不是必要的。
常見錯誤
(把初始度數凍結)
檢驗加邊時要使用當前的度。在第一個例題中, 起初度之和為五,未通過檢驗;要等 把 提高到三之後,它才變為合資格。
常見錯誤
(把析取當成硬性要求)
不要把度序列的兩個選項與對較大指標度的無條件要求互換。在最小度至少為 時,第一個選項在每個指標都成立,對 根本沒有任何要求。
常見錯誤
(沿非生成的路徑修補)
去掉所加的圈邊而得到的生成路徑,對於修補是必不可少的;任意的圖路徑未必包含所有頂點,把它閉合得到的圈會遺漏一些頂點。
總結
較大的端點度之和使得添加一條缺失的邊對哈密頓性是安全的。反覆加邊得到與次序無關的閉包,並可構造性地還原圈。任何封閉的非完全圖中度之和最大的非邊,都迫使出現被禁止的排序度模式,由此證明了完整的度序列條件,並說明了失敗檢驗的局限。
練習
快速檢查
(直接證明:最小度至少為 使度序列條件中的每個指標檢驗都成立。)
所需的指標嚴格小於 。
解答 · 答案
每個排序後的度都至少為最小度,因而至少為 。對每個允許的整數 ,這使得 。因此第一個選項成立,無需檢查第二個。度序列定理在此假設下證明了哈密頓性。
快速檢查
(為甚麼添加其他合資格的邊永遠不會使先前合資格的缺失邊變為不合資格?僅憑這一點能證明每個停止圖都相同嗎?)
第一個問題用度的單調性,第二個問題用同頂點閉圖的包含關係。
解答 · 答案
加邊不會使任一端點的度減小,所以合資格的邊在被加入之前一直保持合資格。要證明停止圖的唯一性,須與任意與原圖同頂點且包含其全部邊的閉圖作比較。歸納地,它必須包含合資格序列中的每條邊,否則其端點的度就會與閉性矛盾。取兩個停止圖分別作為比較的閉圖,即證明相互包含。單調性提供了度的比較;閉性提供了矛盾。
快速檢查
(在最大和非邊的證明中,分別解釋為甚麼至少有 個度至多為 ,以及為甚麼至少有 個度至多為 。)
分別數這兩個不同所選頂點的非鄰點; 自身只在第二次計數中計入。
解答
因為 ,頂點 至少有 個非鄰點。每一個的度至多為 ,否則它與 構成的頂點對會超過所選的最大和。這給出第一個次序統計量的界。
頂點 有 個非鄰點,由同樣的極大性,每個的度至多為 。再加上 自身,因為 ,其度 不大於 。這給出 個符合條件的頂點和第二個次序統計量的界。二者合起來在指標 處使兩個選項都不成立。