【二分圖】 二分圖上匹配問題 和 匈牙利算法正確性說明

• 本文討論無權(quán)圖

• 思維上沒什么難度，但是文字量卻比自己想的要多……

0. 一些前置

• 什么是二分圖上的匹配？什么是匈牙利算法？

??“二分圖最大匹配概念、匈牙利算法” 這里引用 Pecco 的介紹。這篇文章寫的非常通俗易懂，而且揭示了匈牙利算法（或者說增廣路）的本質(zhì)是“樸素的匹配調(diào)整”。

• 增廣路、交錯(cuò)路是什么？

??“增廣路、交錯(cuò)路概念” 這里引用 OI-wiki 的內(nèi)容介紹。

1.匈牙利算法跑完之后，二分圖中不存在增廣路

??我們先強(qiáng)調(diào)一下，在二分圖上增廣路的一些性質(zhì)。因?yàn)樵鰪V路一定有偶數(shù)個(gè)點(diǎn)、奇數(shù)條邊，因此二分圖上增廣路的兩個(gè)端點(diǎn)一定分別在兩側(cè)。那么顯然，如果從一側(cè)出發(fā)找不到增廣路，那么從另一側(cè)出發(fā)肯定也找不到。以及增廣路中除了兩端點(diǎn)外所有的點(diǎn)都是匹配點(diǎn)，以及增廣路中最左右兩條邊是未匹配的，剩下的邊交替著匹配和未匹配。

??因此，只要證明了從一側(cè)的任一點(diǎn)出發(fā)都找不到增廣路，那么整張二分圖就沒有增廣路。我們不妨假設(shè)從左側(cè)出發(fā)。

??我們歸納地證明一下（通過討論匈牙利算法進(jìn)行到左側(cè)的第幾個(gè)點(diǎn)）。我們要證明的是，匈牙利算法進(jìn)行完某一個(gè)點(diǎn)之后，從這個(gè)點(diǎn)出發(fā)以及從之前的（左側(cè)的）點(diǎn)出發(fā)都找不到增廣路，即圖中沒有增廣路。下文的提及的“前xx個(gè)點(diǎn)“都是數(shù)左側(cè)的點(diǎn)。

??首先，當(dāng)一開始算法進(jìn)行完 \(0\) 個(gè)點(diǎn)的時(shí)候，前 \(0\) 個(gè)點(diǎn)中沒有增廣路。如果你不放心，那么我們考慮算法進(jìn)行第一個(gè)點(diǎn)，要么有增廣路被增廣了 第一個(gè)點(diǎn)變成了匹配點(diǎn) ，從前 \(1\) 個(gè)點(diǎn)出發(fā)沒有增廣路；要么就找不到增廣路，同樣從前 \(1\) 個(gè)點(diǎn)出發(fā)沒有增廣路。

??現(xiàn)在我們假設(shè)前 \(k\) 個(gè)點(diǎn)出發(fā)沒有增廣路，我們想證明，在進(jìn)行完第 \(k + 1\) 個(gè)點(diǎn)的搜索、（可能存在的）增廣之后，圖中不存在增廣路。

??如果從這個(gè)點(diǎn)出發(fā)找不到增廣路，那么也肯定不會有任何操作，也就不會影響前面的點(diǎn)的結(jié)果，因此前 \(k + 1\) 個(gè)點(diǎn)中沒有增廣路。

??如果從新加入的這個(gè)點(diǎn)出發(fā)找到了增廣路，那么這條路就要被增廣，增廣之后就不是增廣路了。我們現(xiàn)在唯一要考慮的就是，這條路增廣的過程中，會不會影響先前的點(diǎn)，使得先前的點(diǎn)中間出現(xiàn)增廣路？

??增廣完成后，增廣的路徑上都變成了匹配點(diǎn)。

??我們考慮增廣完成后的情況。假設(shè)，增廣完成后，在之前的點(diǎn)中間（只能在之前的點(diǎn)中間出現(xiàn)在增廣路，因?yàn)樾曼c(diǎn)已經(jīng)被匹配了），出現(xiàn)了增廣路。

（本圖中內(nèi)容涵蓋上文和下文，請結(jié)合對應(yīng)部分內(nèi)容閱讀）

??加入新的增廣路 和 這次被增廣的增廣路沒有交點(diǎn)，那就矛盾了，因?yàn)檫@次增廣過程根本不會影響到這條路徑，那么這條所謂的“新的”增廣路在之前就是增廣路，不符合我們的假設(shè)。

