動機
假設若干工作必須分配給互不相同的工人,而每項工作都有一份可接受的工人名單。貪心地選取一名可用的工人,可能會堵住後面的工作,即使完整的分配方案其實存在。增廣路徑可以修正先前的選擇:它在未使用的邊與已使用的邊之間交替,把這些邊的狀態整體翻轉後,分配數恰好增加一。
對於二分圖,同樣的搜尋在無法繼續改進時還會給出一份證書。頂點覆蓋證明某個匹配是最大的,而一組有虧缺的工作則說明為甚麼不存在完整的分配。這些見證把算法給出的答案變成可以獨立檢驗的結論。
定義
定義 3.10.1
(二分圖、匹配與已匹配頂點)
設 為有限簡單二分圖,其左、右頂點集不相交,而且每條邊都連接兩側各一個頂點。匹配 中任意兩條邊都沒有公共端點。與 中某條邊關聯的頂點稱為已匹配頂點,否則稱為未匹配頂點。匹配的大小是其所含邊的條數。
定義 3.10.2
(增廣路徑)
對於 ,增廣路徑是一條簡單路徑:它從 中的一個未匹配頂點出發,終止於 中的一個未匹配頂點,並且在 以外的邊與 中的邊之間交替。它的第一條邊和最後一條邊都不在 中。翻轉路徑上每條邊的狀態,就是刪去路徑上屬於匹配的邊,並加入其餘的邊。
定義 3.10.3
(頂點覆蓋與鄰域)
頂點覆蓋是與每條邊都相交的頂點集合。對於 ,其鄰域 是與 中至少一個成員相鄰的頂點的集合。空圖與空匹配都是容許的;若 為空,則覆蓋 全部頂點的匹配平凡地存在。
定理
定理 3.10.4
(增廣路徑判準)
一個匹配是最大匹配,當且僅當它不存在增廣路徑。翻轉一條增廣路徑會得到一個多一條邊的匹配。
定理 3.10.5
(Hall 證書與匹配-覆蓋證書)
覆蓋 中每個頂點的匹配存在,當且僅當對每個 都有 。此外,每個有限二分圖都有一個頂點覆蓋,其大小等於最大匹配的大小。
證明
翻轉為何有效
證明
(翻轉增廣路徑令匹配增大)
增廣路徑以未匹配邊開始並以未匹配邊結束,而且兩種邊交替出現,因此它含有的 以外的邊比 中的邊恰好多一條。在內部頂點處,路徑上恰有一條邊屬於匹配、一條邊不屬於匹配,翻轉就是把兩者互換。在每個端點處,新加入的邊是唯一的匹配邊,因為該端點原先是未匹配的。路徑以外的頂點保持原來的狀態。所以翻轉後的邊集是一個大小為 的匹配。
證明
(沒有增廣路徑即為最大匹配)
最大匹配不可能有增廣路徑,因為翻轉會令它變大。至於反方向,把 與任意一個更大的匹配 比較。構造它們的對稱差:保留恰好屬於其中一個匹配的邊。在對稱差中每個頂點的度至多為二,而與它關聯的邊在 與 之間交替。每個連通分支要麼是交替路徑,要麼是交替圈,要麼是孤立頂點。圈中兩個匹配的邊數相等。路徑中一個匹配的邊數至多比另一個多一。
因為 ,所以某個分支路徑中 的邊比 的邊多一條。它兩端的邊都屬於 ,因此其端點在 下是未匹配的。在二分圖中,這條奇數長度的路徑兩個端點分別位於兩側;把它從 到 定向,它就是 的一條增廣路徑。因此,若不存在增廣路徑,則不存在更大的匹配。
證明透視
透過對稱差比較兩個匹配
這個證明只有一個想法:通過兩個匹配不一致的邊來比較它們。每個頂點至多關聯 的一條邊和 的一條邊,所以它在對稱差中的度至多為二,連通分支因此只能是路徑或圈。沿著路徑或圈,邊在 與 之間交替,所以圈中兩個匹配的邊數相等,不可能解釋 的盈餘。盈餘只能出現在路徑上,而一條路徑至多多出一條邊。多出一條 邊的路徑,兩端的邊都屬於 。 中沒有邊可以與它的端點相交:這樣的邊若不同時屬於 ,便是該端點的第二條 邊;若同時屬於兩個匹配,它就不在對稱差之中。所以兩個端點在 下都是自由的。二分性只在最後一步使用,用來說明奇數長度的路徑兩端分屬兩側。若沒有 這個假設,對稱差可以只由圈和兩邊平衡的路徑組成,也就不能保證存在改進。
搜尋與最優性證書
從任意匹配出發,把每條未匹配邊定向為從 到 ,把每條匹配邊定向為從 到 。從所有未匹配的左頂點出發搜尋這個有向圖。若到達某個未匹配的右頂點,則由前驅指標給出一條增廣路徑。翻轉它,然後重複。每次翻轉都令匹配的大小增加,因此至多發生 次翻轉。使用鄰接表時,一次搜尋需要 時間,於是包括最後一次搜尋在內的總時間為 。
證明
(失敗的搜尋給出同樣大小的覆蓋)
設最後一次搜尋沒有找到未匹配的右頂點。令 與 分別為兩側被到達的頂點。定義
這是一個頂點覆蓋。考慮邊 。若 ,則其左端點屬於 。若 而且該邊是未匹配的,則有向搜尋會到達 。若該邊是匹配邊,則被到達的已匹配左頂點必定是沿著它唯一的匹配邊從它的配偶 到達的;未匹配的根沒有與之關聯的匹配邊。因此無論哪種情形都有 ,該邊被覆蓋。
中的每個頂點都是已匹配的,因為到達未匹配的右頂點就會給出一條增廣路徑。它的配偶位於 中。反過來,由同樣的搜尋論證, 中每個已匹配頂點的配偶都位於 中。一條匹配邊要麼兩個端點都被到達,要麼都沒有被到達。因此覆蓋 恰好含有 中每條邊的一個端點,並且不含任何未匹配頂點:它的大小恰好是 。
任何頂點覆蓋的大小都不小於任何匹配的大小,因為不同的匹配邊需要不同的覆蓋頂點。於是 與 互相證明對方的最優性。這就在不預先假定的情況下證明了定理中的匹配-覆蓋部分。
反例模式
貪心分配可能卡住
設 ,,邊為 。貪心地選取 會令 未匹配。交替路徑 翻轉舊邊 ,並加入 ,得到大小為二的匹配。
閱讀證書
最後一次搜尋有兩種可能的用途。若它到達某個未匹配的右頂點,則前驅連結給出一串具體的邊變更。若沒有到達,則被到達的集合給出一個覆蓋,而且當某個左根仍未匹配時,還給出一個有虧缺的鄰域。這是同一次探索的不同結果。驗證者不必信任搜尋的實作:他可以直接根據圖檢驗匹配、覆蓋和鄰域的斷言。
概念視角算法
把匹配看作整數單位流
最大匹配也可以由單位容量的流構造得到:把源點連到每個左頂點,把每條原有的邊從左向右定向,並把每個右頂點連到匯點。一個整數的單位流選出一條邊,兩端的單位容量則防止兩條被選出的邊共享一個頂點。上面的交替路徑正是這個特定網絡中的殘量增廣路徑。這裏的直接證明額外提供了 Hall 見證,並使先前分配的撤銷清晰可見。
定義 3.10.6
(極大匹配)
極大匹配是指沒有任何邊可以直接加入而仍保持匹配性質的匹配。每個最大匹配都是極大的,但反過來不成立,貪心的例子就說明了這一點: 是極大的,因為其餘兩條邊都碰到已匹配的端點,然而翻轉一條交替路徑卻得到兩條邊。因此,對單條邊的局部檢查不能代替增廣路徑判準。
反例模式
覆蓋等式不能去掉二分性
在一般圖中,最大匹配與最小頂點覆蓋的大小可以不同。取以 為頂點、邊為 的三角形。其中任意兩條邊都有公共頂點,所以匹配至多含一條邊。單獨一個頂點只與三條邊中的兩條相交: 沒有覆蓋 , 與 同理。因此每個覆蓋至少需要兩個頂點,而 就是一個覆蓋。最大匹配的大小為一,最小覆蓋的大小為二。三角形含有奇圈,不是二分圖,定理中的等式在這裏不成立。
Hall 條件的證明
證明
(由失敗的搜尋得出 Hall 條件)
若某個匹配覆蓋 ,則任意 中的不同頂點被匹配到 中不同的頂點。因此 是必要的。
對於充分性,取一個最大匹配,並假設它令某個左頂點未匹配。運行最後一次交替搜尋。集合 至少含有一個未匹配的根。被到達的左頂點的每個鄰點在右側都被到達:未匹配邊沿正向被遍歷,而被到達的已匹配左頂點的匹配邊通向已經被到達的、發現它的那個右頂點。反過來,每個被到達的右頂點都是從 中的某個左鄰點到達的。因此 。
的所有頂點都被匹配到 中互不相同的頂點。被到達的左側還至少含有一個未匹配的根,所以 。這是對 Hall 條件的明確違反。其逆否命題證明了充分性,並且每當不存在覆蓋左側的匹配時,都給出一個可檢驗的虧缺集合。
證明透視
最大性只用來使搜尋失敗
充分性只用了一次最大匹配:它保證最後一次搜尋會失敗。失敗表示沒有到達未匹配的右頂點,所以 中每個頂點都有配對對象,而這個對象也被到達。於是 中已匹配的頂點與 的頂點一一對應,再加上未匹配的起點,便得 。搜尋對遍歷封閉,故 ,此計數即成為對明確集合 的 。違反條件的集合是從失敗的搜尋讀出的,並非靠枚舉找到。
該條件適用於 的每個子集,而不僅僅是單個頂點。每項工作至少有一名可接受的工人,並不保證所有工作能同時得到分配。一組工作合起來可能可選的工人太少。
例題詳解
例題 3.10.7
(修復一個貪心匹配)
對於 , 以及邊 ,從 開始。從未匹配的 出發搜尋:沿正向遍歷 ,沿反向遍歷匹配邊 ,再沿正向遍歷 。頂點 是未匹配的。翻轉後得到 ,它覆蓋了兩個左頂點。
例題 3.10.8
(一個 Hall 障礙)
設 ,,其中 和 只與 相鄰, 與 和 相鄰。每個左頂點都有鄰點,但 的 。因為 ,所以不存在覆蓋 的匹配。匹配 是大小為二的最大匹配。
例題 3.10.9
(覆蓋證明最大大小)
對於上一個圖, 覆蓋所有邊,大小為二。匹配 的大小也是二。任何匹配的邊數都不可能超過頂點覆蓋的頂點數,因此無需枚舉所有可能的匹配,兩者都是最優的。
例題 3.10.10
(某一側可以為空)
若 而 是任意有限集合,則空匹配覆蓋 的每個頂點。Hall 條件只有子集 ,此時 。空的頂點覆蓋也是最優的,因為沒有邊。
常見錯誤
常見錯誤
(交替不等於增廣)
交替路徑並不自動是增廣路徑:它的兩個端點都必須是未匹配的,這樣才會含有比已使用的邊多一條的未使用邊。在貪心例子中取 ,路徑 是交替的,但它的端點 是已匹配的。翻轉後 被 取代,大小仍是一。同樣,翻轉交替圈只會改變被選中的邊,不會令匹配變大。
常見錯誤
(大小相等本身不構成最優性證書)
只有當所提出的集合確實與每條邊都相交時,匹配-覆蓋證書才成立。在邊為 的圖中,集合 與匹配 大小相同,卻漏掉了 ,所以它不是覆蓋。應當先驗證該邊集是匹配,再檢驗覆蓋性質,最後才比較大小。
常見錯誤
(Hall 條件針對子集,而不是單個頂點)
只檢查每個左頂點都有鄰點,會遺漏不同左頂點之間的衝突。在同一個圖中,、、 各自都有鄰點,但 的 。當最大匹配沒有覆蓋左側時,交替搜尋會給出一個具體的違反條件的子集;要得到這份證書,無需枚舉所有子集。
總結
增廣路徑提供局部改進,而對稱差證明了此類路徑的缺失在全局上是決定性的。最後一次交替搜尋給出與匹配大小相同的頂點覆蓋。若某個左頂點仍未匹配,則被到達的左集合的鄰點太少,從而給出 Hall 障礙。這些證書既解釋了分配的成功,也解釋了它的失敗。
練習
快速檢查
(在貪心的例子中,寫出翻轉路徑 之前和之後各條邊的狀態。)
把 、、 三條邊逐條列出。
解答 · 答案
起初 是已匹配的,而 與 是未匹配的。翻轉後刪去 ,並加入 與 ,所以之後 未匹配, 與 已匹配。結果是大小為二而不是一的匹配。
快速檢查
(設三個左頂點都只與兩個右頂點相鄰。給出一個 Hall 障礙,並給出匹配大小的一個上界。)
試取 為整個左側。
解答 · 答案
取 為全部三個左頂點。它的鄰域至多有兩個頂點,因此 。匹配的每條邊使用不同的右端點,所以匹配的大小至多為二。
練習 3.10.11
(同一個圖中的匹配 與頂點覆蓋 滿足 。證明 是最大匹配, 是最小頂點覆蓋。)
核心證明
兩個集合都在同一個圖中,只知道它們的大小。
提示(1)
匹配中不同的邊沒有公共端點,所以覆蓋要為每條匹配邊各用一個不同的頂點。
解答(3)
- 1
比較任意匹配與任意覆蓋
關鍵一步
對圖中任意匹配 與任意頂點覆蓋 ,
依據: 不同的匹配邊沒有公共端點,而每條邊都需要一個覆蓋頂點。
- 2
給每個覆蓋一個下界
取 ,得到對每個覆蓋 都有 。由於 ,覆蓋 的大小已是最小可能值。
- 3
給每個匹配一個上界
∎取 ,得到對每個匹配 都有 。由於 ,匹配 是最大匹配,而 是最小頂點覆蓋。
快速檢查
(若一個匹配覆蓋 的所有頂點,解釋為甚麼每個子集 至少有 個鄰點,包括 的情形。)
把 的每個頂點送到它的配偶。
解答 · 答案
該匹配把 的每個頂點送到不同的右鄰點,給出從 到 的單射。因此 。對於空集,這是成立的不等式 。