二分圖(匈牙利,KM算法詳解)課件

二分圖匹配二分圖匹配1Bi-partitegraph二分圖的定義：二分圖是這樣的一個圖，它的頂點(diǎn)可以分為兩個集合X和Y。所有的邊關(guān)聯(lián)的兩個頂點(diǎn)中，恰好一個屬于集合X，一個屬于集合Y。123456二分圖的匹配：給定一個二分圖G，M為G邊集的一個子集，如果M滿足當(dāng)中的任意兩條邊都不依附于同一個頂點(diǎn)，則稱M是一個匹配。Bi-partitegraph二分圖的定義：123456二2二分圖的最大匹配定義：圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。如右圖所示：藍(lán)色部分就構(gòu)成一個最大匹配，同時它也是一個完美匹配完美匹配：如果所有點(diǎn)都在匹配邊上，稱這個最大匹配是完美匹配。

二分圖的最大匹配定義：如右圖所示：藍(lán)色部分3二分圖的最大匹配匈牙利算法（時間復(fù)雜度O(nm)） 其思想是用寬度優(yōu)先搜索來找增廣路徑（和floodfill算法類似轉(zhuǎn)化為單位容量簡單網(wǎng)絡(luò)的最大流問題在二分圖的基礎(chǔ)上，加入源點(diǎn)s和匯點(diǎn)t，讓s與每個X結(jié)點(diǎn)連一條邊，每個Y結(jié)點(diǎn)和t連一條邊，所有弧的容量為1。這樣，飽和弧就對應(yīng)著匹配邊。二分圖的最大匹配匈牙利算法（時間復(fù)雜度O(nm)） 4二分圖的最大匹配匈牙利算法：尋找增廣路：初始時最大匹配為空

for二分圖左半邊的每個點(diǎn)i

do從點(diǎn)i出發(fā)尋找增廣路徑如果找到，則把它取反（即增加了總了匹配數(shù)）?？匆坏览}：PKU1469二分圖的最大匹配匈牙利算法：5PKU1469一共有N個學(xué)生跟P門課程,一個學(xué)生可以任意選一門或多門課,問是否達(dá)成: 1.每個學(xué)生代表的都是不同的課（如果一個學(xué)生選修的那門課，那么他就可以代表這門課） 2.每門課都有一個代表PKU1469一共有N個學(xué)生跟P門課程,一個學(xué)6PKU1469輸入為:PN(課程數(shù)跟學(xué)生數(shù))接著有P行,格式為Countstudentistudenti+1……studentcount(Count表示對課程1感興趣的學(xué)生數(shù),接著有Count個學(xué)生)如第一行212表示學(xué)生1跟學(xué)生2對課程1感興趣輸出為:若每門課都能找到一位代表則輸出”YES”,否則為”NO”PKU1469輸入為:7PKU1469假如有三個學(xué)生跟三門課程,學(xué)生1,2,3.為了跟學(xué)生區(qū)分,假設(shè)3個課程為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中尋找最大匹配,只要這個最大匹配大于或等于課程數(shù)P,那么就達(dá)到要求了.PKU1469假如有三個學(xué)生跟三門課程,學(xué)生1,2,3.為了8尋找最大匹配的匈牙利算法流程

