1、二分圖匹配,1,什么是二分圖？,在離散數(shù)學中，我們都學過偶圖，而偶圖就是二分圖。二分圖：給你一個圖，它的頂點可以分為兩個集合，集合V1和V2，所有關(guān)聯(lián)邊的一個頂點在V1中，另一個頂點則在V2中。,v1,v2,v3,v4,v5,v1,v2,v3,v4,二分圖,非二分圖,2,什么是二分圖匹配？,二分圖匹配：給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。,v1,v2,v3,v4,v5,v1,v2,v3,v4,v5,匹配1,匹配2,3,二分圖的最大匹配,最大匹配：圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。,今天我要講的是無權(quán)二分圖的最大匹配問題，采用

2、匈牙利算法。,4,匈牙利算法必備知識：1.蓋點：有被M中的邊關(guān)聯(lián)到的節(jié)點，未蓋點則相反。2.增廣路徑：若二分圖中有一條路徑p，其起始點和結(jié)束點都是未蓋點，其間屬于M的邊和不屬于M的邊交替出現(xiàn)，則稱路徑p是一條關(guān)于M的增廣路徑。匈牙利算法：計算二分圖最大匹配就是應用增廣路徑的概念，每次尋找一條關(guān)于M的增廣路徑p，通過M和增廣路徑進行異或，使得M中的匹配數(shù)增加1。以此類推，直至二分圖中不存在關(guān)于M的增廣路徑為止。此時得到匹配M就是圖G的一個最大匹配。注：M為一個邊集，M就是二分圖的匹配,5,結(jié)合增廣路徑的定義和下圖所示，我們可以理解以下結(jié)論：1.增廣路徑的長度必定為奇數(shù)，第一條邊和最后一條邊都不屬

3、于M。2.將M和增廣路徑進行異或操作（去同存異）可以得到一個更大的匹配M。3.M比M的匹配數(shù)多1。4.M為G的最大匹配當且僅當不存在M的增廣路徑。核心：判斷當前結(jié)點為起點的增廣路徑是否存在。,6,poj1274,題目大意：有N頭奶牛，M個產(chǎn)奶的棚子，每頭奶牛都有自己想去產(chǎn)奶的幾個棚子，問可以產(chǎn)生的最大匹配數(shù)。,數(shù)據(jù)：SampleInput55NM225第一頭：tm2m53234第二頭：tm2m3m4215第三頭：.3125第四頭：.12第五頭：.SampleOutput4,7,解題思路：將奶牛看成N集合，棚子看成M集合1,對于N集合中一個未匹配的節(jié)點i,尋找它的每條關(guān)聯(lián)邊,如果它的邊上的另一個節(jié)點j還沒匹配則表明找到了一個匹配,直接轉(zhuǎn)步驟4;2,假如節(jié)點i它邊上的另一個節(jié)點j已經(jīng)匹配,那么就轉(zhuǎn)向跟j匹配的節(jié)點，也就是它的前驅(qū),假設(shè)是prej,然后再對prej重復1,2的步驟,即尋找增廣路徑.3,假如我們在1,2步過程中找到一條增廣路,那么修改各自對應的匹配點,轉(zhuǎn)步驟4,若無增廣路,則退出.4,匹配數(shù)+1;,8,9,i=1時：Pre2=1;,10,1,2,3,i=2時：Pre5=1;Pre2=2;,11,1,i=3時：Pre1=3;,12,i=4時：Pre3=2;Pre2=1;Pre5=