ACM講課之二分圖匹配匈牙利算法PPT課件

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

2、。第3頁/共14頁匈牙利算法必備知識匈牙利算法必備知識：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就是二分圖的匹配第4頁/共14頁結(jié)合增廣路徑的定義和下圖所示，我們可以理解以下結(jié)論：1.增廣路徑的長度必定為奇數(shù)

3、，第一條邊和最后一條邊都不屬于 M。2.將 M 和增廣路徑進行異或操作（去同存異）可以得到一個更大的匹配 M。3.M 比 M 的匹配數(shù)多 1。4.M 為 G 的最大匹配當且僅當不存在 M 的增廣路徑。核心：判斷當前結(jié)點為起點的增廣路徑是否存在。第5頁/共14頁poj1274題目大意：有N頭奶牛，M個產(chǎn)奶的棚子，每頭奶牛都有自己想去產(chǎn)奶的幾個棚子，問可以產(chǎn)生的最大匹配數(shù)。數(shù)據(jù)：Sample Input5 5 N M2 2 5 第一頭： t m2 m53 2 3 4 第二頭： t m2 m3 m42 1 5 第三頭：.3 1 2 5 第四頭：.1 2 第五頭：.Sample Output4第6頁/

4、共14頁解題思路：將奶?？闯蒒集合，棚子看成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重復(fù)1,2的步驟,即尋找增廣路徑.3,假如我們在1,2步過程中找到一條增廣路, 那么修改各自對應(yīng)的匹配點,轉(zhuǎn)步驟4,若無增廣路, 則退出.4,匹配數(shù)+1;第7頁/共14頁23455432112345543211第8頁/共14頁2345543211i = 1 時：Pre2 = 1;第9頁/共14頁2345543211123i = 2 時：Pre5 = 1;Pre2 = 2; 第10頁/共14頁23455432111i = 3時：Pre1 = 3;第11頁/共14頁2345543211i = 4時 ：Pre3 = 2;Pre2 = 1;Pre5 = 3;Pre1 = 4;第12頁/共1