首先我們先看節(jié)點(diǎn)1,尋找下一條邊,假設(shè)找到節(jié)點(diǎn)5,因為1跟5都還沒匹配,所以找到一個匹配.標(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)尋找下一條邊時,如圖中的藍(lán)邊,我們發(fā)現(xiàn)節(jié)點(diǎn)6的yM[6]=2;已經(jīng)匹配了.此時我們就轉(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還沒匹配.于是我們找到了一個增廣路徑增廣路如圖中箭頭所示尋找最大匹配的匈牙利算法流程

首先我們先看節(jié)點(diǎn)1,尋找下一條9123456把圖中紅色線去掉藍(lán)色線加上123456123456找到一個更好的匹配更改各自的匹配點(diǎn)123456把圖中紅色線去掉藍(lán)色線加上1234561234510總結(jié)所以流程就是:1,對于一個未匹配的節(jié)點(diǎn)u,尋找它的每條邊,如果它的邊上的另一個節(jié)點(diǎn)v還沒匹配則表明找到了一個匹配,直接轉(zhuǎn)步驟4;2,假如節(jié)點(diǎn)u它邊上的另一個節(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;總結(jié)所以流程就是:11最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點(diǎn)關(guān)聯(lián)。可以證明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)M簡單的證明如下：（1）M個是足夠的。只需要讓它們覆蓋最大匹配的M條邊，則其它邊一定被覆蓋（如果有邊e不被覆蓋，把e加入后得到一個更大的匹配）（2）M個是必需的，僅考慮形成最大匹配的這M條邊，由于它們兩兩之間沒有公共點(diǎn)，因此至少需要M個點(diǎn)才可以把它們覆蓋

最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合12PKU3041:(類似的有PKU3020)

問題:假如你現(xiàn)在正處在一個N*N的矩陣中,這個矩陣?yán)锩嬗蠯個障礙物,你擁有一把武器,一發(fā)彈藥一次能消滅一行或一列的障礙物,求最小的彈藥消滅全部障礙物輸入為:NK接下來有K行,每行包含障礙物的坐標(biāo),即r行c列;如:3411132232輸出為:花費(fèi)最小的彈藥數(shù)PKU3041:(類似的有PKU3020)

