二分圖(匈牙利,KM算法詳解).ppt

《二分圖(匈牙利,KM算法詳解).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、二分圖匹配Bi-partitegraph二分圖的定義：二分圖是這樣的一個(gè)圖，它的頂點(diǎn)可以分為兩個(gè)集合X和Y。所有的邊關(guān)聯(lián)的兩個(gè)頂點(diǎn)中，恰好一個(gè)屬于集合X，一個(gè)屬于集合Y。123456二分圖的匹配：給定一個(gè)二分圖G，M為G邊集的一個(gè)子集，如果M滿足當(dāng)中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。二分圖的最大匹配定義：圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。如右圖所示：藍(lán)色部分就構(gòu)成一個(gè)最大匹配，同時(shí)它也是一個(gè)完美匹配完美匹配：如果所有點(diǎn)都在匹配邊上，稱這個(gè)最大匹配是完美匹配。二分圖的最大匹配匈牙利算法（時(shí)間復(fù)雜度O(nm)）其思想是用寬度優(yōu)先搜索來找增廣路徑（和floodfill算法類

2、似轉(zhuǎn)化為單位容量簡單網(wǎng)絡(luò)的最大流問題在二分圖的基礎(chǔ)上，加入源點(diǎn)s和匯點(diǎn)t，讓s與每個(gè)X結(jié)點(diǎn)連一條邊，每個(gè)Y結(jié)點(diǎn)和t連一條邊，所有弧的容量為1。這樣，飽和弧就對應(yīng)著匹配邊。二分圖的最大匹配匈牙利算法：尋找增廣路：初始時(shí)最大匹配為空for二分圖左半邊的每個(gè)點(diǎn)i???do從點(diǎn)i出發(fā)尋找增廣路徑如果找到，則把它取反（即增加了總了匹配數(shù)）?？匆坏览}：PKU1469PKU1469一共有N個(gè)學(xué)生跟P門課程,一個(gè)學(xué)生可以任意選一門或多門課,問是否達(dá)成:1.每個(gè)學(xué)生代表的都是不同的課（如果一個(gè)學(xué)生選修的那門課，那么他就可以代表這門課）2.每門課都有一個(gè)代表PKU1469輸入為:PN(課程數(shù)跟學(xué)生數(shù))接著

3、有P行,格式為Countstudentistudenti+1……studentcount(Count表示對課程1感興趣的學(xué)生數(shù),接著有Count個(gè)學(xué)生)如第一行212表示學(xué)生1跟學(xué)生2對課程1感興趣輸出為:若每門課都能找到一位代表則輸出”YES”,否則為”NO”PKU1469假如有三個(gè)學(xué)生跟三門課程,學(xué)生1,2,3.為了跟學(xué)生區(qū)分,假設(shè)3個(gè)課程為4,5,6左邊節(jié)點(diǎn)是學(xué)生,右邊節(jié)點(diǎn)是課程,下圖表示,學(xué)生1對課程4,5感興趣,學(xué)生2對課程5,6感興趣,學(xué)生3對課程6感興趣123456于是問題就變?yōu)樵诙謭D中尋找最大匹配,只要這個(gè)最大匹配大于或等于課程數(shù)P,那么就達(dá)到要求了.尋找最大匹配的匈牙利算

4、法流程首先我們先看節(jié)點(diǎn)1,尋找下一條邊,假設(shè)找到節(jié)點(diǎn)5,因?yàn)?跟5都還沒匹配,所以找到一個(gè)匹配.標(biāo)記,xM[1]=5,yM[5]=1;123456假如我們用xM數(shù)組表示左邊節(jié)點(diǎn)對其右邊節(jié)點(diǎn)的匹配,yM表示右邊節(jié)點(diǎn)對其左邊節(jié)點(diǎn)的匹配,初始化為-1;現(xiàn)在重點(diǎn)看節(jié)點(diǎn)3,當(dāng)尋找下一條邊時(shí),如圖中的藍(lán)邊,我們發(fā)現(xiàn)節(jié)點(diǎn)6的yM[6]=2;已經(jīng)匹配了.此時(shí)我們就轉(zhuǎn)到節(jié)點(diǎn)6的匹配點(diǎn)2上去,發(fā)現(xiàn)節(jié)點(diǎn)2的另一條邊2->5中節(jié)點(diǎn)5也已經(jīng)匹配了,yM[5]=1;繼續(xù)轉(zhuǎn)到節(jié)點(diǎn)1,發(fā)現(xiàn)節(jié)點(diǎn)1的邊1->4中節(jié)點(diǎn)4還沒匹配.于是我們找到了一個(gè)增廣路徑增廣路如圖中箭頭所示123456把圖中紅色線去掉藍(lán)色線加上12345612

5、3456找到一個(gè)更好的匹配更改各自的匹配點(diǎn)總結(jié)所以流程就是:1,對于一個(gè)未匹配的節(jié)點(diǎn)u,尋找它的每條邊,如果它的邊上的另一個(gè)節(jié)點(diǎn)v還沒匹配則表明找到了一個(gè)匹配,直接轉(zhuǎn)步驟4;2,假如節(jié)點(diǎn)u它邊上的另一個(gè)節(jié)點(diǎn)v已經(jīng)匹配,那么就轉(zhuǎn)向跟v匹配的節(jié)點(diǎn),假設(shè)是w,然后再對w重復(fù)1,2的步驟,即尋找增廣路.3,假如我們在1,2步過程中找到一條增廣路,那么修改各自對應(yīng)的匹配點(diǎn),轉(zhuǎn)步驟4,若無增廣路,則退出.4,匹配數(shù)+1;最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)?？梢宰C明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)M簡單的證明如下：（1）M個(gè)是足夠的。只需要讓

6、它們覆蓋最大匹配的M條邊，則其它邊一定被覆蓋（如果有邊e不被覆蓋，把e加入后得到一個(gè)更大的匹配）（2）M個(gè)是必需的，僅考慮形成最大匹配的這M條邊，由于它們兩兩之間沒有公共點(diǎn)，因此至少需要M個(gè)點(diǎn)才可以把它們覆蓋PKU3041:(類似的有PKU3020)問題:假如你現(xiàn)在正處在一個(gè)N*N的矩陣中,這個(gè)矩陣?yán)锩嬗蠯個(gè)障礙物,你擁有一把武器,一發(fā)彈藥一次能消滅一行或一列的障礙物,求最小的彈藥消滅全部障礙物輸入為:NK接下來有K行,每行包含障礙物的坐標(biāo),即r行c列;如:3411132232輸出為:花費(fèi)最小的彈藥數(shù)PKU3041對于上面那個(gè)數(shù)據(jù)我們可以用下面的表示,0表示無障礙物,1表示有;1010100

7、10首先,我們利用行跟列做二分圖:123123行列如果第i行的第j列有障礙物,則在圖中左邊的i行連一條邊到右邊的j列,上面的數(shù)據(jù)就對應(yīng)左圖于是問題就轉(zhuǎn)化成最小點(diǎn)覆蓋的問題.求最大匹配即可.PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU2226DAG圖的最小路徑覆蓋用盡量少的不相交簡單路徑覆蓋有向無環(huán)(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問題。解決此類問題可以建立一個(gè)二分圖模型。把所有頂點(diǎn)i