資源描述：
《ACM講課之二分圖匹配(匈牙利算法).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、二分圖匹配什么是二分圖？在離散數(shù)學(xué)中，我們都學(xué)過偶圖，而偶圖就是二分圖。二分圖：給你一個圖，它的頂點可以分為兩個集合，集合V1和V2，所有關(guān)聯(lián)邊的一個頂點在V1中，另一個頂點則在V2中。v1v2v3v4v5v1v2v3v4二分圖非二分圖什么是二分圖匹配？二分圖匹配：給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。v1v2v3v4v5v1v2v3v4v5匹配1匹配2二分圖的最大匹配最大匹配：圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。今天我要講的是無權(quán)二分圖的最大匹配問題，采用匈牙利算法。匈牙利算法必備
2、知識：1.蓋點：有被M中的邊關(guān)聯(lián)到的節(jié)點，未蓋點則相反。2.增廣路徑：若二分圖中有一條路徑p，其起始點和結(jié)束點都是未蓋點，其間屬于M的邊和不屬于M的邊交替出現(xiàn)，則稱路徑p是一條關(guān)于M的增廣路徑。匈牙利算法：計算二分圖最大匹配就是應(yīng)用增廣路徑的概念，每次尋找一條關(guān)于M的增廣路徑p，通過M和增廣路徑進行異或，使得M中的匹配數(shù)增加1。以此類推，直至二分圖中不存在關(guān)于M的增廣路徑為止。此時得到匹配M就是圖G的一個最大匹配。注：M為一個邊集，M就是二分圖的匹配結(jié)合增廣路徑的定義和下圖所示，我們可以理解以下結(jié)論：1.增廣路徑的長度必定為奇數(shù)，第一條邊和最后一條
3、邊都不屬于M。2.將M和增廣路徑進行異或操作（去同存異）可以得到一個更大的匹配M'。3.M'比M的匹配數(shù)多1。4.M為G的最大匹配當(dāng)且僅當(dāng)不存在M的增廣路徑。核心：判斷當(dāng)前結(jié)點為起點的增廣路徑是否存在。poj1274題目大意：有N頭奶牛，M個產(chǎn)奶的棚子，每頭奶牛都有自己想去產(chǎn)奶的幾個棚子，問可以產(chǎn)生的最大匹配數(shù)。數(shù)據(jù)：SampleInput55NM225第一頭：tm2m53234第二頭：tm2m3m4215第三頭：…..3125第四頭：…..12第五頭：…..SampleOutput4解題思路：將奶?？闯蒒集合，棚子看成M集合1,對于N集合中一個未
4、匹配的節(jié)點i,尋找它的每條關(guān)聯(lián)邊,如果它的邊上的另一個節(jié)點j還沒匹配則表明找到了一個匹配,直接轉(zhuǎn)步驟4;2,假如節(jié)點i它邊上的另一個節(jié)點j已經(jīng)匹配,那么就轉(zhuǎn)向跟j匹配的節(jié)點，也就是它的前驅(qū),假設(shè)是pre[j],然后再對pre[j]重復(fù)1,2的步驟,即尋找增廣路徑.3,假如我們在1,2步過程中找到一條增廣路,那么修改各自對應(yīng)的匹配點,轉(zhuǎn)步驟4,若無增廣路,則退出.4,匹配數(shù)+1;234554321123455432112345543211i=1時：Pre[2]=1;2345543211123i=2時：Pre[5]=1;Pre[2]=2;2345543
5、2111i=3時：Pre[1]=3;2345543211i=4時：Pre[3]=2;Pre[2]=1;Pre[5]=3;Pre[1]=4;二分圖最大匹配延伸最小點覆蓋最小邊覆蓋最大獨立集有向圖最小路徑覆蓋最優(yōu)匹配（KM算法）