問題:13PKU3041對于上面那個數(shù)據(jù)我們可以用下面的表示,0表示無障礙物,1表示有;101010010首先,我們利用行跟列做二分圖:123123行列如果第i行的第j列有障礙物,則在圖中左邊的i行連一條邊到右邊的j列,上面的數(shù)據(jù)就對應(yīng)左圖于是問題就轉(zhuǎn)化成最小點(diǎn)覆蓋的問題.求最大匹配即可.PKU3041對于上面那個數(shù)據(jù)我們可以用下面的表示,0表示無14PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU2226PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU222615DAG圖的最小路徑覆蓋用盡量少的不相交簡單路徑覆蓋有向無環(huán)(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問題。解決此類問題可以建立一個二分圖模型。把所有頂點(diǎn)i拆成兩個：Ｘ結(jié)點(diǎn)集中的i和Y結(jié)點(diǎn)集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設(shè)二分圖最大匹配為m,則結(jié)果就是n-m

記住一個重要的結(jié)論：

DAC圖的最小路徑覆蓋數(shù)=節(jié)點(diǎn)數(shù)(n)-最大匹配數(shù)看一道例題：PKU1422DAG圖的最小路徑覆蓋用盡量少的不相交簡單路徑覆蓋有向無環(huán)(16PKU1422有一個城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個路口相連。同時已知街道不會形成回路。你的任務(wù)是編寫程序求最小數(shù)量的傘兵，這些傘兵可以訪問（visit）所有的路口。對于傘兵的起始降落點(diǎn)不做限制。Input:

3

34

13

23Output:2PKU1422有一個城鎮(zhèn)，它的所有街道都是單行的，并3’2’1’132412344’3’2’1’18二分圖的最大獨(dú)立集最大獨(dú)立集問題：在Ｎ個點(diǎn)的圖G中選出m個點(diǎn)，使這m個點(diǎn)兩兩之間沒有邊．求m最大值．記住一個重要的結(jié)論：二分圖的最大獨(dú)立集數(shù)=節(jié)點(diǎn)數(shù)(n)-最大匹配數(shù)二分圖的最大獨(dú)立集最大獨(dú)立集問題：在Ｎ個點(diǎn)的圖G中選出m個19黑色點(diǎn)即為一個最大獨(dú)立集可以這樣理解，在總的點(diǎn)集中，去掉最少的點(diǎn)，使得剩下的點(diǎn)相互之間沒有邊。用最少的點(diǎn)去覆蓋所有的邊，也就是最小覆蓋。黑色點(diǎn)即為一個最大獨(dú)立集可以這樣理解，在總的點(diǎn)集中，去掉最少20二分圖最優(yōu)匹配又稱帶權(quán)最大匹配。二分圖的每條邊帶有權(quán)值。求一個匹配使得匹配邊上的權(quán)值和最大。一般X和Y集合頂點(diǎn)個數(shù)相同，最優(yōu)匹配也是一個完備匹配，即每個頂點(diǎn)都被匹配。如果個數(shù)不相等，可以通過補(bǔ)點(diǎn)加0邊實(shí)現(xiàn)轉(zhuǎn)化。最小？看一道例題：PKU2195二分圖最優(yōu)匹配又稱帶權(quán)最大匹配。21PKU2195題意：有N個人跟N個房子,每個人跟房子都有一定的距離,現(xiàn)在要讓這N個人全部回到N個房子里面去,要求所有人回去的距離最短.現(xiàn)在我們假設(shè)要求的是最大距離.那么就是求最大權(quán)匹配.下面我們先介紹一下KM算法PKU2195題意：22KM算法基本概念：可行頂標(biāo)和相等子圖可行頂標(biāo)：L是一個關(guān)于結(jié)點(diǎn)的函數(shù)，L(x)是頂點(diǎn)x對應(yīng)的頂標(biāo)值?？尚许敇?biāo)對于圖中的每條邊(x,y)都有L(x)+L(y)>=w(x,y)相等子圖：只包含L(x)+L(y)=w(x,y)的邊的子圖KM算法基本概念：可行頂標(biāo)和相等子圖23KM算法定理：如果一個相等子圖中包含完備匹配，那么這個匹配就是最優(yōu)匹配證明：由于在算法過程一直保持頂標(biāo)的可行性，所以任意一個匹配的權(quán)值和肯定小于等于所有結(jié)點(diǎn)的頂標(biāo)之和，則相等子圖中的完備匹配肯定是最優(yōu)匹配KM算法定理：如果一個相等子圖中包含完備匹配，那么這個匹配就24KM算法算法流程設(shè)頂點(diǎn)Xi的頂標(biāo)為a[i]，頂點(diǎn)Yi的頂標(biāo)為b[i]ⅰ.初始時，a[i]為與Xi相關(guān)聯(lián)的邊的最大權(quán)值，b[j]=0，保證a[i]+b[j]>=w(i,j)成立ⅱ.當(dāng)相等子圖中不包含完備匹配時，就適當(dāng)修改頂標(biāo)以擴(kuò)大相等子圖，直到找到完備匹配為止ⅲ.修改頂標(biāo)的方法KM算法算法流程25KM算法當(dāng)從Xi尋找增廣路失敗后，得到一棵交錯樹，它的所有葉子節(jié)點(diǎn)都是X節(jié)點(diǎn)，對交錯樹中X頂點(diǎn)的頂標(biāo)減少d值，Y頂點(diǎn)的頂標(biāo)增加d值，對于圖中所有的邊(i,j)，可以看到i和j都不在交錯樹中，邊(i,j)仍然不屬于相等子圖i和j都在交錯樹中，邊(i,j)仍然屬于相等子圖i不在交錯樹中，j在交錯樹中，a[i]+b[j]擴(kuò)大，邊(i,j)不屬于相等子圖KM算法當(dāng)從Xi尋找增廣路失敗后，得到一棵交錯樹，它的所有葉26KM算法i在交錯樹,j不在交錯樹中,邊(i,j)有可能加入到相等子圖中為了使a[i]+b[j]>=w(i,j)始終成立,且至少有一條邊加入到相等子圖中,d=min{a[i]+b[j]-w(i,j)},i在交錯樹中,j不在交錯樹中KM算法i在交錯樹,j不在交錯樹中,邊(i,j)有可能加入到27假設(shè)有3個人,我們弄個簡化版的.每個人與家的距離如下圖第一個人到家1,2,3的距離為3,5,4,第二個人只能到家1,2距離為2,4,第三個人只能到家3,距離為7;345247manhome123321假設(shè)有3個人,我們弄個簡化版的.每個人與家的距離如下圖34528345247manhome123321改變a,b后345247manhome123321ab437010重新匹配左節(jié)點(diǎn)2找到增廣路b010345247manhome123321a437對左節(jié)點(diǎn)3進(jìn)行匹配345247manhome123321改變a,b后3452429345247manhome123321ab437010345247manhome123321ab336011找到最優(yōu)匹配345247manhome123321改變a,bab336011重新匹配左節(jié)點(diǎn)3,找到增廣路345247manhome123321ab43701034530回到例題:PKU2195題目是說有N個人跟N個房子,每個人跟房子都有一定的距離,現(xiàn)在要讓這N個人全部回到N個房子里面去,要求所有人回去的距離最短.那么求的就是最小權(quán)匹配了,那么如果我們把所有邊的權(quán)值取反,如圖所示,求其最大匹配,那么結(jié)果就是我們要的了.問題解決.345247manhome123321-3-4-5-2-4-7manhome123321回到例題:PKU2195345247manhome1233231練習(xí)題Pku2239,2536Pku3041,1325,2226pku1466Pku1422,2594pku2195練習(xí)題Pku2239,253632THEENDTHEEND33二分圖匹配二分圖匹配34Bi-partitegraph二分圖的定義：二分圖是這樣的一個圖，它的頂點(diǎn)可以分為兩個集合X和Y。所有的邊關(guān)聯(lián)的兩個頂點(diǎn)中，恰好一個屬于集合X，一個屬于集合Y。123456二分圖的匹配：給定一個二分圖G，M為G邊集的一個子集，如果M滿足當(dāng)中的任意兩條邊都不依附于同一個頂點(diǎn)，則稱M是一個匹配。Bi-partitegraph二分圖的定義：123456二35二分圖的最大匹配定義：圖中包含邊數(shù)最多的匹配稱為圖的最大匹配。如右圖所示：藍(lán)色部分就構(gòu)成一個最大匹配，同時它也是一個完美匹配完美匹配：如果所有點(diǎn)都在匹配邊上，稱這個最大匹配是完美匹配。

二分圖的最大匹配定義：如右圖所示：藍(lán)色部分36二分圖的最大匹配匈牙利算法（時間復(fù)雜度O(nm)） 其思想是用寬度優(yōu)先搜索來找增廣路徑（和floodfill算法類似轉(zhuǎn)化為單位容量簡單網(wǎng)絡(luò)的最大流問題在二分圖的基礎(chǔ)上，加入源點(diǎn)s和匯點(diǎn)t，讓s與每個X結(jié)點(diǎn)連一條邊，每個Y結(jié)點(diǎn)和t連一條邊，所有弧的容量為1。這樣，飽和弧就對應(yīng)著匹配邊。二分圖的最大匹配匈牙利算法（時間復(fù)雜度O(nm)） 37二分圖的最大匹配匈牙利算法：尋找增廣路：初始時最大匹配為空

for二分圖左半邊的每個點(diǎn)i

do從點(diǎn)i出發(fā)尋找增廣路徑如果找到，則把它取反（即增加了總了匹配數(shù)）。看一道例題：PKU1469二分圖的最大匹配匈牙利算法：38PKU1469一共有N個學(xué)生跟P門課程,一個學(xué)生可以任意選一門或多門課,問是否達(dá)成: 1.每個學(xué)生代表的都是不同的課（如果一個學(xué)生選修的那門課，那么他就可以代表這門課） 2.每門課都有一個代表PKU1469一共有N個學(xué)生跟P門課程,一個學(xué)39PKU1469輸入為:PN(課程數(shù)跟學(xué)生數(shù))接著有P行,格式為Countstudentistudenti+1……studentcount(Count表示對課程1感興趣的學(xué)生數(shù),接著有Count個學(xué)生)如第一行212表示學(xué)生1跟學(xué)生2對課程1感興趣輸出為:若每門課都能找到一位代表則輸出”YES”,否則為”NO”PKU1469輸入為:40PKU1469假如有三個學(xué)生跟三門課程,學(xué)生1,2,3.為了跟學(xué)生區(qū)分,假設(shè)3個課程為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中尋找最大匹配,只要這個最大匹配大于或等于課程數(shù)P,那么就達(dá)到要求了.PKU1469假如有三個學(xué)生跟三門課程,學(xué)生1,2,3.為了41尋找最大匹配的匈牙利算法流程

首先我們先看節(jié)點(diǎn)1,尋找下一條邊,假設(shè)找到節(jié)點(diǎn)5,因為1跟5都還沒匹配,所以找到一個匹配.標(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)尋找下一條邊時,如圖中的藍(lán)邊,我們發(fā)現(xiàn)節(jié)點(diǎn)6的yM[6]=2;已經(jīng)匹配了.此時我們就轉(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還沒匹配.于是我們找到了一個增廣路徑增廣路如圖中箭頭所示尋找最大匹配的匈牙利算法流程

首先我們先看節(jié)點(diǎn)1,尋找下一條42123456把圖中紅色線去掉藍(lán)色線加上123456123456找到一個更好的匹配更改各自的匹配點(diǎn)123456把圖中紅色線去掉藍(lán)色線加上1234561234543總結(jié)所以流程就是:1,對于一個未匹配的節(jié)點(diǎn)u,尋找它的每條邊,如果它的邊上的另一個節(jié)點(diǎn)v還沒匹配則表明找到了一個匹配,直接轉(zhuǎn)步驟4;2,假如節(jié)點(diǎn)u它邊上的另一個節(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;總結(jié)所以流程就是:44最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點(diǎn)關(guān)聯(lián)?？梢宰C明：最少的點(diǎn)（即覆蓋數(shù)）＝最大匹配數(shù)M簡單的證明如下：（1）M個是足夠的。只需要讓它們覆蓋最大匹配的M條邊，則其它邊一定被覆蓋（如果有邊e不被覆蓋，把e加入后得到一個更大的匹配）（2）M個是必需的，僅考慮形成最大匹配的這M條邊，由于它們兩兩之間沒有公共點(diǎn)，因此至少需要M個點(diǎn)才可以把它們覆蓋

最小點(diǎn)覆蓋最小覆蓋：最小覆蓋要求用最少的點(diǎn)（Ｘ集合或Ｙ集合45PKU3041:(類似的有PKU3020)

問題:假如你現(xiàn)在正處在一個N*N的矩陣中,這個矩陣?yán)锩嬗蠯個障礙物,你擁有一把武器,一發(fā)彈藥一次能消滅一行或一列的障礙物,求最小的彈藥消滅全部障礙物輸入為:NK接下來有K行,每行包含障礙物的坐標(biāo),即r行c列;如:3411132232輸出為:花費(fèi)最小的彈藥數(shù)PKU3041:(類似的有PKU3020)

問題:46PKU3041對于上面那個數(shù)據(jù)我們可以用下面的表示,0表示無障礙物,1表示有;101010010首先,我們利用行跟列做二分圖:123123行列如果第i行的第j列有障礙物,則在圖中左邊的i行連一條邊到右邊的j列,上面的數(shù)據(jù)就對應(yīng)左圖于是問題就轉(zhuǎn)化成最小點(diǎn)覆蓋的問題.求最大匹配即可.PKU3041對于上面那個數(shù)據(jù)我們可以用下面的表示,0表示無47PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU2226PKU2226現(xiàn)在我們看一道構(gòu)圖比較復(fù)雜的題：PKU222648DAG圖的最小路徑覆蓋用盡量少的不相交簡單路徑覆蓋有向無環(huán)(DAG)G的所有頂點(diǎn)，這就是DAG圖的最小路徑覆蓋問題。解決此類問題可以建立一個二分圖模型。把所有頂點(diǎn)i拆成兩個：Ｘ結(jié)點(diǎn)集中的i和Y結(jié)點(diǎn)集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設(shè)二分圖最大匹配為m,則結(jié)果就是n-m

記住一個重要的結(jié)論：

DAC圖的最小路徑覆蓋數(shù)=節(jié)點(diǎn)數(shù)(n)-最大匹配數(shù)看一道例題：PKU1422DAG圖的最小路徑覆蓋用盡量少的不相交簡單路徑覆蓋有向無環(huán)(49PKU1422有一個城鎮(zhèn)，它的所有街道都是單行的，并且每條街道都是和兩個路口相連。同時已知街道不會形成回路。你的任務(wù)是編寫程序求最小數(shù)量的傘兵，這些傘兵可以訪問（visit）所有的路口。對于傘兵的起始降落點(diǎn)不做限制。Input:

3

34

13

23Output:2PKU1422有一個城鎮(zhèn)，它的所有街道都是單行的，并且50132412344’3’2’1’132412344’3’2’1’51二分圖的最大獨(dú)立集最大獨(dú)立集問題：在Ｎ個點(diǎn)的圖G中選出m個點(diǎn)，使這m個點(diǎn)兩兩之間沒有邊．求m最大值．記住一個重要的結(jié)論：二分圖的最大獨(dú)立集數(shù)=節(jié)點(diǎn)數(shù)(n)-最大匹配數(shù)二分圖的最大獨(dú)立集最大獨(dú)立集問題：在Ｎ個點(diǎn)的圖G中選出m個52黑色點(diǎn)即為一個最大獨(dú)立集可以這樣理解，在總的點(diǎn)集中，去掉最少的點(diǎn)，使得剩下的點(diǎn)相互之間沒有邊。用最少的點(diǎn)去覆蓋所有的邊，也就是最小覆蓋。黑色點(diǎn)即為一個最大獨(dú)立集可以這樣理解，在總的點(diǎn)集中，去掉最少53二分圖最優(yōu)匹配又稱帶權(quán)最大匹配。二分圖的每條邊帶有權(quán)值。求一個匹配使得匹配邊上的權(quán)值和最大。一般X和Y集合頂點(diǎn)個數(shù)相同，最優(yōu)匹配也是一個完備匹配，即每個頂點(diǎn)都被匹配。如果個數(shù)不相等，可以通過補(bǔ)點(diǎn)加0邊實(shí)現(xiàn)轉(zhuǎn)化。最??？看一道例題：PKU2195二分圖最優(yōu)匹配又稱帶權(quán)最大匹配。54PKU2195題意：有N個人跟N個房子,每個人跟房子都有一定的距離,現(xiàn)在要讓這N個人全部回到N個房子里面去,要求所有人回去的距離最短.現(xiàn)在我們假設(shè)要求的是最大距離.那么就是求最大權(quán)匹配.下面我們先介紹一下KM算法PKU2195題意：55KM算法基本概念：可行頂標(biāo)和相等子圖可行頂標(biāo)：L是一個關(guān)于結(jié)點(diǎn)的函數(shù)，L(x)是頂點(diǎn)x對應(yīng)的頂標(biāo)值?？尚许敇?biāo)對于圖中的每條邊(x,y)都有L(x)+L(y)>=w(x,y)相等子圖：只包含L(x)+L(y)=w(x,y)的邊的子圖KM算法基本概念：可行頂標(biāo)和相等子圖56KM算法定理：如果一個相等子圖中包含完備匹配，那么這個匹配就是最優(yōu)匹配證明：由于在算法過程一直保持頂標(biāo)的可行性，所以任意一個匹配的權(quán)值和肯定小于等于所有結(jié)點(diǎn)的頂標(biāo)之和，則相等子圖中的完備匹配肯定是最優(yōu)匹配KM算法定理：如果一個相等子圖中包含完備匹配，那么這個匹配就57KM算法算法流程設(shè)頂點(diǎn)Xi的頂標(biāo)為a[i]，頂點(diǎn)Yi的頂標(biāo)為b[i]ⅰ.初始時，a[i]為與Xi相關(guān)聯(lián)的邊的最大權(quán)值，b[j]=0，保證a[i]+b[j]>=w(i,j)成立ⅱ.當(dāng)相等子圖中不包含完備匹配時，就適當(dāng)修改頂標(biāo)以擴(kuò)大相等子圖，直到找到完備匹配為止ⅲ.修改頂標(biāo)的方法KM算法算法流程58KM算法當(dāng)從Xi尋找增廣路失敗后，得到一棵交錯樹，它的所有葉子節(jié)點(diǎn)都是X節(jié)點(diǎn)，對交錯樹中X頂點(diǎn)的頂標(biāo)減少d值，Y頂點(diǎn)的頂標(biāo)增加d值，對于圖中所有的邊(i,j)，可以看到i和j都不在交錯樹中，邊(i,j)仍然不屬于相等子圖i和j都在交錯樹中，邊(i,j)仍然屬于相等子圖i不在交錯樹中，j在交錯樹中，a[i]+b[j]擴(kuò)大，邊(i,j)不屬于相等子圖KM算法當(dāng)從Xi尋找增廣路失敗后，