匹配是整體分配問題
定義 3.3.1
(二分圖、匹配與鄰域)
令 為有限二分圖,每條邊連接一個左頂點和一個右頂點。匹配 中任意兩條邊都不共用端點。沒有與匹配邊相接的頂點稱為未匹配。若每個左頂點都被匹配,稱匹配飽和 。對 ,以 表示與 中至少一個頂點相鄰的所有右頂點。
局部選擇可能阻礙另一頂點匹配,即使存在更好的分配也一樣。交替路徑可以修正這些選擇;找不到路徑時,搜尋本身亦可證明無法得到更大的匹配。本節承接網絡流的殘量路徑,直接證明匹配問題的證書。
交替搜尋與增廣
定義 3.3.2
(增廣路徑)
增廣路徑由未匹配的左頂點出發,到未匹配的右頂點結束,路徑上的非匹配邊與匹配邊交替出現。首尾兩條邊都不在 中。翻轉路徑指用路徑與 的對稱差替換 :移除路徑上的舊匹配邊,加入原來未使用的路徑邊。
定理 3.3.3
(增廣步驟)
翻轉 的一條增廣路徑,得到大小為 的匹配。
證明
(翻轉增廣路徑令匹配多一條邊)
路徑的每個內部頂點失去一條匹配邊,同時得到一條,所以它仍恰與一條匹配邊相接。兩個端點原本未匹配,各得到一條匹配邊。路徑以外的頂點不受影響。因此所得為匹配。路徑上不在 中的邊比在 中的邊多一條,所以新的大小為 。
要找這樣的路徑,從所有未匹配左頂點同時開始圖搜尋。從已到達的左頂點,沿不在 中的邊走到右方;從已到達的右頂點,如有匹配邊,便沿該邊走回左方。只在首次到達頂點時記錄前驅。這些指標構成搜尋森林:由已到達的未匹配右頂點沿前驅回溯,便得到通往未匹配左起點的簡單路徑,且符合所需的交替方式;否則搜尋結束時,已到達的集合分別記為 和 。已訪問標記可防止出現環;增廣後匹配已改變,應重新搜尋。
最大匹配與最小覆蓋
定義 3.3.4
(頂點覆蓋)
頂點覆蓋是與每條邊至少有一個端點相接的頂點集合。
定理 3.3.5
(Kőnig 定理)
對任何匹配 ,每個頂點覆蓋的大小至少是 。在有限二分圖中,匹配的最大大小等於頂點覆蓋的最小大小,而且交替搜尋同時給出兩者。
證明
(失敗的搜尋給出同樣大小的覆蓋)
對任何匹配 ,每個覆蓋的大小至少是 :每條匹配邊都需要一個覆蓋頂點,而不同匹配邊沒有共同端點。
假設交替搜尋找不到增廣路徑,則 中每個頂點都已匹配,否則已到達的未匹配右頂點會構成增廣路徑。此外 :從已到達左頂點出發的每條非匹配邊都被遍歷;若它有匹配邊,該匹配右頂點早在左頂點之前已到達。反過來,每個已到達右頂點都是從左鄰點走到的。
定義
每條邊都被覆蓋:若左端點不在 ,它就在 ;若左端點在 ,右端點就在 。每條匹配邊恰有一個端點在 ,因為其兩端要麼均已到達,要麼均未到達。 中每個頂點均已匹配:未匹配左頂點是搜尋起點,未匹配右頂點不可能已到達。因此 。匹配與覆蓋提供相等的下界及上界證書,所以 最大、 最小。這證明了 Kőnig 定理。
證明透視
為何失敗的搜尋是完整的證書
證明從停止條件讀出兩個事實。沒有到達未匹配的右頂點,所以 中每個頂點都有配偶,而配偶位於 。搜尋沿 中每條非匹配邊和 中每條匹配邊走遍,所以它是封閉的,由此得到 ,並說明沒有匹配邊恰有一個端點被到達。這兩點合起來使 成為覆蓋,每條匹配邊恰有一個端點在 中,而且不含未匹配頂點,所以 ,再由弱界完成論證。二分性出現在覆蓋的檢驗中:每條邊的左端點要麼不在 ,要麼在 ;在後一情形,搜尋的封閉性使它的右端點屬於 。含有奇圈的圖沒有這樣的左右劃分,下面的反例正是利用這一點。
從空匹配開始反覆增廣,大小每次增加一,且不超過 ,故必定終止。最後一次失敗的搜尋給出上述證書,無須假設貪心選擇永遠不改便可證明算法正確。採用鄰接表時,一次搜尋成本為 ;最多 次成功搜尋加一次最後失敗搜尋,總時間為 。這只是簡單上界,不聲稱是最佳算法。
反例模式
Kőnig 等式需要二分性
考慮這樣的說法:在每個圖中,匹配的最大大小都等於頂點覆蓋的最小大小。取以 為頂點、邊為 的三角形。其中任意兩條邊都有公共頂點,所以每個匹配至多含一條邊。沒有單獨一個頂點與三條邊都相交,因為 沒有覆蓋 , 與 同理。而 是一個覆蓋。所以最大匹配的大小為一,最小覆蓋的大小為二。三角形含有奇圈,不是二分圖,搜尋所用的左右劃分並不存在。修正後的說法把等式限於二分圖;對一般圖,只有不等式 仍然成立。
由搜尋推出 Hall 條件
定理 3.3.6
(Hall 定理)
有限二分圖存在飽和 的匹配,當且僅當每個 都滿足 。
證明
(由失敗的搜尋得出 Hall 條件)
必要性直接成立:匹配把 的不同頂點送往不同鄰點。為證充分性,執行增廣算法至最大匹配。若仍有未匹配左頂點,失敗搜尋中的 至少有一個未匹配起點。每個已到達右頂點都與不同的已到達左頂點匹配,而每個已到達且已匹配的左頂點的匹配對象都在 。因此 。由 ,集合 違反 Hall 條件。逆否命題完成證明。算法不必直接檢查全部子集:若有阻礙,失敗搜尋便產生一個違反條件的集合。
概念視角代數
把 Kőnig 定理看成 0 與 1 的表格
把 記成一個表格:每個左頂點對應一行,每個右頂點對應一列,當且僅當 時,位置 寫 。匹配就是一組 ,其中任何兩個都不在同一行或同一列;頂點覆蓋就是一組行和列,使每個 都落在其中某一行或某一列上。Kőnig 定理說:互相獨立的 最多有多少個,恰等於覆蓋所有 的行與列至少要多少條。在下面的例題中,三列 已含所有 ,而且存在三個互相獨立的 。
例題:兩個證書
例題 3.3.7
(四個頂點的兩次搜尋)
取 、,邊為 –、–、–、–、– 和 –。從 開始。 和 都未匹配;搜尋可選增廣路徑 ,得到 。
重新從唯一未匹配左頂點 搜尋。交替可達性依次為
由左到右的箭頭使用非匹配邊,由右到左則使用匹配邊。所有右頂點都已到達且已匹配,所以沒有剩餘增廣路徑。此處 、,而 是大小三的覆蓋,等於匹配大小。同時 有四個頂點卻只有三個鄰點,展示了飽和 的 Hall 障礙。追蹤採用一種特定搜尋次序;證書並不依賴掃描邊的次序。
例題 3.3.8
(孤立的左頂點)
取 、,只有一條邊 –,所以 沒有鄰點。從空匹配開始,從兩個未匹配的左頂點同時搜尋。頂點 到達未匹配的右頂點 ,所以 – 是增廣路徑,得 。第二次搜尋只從 出發,沒有到達其他頂點:、。於是 覆蓋唯一的邊,大小為一,等於 。違反條件的集合是 ,其 ,所以 。有虧缺的集合可以只是一個沒有任何鄰點的頂點。
例題 3.3.9
(改道修正先前的選擇)
取 、,邊為 –、–、–,並設局部選擇得到匹配 。唯一未匹配的左頂點是 。搜尋先沿非匹配邊 ,再沿匹配邊 ,然後沿非匹配邊 。右頂點 未匹配,所以 是增廣路徑。翻轉它,刪去 –,加入 – 和 –,得到大小為二、飽和 的匹配。先前選擇的 – 被撤銷,而不是保留。
常見錯誤
常見錯誤
(Hall 條件針對子集,而不是單個頂點)
只檢查每個左頂點都有鄰點並不足夠,因為不同的左頂點可能爭奪同樣的右頂點。在邊為 –、–、– 的圖中,每個左頂點都有鄰點,但 的 ,不存在飽和 的匹配。失敗的搜尋會產生這樣的子集,所以無需枚舉所有子集。
常見錯誤
(大小相等並不構成證書)
只有當頂點集合確實是覆蓋時,大小相等的匹配與頂點集合才證明最優性。取邊 –、–、–、–。匹配 與集合 的大小都是二,但 漏掉了邊 –,所以它不是覆蓋,甚麼也證明不了。應先逐條邊檢驗覆蓋性質,再比較大小。
練習
快速檢查
(取 、,邊為 –、–、–。給出最大匹配、大小相同的覆蓋,以及違反 Hall 條件的子集。)
找出兩個只共用一個鄰點的左頂點。
解答 · 答案
匹配 的大小為二。集合 與每條邊相交,大小也是二,所以兩者都是最優的。子集 的 ,所以 ,不存在飽和 的匹配。
快速檢查
(解釋為何翻轉增廣路徑令匹配大小恰增加一,包括端點發生了甚麼。)
數一數路徑上屬於 和不屬於 的邊各有多少條。
解答 · 答案
路徑上不在 中的邊比在 中的邊多一條,所以翻轉加入的邊比移除的多一條。每個內部頂點以一條匹配邊換另一條,仍恰匹配一次。每個端點原本未匹配,得到一條新的匹配邊,因而匹配一次。
快速檢查
(若交替搜尋尚未遍歷所有可達頂點便過早停止,為何所得匹配與所提出的覆蓋可能無法證明兩者的最優大小相等?)
已到達的集合對遍歷規則是否封閉?
解答 · 答案
此時 與 對遍歷規則並不封閉。某個已到達的左頂點可能有一條非匹配邊通向尚未屬於 的右頂點。這條邊的兩個端點都不在 中,所以 未必是覆蓋。未到達的右頂點也可能是未匹配的,這時增廣路徑仍然存在, 並不是最大的。只有搜尋完成之後,兩個性質才同時成立。