動機
一組各自可接受的分配,未必能夠同時實現。若干請求可能在爭奪過少的可選項。匹配記錄的是沒有公共端點的分配。核心問題是:一次失敗的嘗試,揭示的是真正的資源短缺,還是僅僅源於先前的一個不佳決定。
交錯路徑能夠區分這兩種情況。它可以撤銷部分已選定的分配,同時使總分配數多出一個。如果不存在這樣的改進,那麼這次失敗的搜尋本身就會指出一個鄰點過少的集合,並構造出一個最小頂點覆蓋。因此,同一個論證既解釋了一個算法、一個存在性定理,也解釋了兩個最優化問題之間的等式。
定義
定義 6.1.1
(匹配與頂點覆蓋)
有限簡單圖中的匹配 是一個邊集,其中各邊的端點兩兩不相交。若 中有一條邊與某頂點相交,則稱該頂點被 飽和。最大匹配的大小是可能的最大值;極大匹配則不能透過添加單獨一條邊而擴大。完美匹配飽和每一個頂點。頂點覆蓋是與每條邊都相交的頂點集。
二部圖帶有指定的不相交頂點劃分 ,且每條邊都連接兩個部分。對於 ,其鄰集為 。當兩部分大小不同時,飽和 的匹配不一定飽和 。
定義 6.1.2
(交錯路徑與增廣路徑)
相對於匹配 ,交錯路徑的邊在 之外與 之內交替出現。增廣路徑的頂點互不相同,起點和終點都是未飽和的頂點,並且其第一條和最後一條邊都不屬於 。因此它含有奇數條邊,且 之外的邊比 之內的邊多一條。
把增廣路徑上屬於匹配的邊替換為該路徑上的其餘邊,稱為增廣。內部頂點仍然保持飽和,兩個端點變為飽和,路徑之外的頂點不變。這些局部事實說明,增廣會產生另一個匹配,並且恰好大一個單位。
定理/命題
定理 6.1.3
(增廣路徑判據)
有限圖中的一個匹配是最大匹配,當且僅當相對於它不存在增廣路徑。這一判據不要求圖是二部圖。
定理 6.1.4
(Hall 條件)
部分為 的有限二部圖存在飽和 的匹配,當且僅當對每個子集 都有 。空子集也包括在內,且自動滿足該不等式。
定理 6.1.5
(König 匹配–覆蓋等式)
在有限二部圖中,匹配的最大大小等於頂點覆蓋的最小大小。更確切地說,一個最大匹配可透過下面證明的交錯可達性構造,確定一個大小相同的覆蓋。
證明思路或證明
證明
(用對稱差比較兩個匹配)
增廣路徑會使匹配變大,所以最大匹配不可能有增廣路徑。反之,假設匹配 小於另一個匹配 。考慮邊集為 的圖,即恰好屬於二者之一的邊。每個頂點的度至多為二,每個非平凡連通分支都是邊類型交替出現的路徑或圈。圈中兩種類型的邊數目相等。由於 ,某條路徑所含的 邊比 邊多一條,它以 邊開始並以 邊結束。
它的端點未被 飽和。端點不可能在對稱差中還有另一條 邊,因為它在對稱差中是端點。它也不可能有一條 與 共有的邊,因為與它相連的 邊已經屬於該路徑,而 是匹配。因此這條路徑是 增廣路徑,判據得證。
證明
(交錯可達性給出 Hall 證據與覆蓋)
對於二部圖的結論,取一個最大匹配 ,並令 為 中未飽和的頂點。把每條未匹配的邊從 指向 ,把每條已匹配的邊從 指向 。令 分別為在兩個部分中從 出發可達的頂點,並容許根處的長度為零的可達。
中沒有未飽和的頂點:通向這樣一個頂點的有向路徑將是增廣路徑。因此 中每個被到達的頂點都是已匹配的,並且它的匹配夥伴在 中。反過來, 中每個頂點都是經由它的匹配邊到達的,所以它的夥伴在 中。匹配在這兩個集合之間建立一一對應,得到
此外 。每個被到達的右側頂點都是從某個左側鄰點到達的。從被到達的左側頂點出發的每條未匹配邊都可以被沿用;其匹配邊(若存在)通向的右側頂點,正是到達該左側頂點時所經過的那個右側頂點。因此它的所有鄰點都被到達。
Hall 條件的必要性是直接的:飽和 的匹配把任意 中互不相同的頂點送到互不相同的鄰點。對於充分性,若 非空,則所構造的集合滿足
這與 Hall 條件矛盾。因此 飽和 。
最後令 。左端點在 之外的邊在該端點處被覆蓋;左端點在 中的邊,其右端點在 中。所以 覆蓋每一條邊。它的大小為
任何覆蓋都至少要為每條匹配邊各取一個互不相同的頂點,所以沒有覆蓋能比匹配更小。所構造出的等式證明了 König 定理。
證明透視
極大性與二部性在哪裏進入
二部圖的證明恰好只用一次 的最大性:沒有被到達的右側頂點是未飽和的,否則搜尋就已找到增廣路徑。其餘一切都來自定向。未匹配的邊由 指向 ,匹配邊指回來,所以被到達的右側頂點只能沿其匹配邊離開;這給出 與 之間的配偶雙射,從而 。可達性的封閉性給出 ,而這一個等式一身兩用。當 時,它使 成為 Hall 虧量集;讀作「沒有邊從 通往 」,它又使 成為覆蓋。二部性使一個定向就能記錄交錯;在一般圖中,一個頂點可以在兩種奇偶性下都被到達,配偶雙射便不再成立。
例題詳解
例題 6.1.6
(一個可以修復的極大匹配)
令 ,,邊為 。匹配 是極大的:不與已有端點共享就無法再添加任何剩餘的邊。然而 是一條增廣路徑。把 替換為 ,就得到大小為二的匹配。這一修復暫時撤銷了先前的一個分配;只容許添加的規則會錯過它。
例題 6.1.7
(虧量集與最小覆蓋)
令 ,,邊為 。集合 只有鄰點 ,所以沒有匹配能飽和 。取 。從根 出發做交錯可達,得到 和 。所得覆蓋為 ,大小為二。這既證明了 是最大匹配,也證明了該覆蓋是最小的。整個左側集合有三個鄰點,所以只檢查整個集合會錯過這個障礙。
例題 6.1.8
(每個正度正則二部圖都有完美匹配)
設一個有限非空二部圖是 正則的,其中 。從兩個部分分別數邊,得 ,所以兩部分大小相等。對任意 ,恰有 條邊從 出發,且都終止於 ;而 的頂點總共至多關聯 條邊。因此 。由 Hall 定理,存在飽和 的匹配;兩部分大小相等使它成為完美匹配。正性條件使我們能約去 ,並排除了孤立頂點導致的反例。
為甚麼對稱差是恰當的比較方式
僅比較匹配的大小,只能說明存在改進,卻無法說明如何找到或理解它。對稱差去掉了兩個候選匹配已經一致的邊。剩下的部分具有剛性的局部結構,因為兩個匹配都不會在同一頂點上使用兩條邊。度至多為二迫使它們成為路徑和圈,而邊類型的交替使得對它們大小之差的計算很簡單。
含兩種類型的邊數目相同的路徑,僅僅是交換了分配。圈也一樣。只有較大匹配的邊多一條的路徑才能增加基數。這就是為甚麼一次改進可能需要多次反轉,卻從不需要任意分叉的重排。增廣路徑把比較中有用的一個分支分離了出來。
該判據在所有有限圖中證明了最優性,但高效地搜尋增廣路徑在二部圖中更容易。在那裏,固定的劃分和邊的定向使得直接的可達性搜尋得以組織起來。在非二部圖中,奇數交錯結構可能使樸素搜尋不夠用。定理依然成立;需要額外假設的是簡單的二部圖搜尋過程。
把證明變成算法
從空匹配開始。在有向交錯圖中,從所有未飽和的左側頂點出發搜尋。如果到達了一個未飽和的右側頂點,就利用父指標提取出一條簡單有向路徑並增廣。為新匹配重建定向,然後重複。每次增廣使邊數增加一,所以增廣次數至多為較小部分的大小。
如果沒有到達任何未飽和的右側頂點,同樣的可達集證明會構造出一個與當前匹配同樣大小的覆蓋。因此停止條件證明了最大基數;它並不僅僅是某個特定貪心選擇的失敗。特別地,先前的一個不佳分配可以在之後的搜尋中被糾正,正如第一個例子所示。
使用鄰接表時,每次搜尋需要 時間,包括初始化可達性數據。重複進行就得到一個直接的界 。這是該初等算法的界,而不是二部匹配已知的最佳界。當存在許多孤立頂點時,保留頂點項是有意義的。更稠密的表示可以改變搜尋成本,儘管證明並不改變。
度量必須有多少請求保持未分配
定義最大虧量為 的子集上 的最大值。它是非負的,因為空集給出零。對於任何匹配和任何這樣的子集,至多只有與其鄰點數相同的頂點能被匹配,所以至少有與其虧量相同數目的左側頂點必須保持未匹配。
對於最大匹配,交錯可達集達到這個下界。被到達的左側頂點、被到達的右側頂點與未匹配的根之間的等式表明,它的虧量恰好等於未匹配左側頂點的數目。因此
Hall 定理恰好是虧量為零的情形。這個公式還解釋了為甚麼失敗證書可以比是或否的回答更有資訊量:它量化了不可避免的短缺。不需要假設兩個部分大小相等。
概念視角結構
一個可行構造與一個普遍的界相遇
匹配展示了可以共存的分配。覆蓋則為每個匹配給出了上界,因為每條互不相交的邊都需要各自的覆蓋頂點。找到大小相同的兩者,就證明了兩側的最優性。虧量子集給出另一個上界,它指出了爭奪過少鄰點的那些請求。這些都是可檢驗的證書,而不是對搜尋歷史的訴諸。
覆蓋、獨立集與二部性的作用
頂點覆蓋的補集是獨立集:兩個端點都在覆蓋之外的邊將不會被覆蓋。反過來,獨立集的補集覆蓋每一條邊。因此在任何有限圖中,最大獨立集的大小加上最小覆蓋的大小等於頂點數。與 König 定理結合,這可以由一個匹配及其覆蓋算出二部圖中獨立集的最優值。
這一推論並不能使獨立集在所有圖中都變得容易。覆蓋與獨立集互補的等式是普遍成立的,而覆蓋大小與匹配大小相等則專屬於二部圖。把這兩個適用範圍區分開,可以防止把一個有效的等式用來把某種最優化方法推廣到其假設之外。
常見錯誤
反例模式
匹配–覆蓋等式在三角形上不成立
三角形的最大匹配大小為一,因為任意兩條邊都共享一個頂點。它的最小頂點覆蓋大小為二:一個頂點會漏掉對邊,而任意兩個頂點則覆蓋全部三條邊。因此兩個最優值不同。二部性對 König 等式是必要的,儘管每個匹配仍然受每個頂點覆蓋所限制。
常見錯誤
(整體平衡不蘊含 Hall 條件)
Hall 條件要對待飽和一側的每個子集進行檢驗。兩部分大小相等、邊的總數足夠多或沒有孤立頂點,都是不充分的。第二個例子中的虧量對沒有孤立頂點,而且整側鄰點計數發現不了它。
常見錯誤
(頂點覆蓋不是邊覆蓋)
頂點覆蓋是與每條邊相交的頂點集合;邊覆蓋則是與每個頂點相交的邊集合。兩者是不同的最優化問題。在邊為 的路徑上, 是大小為一的最小頂點覆蓋,而每個邊覆蓋都需要兩條邊,因為 只在 上, 只在 上。
總結
增廣透過交換交錯邊來修復匹配。對稱差證明了不存在增廣路徑刻畫了最大基數。在二部圖中,交錯可達性同時給出了 Hall 短缺的證據和與匹配同樣大小的覆蓋,從而以構造性的方式建立了 Hall 定理和 König 定理。
練習
快速檢查
(對於左側頂點 和右側頂點 ,取邊 。求一個最大匹配和一個最小頂點覆蓋。)
給出大小相等的可行對象,作為最優性證書。
解答 · 答案
邊 構成大小為三的匹配。整個右側 是大小為三的覆蓋,所以由匹配–覆蓋界,兩者都是最優的。特別地,沒有匹配能飽和全部四個左側頂點。子集 只有鄰點 ,這證明了虧量為一。
快速檢查
(如果一個二部圖有飽和 的匹配,證明:刪去一個左側頂點及其匹配的右側頂點後,所得的圖仍有飽和剩餘左側的匹配。)
不要把它與刪除任意一個右側頂點混淆。
解答 · 答案
去掉與所選左側頂點相關聯的唯一匹配邊。它的右端點就是被刪去的右側頂點,並且沒有其他匹配邊使用這兩個端點中的任何一個。因此每個其他左側頂點在剩餘的圖中都保留其原來的匹配邊。這就構造出了所需的飽和匹配。刪除一個無關的右側頂點可能破壞另一條必要的邊,因而不一定保持飽和。
快速檢查
(給出一個兩部分大小相等、沒有孤立頂點、且沒有完美匹配的二部圖。)
用一個具體的 Hall 子集來解釋失敗的原因。
解答 · 答案
取 ,,邊為 。每個頂點的度都為正,兩個部分的大小都是三。然而 ,違反了 Hall 不等式。任何匹配對 至多有一條邊,對 至多有一條邊,所以大小至多為二; 達到了這個界。