資源描述：
《二分圖匹配及其應(yīng)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、二分圖匹配及其應(yīng)用劉汝佳目錄增廣路定理與Hall定理二分圖最大基數(shù)匹配二分圖最大權(quán)匹配應(yīng)用二分圖最大匹配二分圖：結(jié)點可以分為兩部分X和Y，每部分內(nèi)部無邊相連匹配：無公共點的邊集合未蓋點：不與任何匹配邊鄰接的點最大匹配：包含邊數(shù)最多的匹配XY增廣路從未蓋點開始經(jīng)過非匹配邊、匹配邊、非匹配邊……序列，最終通過一條非匹配邊到達(dá)另一個未蓋點非匹配邊個數(shù)比匹配邊個數(shù)多一如果把匹配邊和非匹配邊互換…匹配仍合法，但基數(shù)加一增廣路定理匹配是最大匹配當(dāng)且僅當(dāng)不存在增廣路這個定理適用于任意圖011001011010匈牙利樹思
2、考：忽略虛線邊會導(dǎo)致存在增廣路卻找不到嗎？增廣路定理的證明必要性.如果存在則增廣后得到更大匹配.充分性.如果M不是最大匹配,取最大匹配M’,作M’和M的對稱差G’,則G’在M’中的邊應(yīng)比M’中更多.G’有三種可能的連通分支孤立點.當(dāng)某邊(u,v)同時屬于兩個匹配,則u和v都是孤立點.交互回路.該回路中屬于M和M’的邊數(shù)相同交互道路.如果不存在增廣路,則
3、M’
4、=
5、M
6、,與假設(shè)矛盾;如果存在M關(guān)于M’的增廣路,又與M’是最大匹配矛盾,因此存在M’關(guān)于M的增廣路Hall定理在二分圖(X,Y,E)中,X到Y(jié)存在
7、完全匹配(X的結(jié)點全被匹配)的充要條件是對于X的任意子集A,恒有必要性.若存在A使得右邊>左邊,則A無法全部匹配充分性.假設(shè)G的最大匹配M不是完全匹配,一定存在結(jié)點X的結(jié)點x0關(guān)于M是非飽和點.如果x0的鄰集為空,則令A(yù)={x0}引出矛盾;如果非空則其中每個結(jié)點均為飽和點(否則會有增廣路).尋找與x0為端點的關(guān)于M的一切交錯路,設(shè)其中Y結(jié)點的集合為Y’,X結(jié)點的集合為X’,則Y’結(jié)點與X’-{x0}的結(jié)點一一對應(yīng),因此
8、X’
9、>
10、Y’
11、,令A(yù)=X’引出矛盾.二分圖最大匹配算法匈牙利樹是從所有未蓋點,而不是
12、從固定未蓋點長出的樹Edmonds-Karp算法:把所有未蓋點放到隊列中,BFS尋找/增廣路時間均為O(m)最多找O(n)次時間復(fù)雜度O(nm)Hopcroft算法：每次沿多條增廣路同時增廣每次尋找若干條結(jié)點不相交最短增廣路每次的最短增廣路集是極大的時間復(fù)雜度基于DFS的算法:每次選一個未蓋點u進(jìn)行DFS.如果找不到增廣路則換一個未蓋點,且以后再也不從u出發(fā)找增廣路.Hopcroft算法可以證明：如果每次找到的最短增廣路集是極大的，則只需要增廣次關(guān)鍵：用O(m)時間找一個極大最短增廣路集步驟1：用距離標(biāo)號
13、擴(kuò)展匈牙利樹，找到第一個未蓋點時并不停止，把此時的距離標(biāo)號設(shè)為上限。這樣，找到的所有未蓋點距離標(biāo)號都相同步驟2：每次任取一個未蓋點，用DFS找到它到起點的增廣路(只沿著距離標(biāo)號下降的方向),標(biāo)記經(jīng)過的點,找所有增廣路的總時間為O(m)基于DFS的算法從貪心匹配,而不是空匹配開始每次從一個未蓋點開始DFS找增廣路,而不是一次性把所有未蓋點放入隊列進(jìn)行BFS如果從一個未蓋點u開始找不到增廣路,則以后再也不用考慮u了.為什么?定理:假設(shè)G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也
14、不存在從u出發(fā)關(guān)于增廣后新匹配的增廣路定理的證明(1)定理:假設(shè)G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關(guān)于增廣后新匹配M’的增廣路證明:假設(shè)增廣后從u出發(fā)有增廣路Q.若Q與P不相交,則Q就是M-增廣路,矛盾.因此Q與P相交.下面借助P和Q構(gòu)造出從u出發(fā)關(guān)于M的增廣路,從而得到矛盾定理的證明(2)Q與P相交.設(shè)P的兩個M-非飽和點為u0和v0,而Q的兩個M’-非飽和點是u,v.從u開始沿Q走,設(shè)第一個P中結(jié)點為w,則w把P分為兩段,其中必有一段以M中邊與w
15、關(guān)聯(lián),得到從u出發(fā)增廣路wv0u0vuPQ完全二分圖的最大權(quán)完美匹配完全二分圖，每條邊有一個非負(fù)整數(shù)權(quán)值目標(biāo)：求出權(quán)和最大的完美匹配特點：完美匹配容易求，但權(quán)最大的不易可行頂標(biāo)：結(jié)點函數(shù)l，對任意弧(x,y)滿足相等子圖：G的生成子圖，包含所有點，但只包含滿足l(x)+l(y)=w(x,y)的所有弧(x,y)相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)匹配證明：設(shè)M*是相等子圖的完美匹配，則根據(jù)定義設(shè)M是原圖的任意完美匹配，則關(guān)鍵：尋找好的可行頂標(biāo)，使相等子圖有完美匹配算法思想關(guān)鍵：尋找好
16、的可行頂標(biāo)，使相等子圖有完美匹配思想：隨便構(gòu)造一個可行頂標(biāo)（例如Y結(jié)點頂標(biāo)為0，X結(jié)點的頂標(biāo)為它出發(fā)所有弧的最大權(quán)值，然后求相等子圖的最大匹配存在完美匹配，算法終止否則修改頂標(biāo)使得相等子圖的邊變多，有更大機(jī)會存在完美匹配考慮相等子圖不存在完美匹配時的情形Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為6，不是完美匹配算法在尋找增廣路失敗的同時得到了一棵匈牙利樹雖然此匈牙利樹并沒有包含未蓋點（因此沒有找到增廣路），但
