從配對到圖
假設每名學生最多選一個項目,而每個項目最多接收一名學生。邊代表允許的配對。允許的邊多,並不代表人人都能配對:幾名學生可能只能選同一個項目。以下假設有限二分圖 的每條邊都連接左、右兩側。
定義 2.2.1
(匹配)
的匹配是一組互不共用端點的邊 。若 中有邊與某頂點相接,稱該頂點已匹配,否則稱未匹配。大小 最大的匹配稱為最大匹配。
我們要令匹配大小最大,而不只是找一個不能再直接加入單邊的匹配。
常見錯誤
(極大不等於最大)
不能再加入任何邊的匹配稱為極大匹配,但它未必是最大匹配。對邊 ,匹配 是極大的,因為 和 都與它共用端點;然而 更大。貪心地逐條加邊只會停在極大匹配;要達到最大匹配,可能須撤回先前的選擇,正如第一個例題所示。
建立流網絡
加入源點 和匯點 。對每個 加入容量為一的 ;對每條邊 加入容量為一的 ;對每個 加入容量為一的 。
命題 2.2.2
(最大匹配就是最大整數流)
在這個網絡中,最大流值等於 的最大匹配大小。更精確地說,匹配與同值的可行整數流一一對應。
證明
(雙向轉換)
每條匹配邊沿 傳送一單位,便得到值等於匹配大小的可行整數流。
反過來,對任意可行整數流,單位容量使每條邊的流量只能是零或一。由流量守恆,以及源點和匯點兩側的單位容量,可知流量為一的中間邊不共用左右端點,故組成同樣大小的匹配。整數最大流定理保證存在整數最大流,所以最大流值等於最大匹配大小。
整數條件不可省略:一般分數可行流本身不指定一組匹配。
例題 2.2.3
(反向邊如何修訂配對)
假設 可選項目 或 , 只能選 。若先把 配給 ,流在 上有一單位,殘量網絡便含反向邊 。殘量路徑 用上這條邊。沿路增廣一單位會取消 –,再加入 – 與 –。
最後的流值為 ,只包含允許的正向配對 。兩名學生都已獲配,所以不存在更大的匹配。原來的局部極大單邊配對 並非最大。
另一種證書:覆蓋所有邊
定義 2.2.4
(頂點覆蓋)
的頂點覆蓋是頂點集合 ,使 的每條邊至少有一個端點在 中。
引理 2.2.5
(匹配不會大於覆蓋)
在任何有限圖中,若 是匹配而 是頂點覆蓋,則 。
證明
(為每條匹配邊指定一個覆蓋頂點)
的每條邊都有端點在 中,任選其一。 中兩條不同的邊沒有公共端點,所以分到不同的頂點。這給出由 到 的單射。
只有能找到大小相同的匹配和覆蓋時,這個引理才給出可核驗的最優證書。
定理 2.2.6
(二分圖中的匹配與覆蓋等式)
有限二分圖的最大匹配大小等於最小頂點覆蓋大小。
證明
(由交替可達性構造覆蓋)
取最大匹配 。從所有未匹配的左頂點開始走交替路徑:由左到右走未匹配邊,由右到左走匹配邊。令到達的左右頂點集合為 。到達的右頂點不可能未匹配,否則該交替路徑可增廣 。
令 。它覆蓋每條邊:若 且 ,規則會到達 ;若 ,已到達且有匹配的左頂點必經其匹配的右端點到達,因此 也已到達。(未匹配左頂點沒有匹配邊。)所以左端不在 的邊,其右端必在 。
每條匹配邊恰有一個端點在 :左端到達時右端也到達;左端未到達時,右端也不能到達,否則會沿匹配邊到達左端。 中每個頂點均已匹配,因未匹配左頂點全是起點; 中每個頂點亦已匹配,因不存在增廣路徑。因此 。由引理即得兩者分別最優。
證明使用二分性與最大匹配,不能不加條件套用到任意圖。
證明透視
兩個假設各在哪裏起作用
的最大性只用了一次:保證每個到達的右頂點都已匹配。若對非最大匹配進行同樣構造,可能到達未匹配的右頂點; 仍是覆蓋,但該頂點不對應 的任何邊,於是 ,甚麼也證明不了。
二分性體現在搜尋的形狀上。每條邊兩端分屬兩側,所以搜尋在兩側之間交替,覆蓋才可取為左側未到達的頂點加上右側已到達的頂點。
關鍵一步: 或 單獨都不是小的覆蓋;這個覆蓋混合兩側,恰好在交替可達性停止之處轉換側別。
如何收結:證明從未直接說明 是最小覆蓋,而是證明 ;引理對每個覆蓋和每個匹配都成立,於是兩者同時最優。
常見錯誤
(把到達的頂點當作覆蓋)
覆蓋是 :左側取未到達的,右側取已到達的。取全部到達頂點 是錯的。在下面的瓶頸例子中,對匹配 ,這會得到 ,漏掉了邊 和 。
瓶頸例子
例題 2.2.7
(兩名學生爭一個項目)
令 、、。匹配 的大小為二;頂點覆蓋 覆蓋全部四條邊,大小亦為二,故證明不存在大小為三的匹配。直接看, 都只能選項目 ,不能同時獲配。
另一個匹配 同樣最優:證書確定最優值,不一定確定唯一配對。
例題 2.2.8
(完美匹配令搜尋沒有起點)
令 、、,匹配為 。每個左頂點都已匹配,所以交替搜尋沒有起點:。構造給出 。
驗證: 覆蓋 和 , 覆蓋 。因此 是大小為 的覆蓋,兩者均最優。在這個退化情況中,覆蓋就是整個左側;只要 匹配了 的全部頂點,情況必定如此。
反例模式
沒有二分性時匹配與覆蓋等式不成立
或許有人以為任何圖的最大匹配與最小覆蓋都相等。取頂點為 的三角形。三條邊中任意兩條都共用頂點,所以最大匹配大小為一。單一頂點只覆蓋與它相接的兩條邊,漏掉對邊,所以每個覆蓋至少有兩個頂點; 是大小為二的覆蓋。兩者為 。引理 在任何圖都成立;等號則需要二分假設。
練習
快速檢查
(對邊 ,給出可改善匹配 的交替路徑及所得匹配。)
由未匹配的左頂點 出發。
解答 · 答案
交替路徑 把 換成 ,得到兩條匹配邊。
快速檢查
(在瓶頸例子中,驗證 是覆蓋,並解釋它如何給出匹配上界。)
逐一檢查四條邊。
解答 · 答案
由頂點 覆蓋, 由 覆蓋。匹配的不同邊不能共用覆蓋頂點,故最多選兩條。
快速檢查
(在瓶頸例子中,從匹配 的未匹配左頂點 出發,求 和構造出的覆蓋。)
由左到右走未匹配邊,由右到左走匹配邊。
解答 · 答案
由 到達 ,再沿匹配邊到達 ;沒有其他可到達頂點。因此 、,覆蓋為 。
快速檢查
(為何值為 的分數可行流不能直接描述大小為 的匹配?甚麼定理另行保證存在整數最優流?)
比較匹配是甚麼,與流量指派的是甚麼。
解答 · 答案
匹配是集合,其大小為整數;分數邊值不一定是一組所選邊。整數容量和整數最大流定理保證存在整數最大流。