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

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

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

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

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

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

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

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

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