??兩條路徑相交的時(shí)候，一條是我們發(fā)現(xiàn)的新的增廣路，一條是本輪中經(jīng)過增廣后，整個(gè)路徑上全部被匹配的路徑。那么顯然相交點(diǎn)不可能存在于增廣路的兩端，因?yàn)榱硪粭l路上的點(diǎn)全匹配了，增廣路上沒匹配。

??（接下來的說明中，涉及到奇偶性的證明和匹配、未匹配沖突的說明，見上圖）

??我們考慮相交在增廣路中間的時(shí)候，如果只是點(diǎn)相交但沒有邊的重合，那么顯然是矛盾的，因?yàn)檫@樣會產(chǎn)生匹配沖突。

??如果有邊的重合，那么我們還原到本輪增廣之前的情況，肯定可以選取“新增廣路”的端點(diǎn)和之前的端點(diǎn)形成增廣路，與之前不存在增廣路矛盾（畫一下就可以知道）。

??因此可以證明，本輪增廣不會使得之前的點(diǎn)中形成新的增廣路，整個(gè)圖中沒有增廣路。這種情況也成立。

??因此歸納成立。匈牙利算法進(jìn)行完成后，二分圖中不存在增廣路。

2. 二分圖中不存在增廣路 等價(jià)于 達(dá)到最大匹配

??我們把原命題逆否一下（逆否之后肯等等價(jià)），二分圖沒達(dá)到最大匹配 等價(jià)于 二分圖中存在增廣路

??后推前是明顯成立的。因?yàn)槎謭D中如果有增廣路，那肯定可以增廣一下，匹配數(shù)量+1。

??前推后在這里引用一個(gè)證明：“匈牙利算法匹配即最大匹配的證明” 這里面的證明基于“匈牙利算法跑完后、二分圖中不存在增廣路”，也就是之前的證明。

3.最大匹配數(shù) 等于 最小點(diǎn)覆蓋數(shù)

??“二分圖最大匹配的K?nig定理及其證明” 在這里我引用了 Matrix67 的證明。下文關(guān)于K?nig定理的證明是參考的這篇文章。

??簡而言之，最小點(diǎn)覆蓋數(shù)的“瓶頸”是有多少條不相交的邊（因?yàn)槎嫉蒙w上）。所以最小覆蓋數(shù) \(\ge\) 最大匹配數(shù)（就是最多的不相交的邊）。而當(dāng)達(dá)成最大匹配之后，二分圖中的匹配邊可以分“方向”（和未匹配點(diǎn)的連接方式有關(guān)），按照方向在匹配邊兩個(gè)端點(diǎn)中的一個(gè)選擇覆蓋。最終證明可以覆蓋所有邊。那么最小點(diǎn)覆蓋數(shù) \(=\) 最大匹配數(shù)。

4.題外話：非二分圖上的無權(quán)圖的匹配

??思路：在圖上進(jìn)行 BFS 或者 DFS 進(jìn)行染色，轉(zhuǎn)化為二分圖。那么有：如果存在奇環(huán)，那么不能直接轉(zhuǎn)化成二分圖，否則是可以的。涉及到奇環(huán)的問題需要縮點(diǎn)等技巧，就另見“帶花樹算法”了。

??首先，二分圖只可能有偶環(huán)，沒有奇環(huán)。我們假設(shè)二分圖形成了環(huán)狀結(jié)構(gòu)，那么存在一條路徑以某一點(diǎn)為起點(diǎn)和終點(diǎn)。根據(jù)二分圖性質(zhì)，因?yàn)槠瘘c(diǎn)和終點(diǎn)同一個(gè)點(diǎn)，所以一定處于同一側(cè)，那么路徑長度就一定為偶數(shù)，因此只能有偶環(huán)，不能有奇環(huán)。

??其次，我們考慮對一個(gè)無向圖進(jìn)行 dfs 染色，黑白相間。我們考慮搜索樹上的情況，因?yàn)闊o向圖 dfs 樹只有 T 邊和 B 邊，T邊上顯然不沖突?？紤] B 邊構(gòu)成環(huán)的情況?？梢钥闯?，如果顏色染色不沖突，那么根據(jù)奇偶性質(zhì)，一定是偶環(huán)，偶環(huán)不沖突。奇環(huán)一定沖突，所以不可能是奇環(huán)。

??于是，有點(diǎn)充要的，二分圖和不含奇環(huán)的無向圖可以相互轉(zhuǎn)化。至于唯一性，那需要考慮連通性的問題了。文章來源地址http://www.zghlxwxcb.cn/news/detail-647126.html

到了這里，關(guān)于【二分圖】 二分圖上匹配問題 和 匈牙利算法正確性說明的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！