二分圖匹配匹配.ppt

《二分圖匹配匹配.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、圖論2江川二分圖一個(gè)圖的點(diǎn)集可以劃分為兩個(gè)不相交的子集，每一個(gè)子集中的點(diǎn)和該子集中的其他點(diǎn)沒(méi)有邊相連二分圖一個(gè)圖是二分圖的充要條件是這個(gè)圖里沒(méi)有奇環(huán)二分圖匹配匹配：給定一個(gè)二分圖G，M為G邊集的一個(gè)子集，如果M滿足當(dāng)中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。最大匹配：所有匹配中邊數(shù)最多的。完備匹配：如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完備匹配。二分圖匹配Hall定理一個(gè)二分圖有完備匹配的充要條件是：任意k個(gè)點(diǎn)相鄰的點(diǎn)的集合中不少于k個(gè)點(diǎn)匈牙利算法M-交錯(cuò)路：p是G的一條通路，如果p中的邊為

2、屬于M中的邊與不屬于M的邊交替出現(xiàn)，則稱p是一條M-交錯(cuò)路。M-飽和點(diǎn)：對(duì)于v∈V(G），如果v與M中的某條邊關(guān)聯(lián)，則稱v是M-飽和點(diǎn)，否則稱v是非M-飽和點(diǎn)。M-可增廣路：p是一條M-交錯(cuò)路，如果p的起點(diǎn)和終點(diǎn)都是非M-飽和點(diǎn)，則稱p為M-可增廣路。匈牙利算法匈牙利算法ForalliinX:1、從i出發(fā)尋找可增廣路2、沿增廣路更新（刪除原屬于M的邊，增加不屬于M的邊）O(nm)匈牙利算法匈牙利算法匈牙利算法應(yīng)用1點(diǎn)覆蓋集：圖的頂點(diǎn)集的子集，覆蓋圖中所有的邊最小點(diǎn)覆蓋：無(wú)向圖中，求最少需要多少個(gè)點(diǎn)可以覆蓋所有的邊。NP應(yīng)用1二分

3、圖的最小點(diǎn)覆蓋應(yīng)用1K?nig定理：二分圖的最小點(diǎn)覆蓋=最大匹配應(yīng)用1假設(shè)最小點(diǎn)覆蓋=N，最大匹配=M考慮最大匹配中的邊兩兩不相交，所以至少需要M條邊覆蓋。得N>=M應(yīng)用2獨(dú)立集:圖的頂點(diǎn)集的子集，其中任意兩點(diǎn)不相鄰。最大點(diǎn)獨(dú)立集:無(wú)向圖中，求一個(gè)最大的頂點(diǎn)集，其中任意兩點(diǎn)不相鄰。NP應(yīng)用2覆蓋集的補(bǔ)集一定是獨(dú)立集證明：假設(shè)某一覆蓋集的補(bǔ)集不是獨(dú)立集。說(shuō)明有一條邊連接了覆蓋集的補(bǔ)集的兩個(gè)點(diǎn)。那么這條邊沒(méi)有被覆蓋集所覆蓋，產(chǎn)生矛盾。應(yīng)用2獨(dú)立集的補(bǔ)集一定是覆蓋集證明：假設(shè)某一獨(dú)立集的補(bǔ)集不是覆蓋集。說(shuō)明有一條邊不被獨(dú)立集的補(bǔ)集覆蓋

4、，那么這條邊連接了獨(dú)立集的兩個(gè)端點(diǎn)，產(chǎn)生矛盾。應(yīng)用2覆蓋集與獨(dú)立集互為補(bǔ)集二分圖中可求出最大匹配M最小覆蓋集=M，最大獨(dú)立集=n-M應(yīng)用3一共N個(gè)男孩和女孩參加聚會(huì)，某些男孩和女孩之間會(huì)產(chǎn)生戀愛(ài)關(guān)系。現(xiàn)在希望找到最多的孩子，他們之間不會(huì)產(chǎn)生戀愛(ài)關(guān)系。應(yīng)用3男孩在一邊，女孩在一邊會(huì)產(chǎn)生戀愛(ài)關(guān)系的連邊找最大獨(dú)立集應(yīng)用4一共N個(gè)人參加聚會(huì)，某些人之間會(huì)產(chǎn)生戀愛(ài)關(guān)系（一定是異性之間）?，F(xiàn)在希望找到最多的人，他們之間不會(huì)產(chǎn)生戀愛(ài)關(guān)系。應(yīng)用4所有的人復(fù)制成兩份放在兩邊會(huì)產(chǎn)生戀愛(ài)關(guān)系的連邊最大獨(dú)立集=N–最大匹配/2應(yīng)用5給你一個(gè)N*N的格子

5、，每個(gè)格子里要么有一個(gè)隕石，要么為空。每一次你可以清除一行或者一列里的所有隕石，求最少要多少次才能把所有的隕石清除干凈。XXXX應(yīng)用5把N*N的格子看成是一個(gè)二分圖，每一行是一個(gè)集合的點(diǎn)，每一列是另一個(gè)集合的點(diǎn)，那么某個(gè)格子（x,y）中有隕石就相當(dāng)于頂點(diǎn)x到頂點(diǎn)y有一條邊，那么要求使隕石全部被清理掉的最少的次數(shù)，就是要使該二分圖中的所有邊都被覆蓋的最少頂點(diǎn)數(shù)。XXXX應(yīng)用6動(dòng)物園有N只貓，M只狗，P個(gè)小孩。每個(gè)小孩都有自己喜歡的和討厭的動(dòng)物。如果他喜歡狗，那么就討厭貓；如果他討厭貓，那么他就喜歡狗。每個(gè)小孩會(huì)說(shuō)，我喜歡__號(hào)貓，

6、討厭__號(hào)狗；或者說(shuō)，我喜歡__號(hào)狗，討厭__號(hào)貓。如果他喜歡的那只動(dòng)物被留下，而且討厭的那只動(dòng)物被帶走，他就會(huì)開心。請(qǐng)問(wèn)最多有多少小孩能開心。應(yīng)用6現(xiàn)在要求最多的小孩，兩兩之間不矛盾從矛盾關(guān)系入手貓和貓之間，狗和狗之間一定不存在矛盾關(guān)系如果A小孩喜歡的動(dòng)物與B小孩討厭的動(dòng)物一樣，或者A小孩討厭的動(dòng)物與B小孩喜歡的動(dòng)物一樣，那AB之間就存在著排斥關(guān)系，則他們之間連接一條邊（他們不可能同時(shí)開心）?求最大的點(diǎn)集，兩兩之間沒(méi)有邊最大點(diǎn)獨(dú)立集應(yīng)用7路徑覆蓋：路徑覆蓋就是在圖中找一些路徑，使之覆蓋了圖中的所有頂點(diǎn)，且任何一個(gè)頂點(diǎn)有且只有一

7、條路徑與之關(guān)聯(lián)。注意一個(gè)單獨(dú)的點(diǎn)也是一條路徑?，F(xiàn)要求有向無(wú)環(huán)圖的最小路徑覆蓋，即在一張有向無(wú)環(huán)圖中，找路徑數(shù)最少的路徑覆蓋。應(yīng)用7把每個(gè)頂點(diǎn)拆成兩份，然后按原圖連邊。應(yīng)用7最小路徑覆蓋=n–最大匹配每一個(gè)匹配相當(dāng)于原圖中的某兩個(gè)路徑合并應(yīng)用8在一個(gè)有向無(wú)環(huán)圖上，至少放多少個(gè)機(jī)器人可以遍歷整個(gè)圖？注意點(diǎn)是可以重復(fù)經(jīng)過(guò)的。應(yīng)用8允許重復(fù)經(jīng)過(guò)點(diǎn)的最小路徑覆蓋如果經(jīng)過(guò)一個(gè)重復(fù)的點(diǎn)我們可以假裝跳過(guò)了它進(jìn)入下一個(gè)點(diǎn)?Floyed求出傳遞閉包再做最小路徑覆蓋應(yīng)用9在一個(gè)N*M的矩形里，有一些格子被毀壞?，F(xiàn)在要求用1*2的木板去覆蓋沒(méi)有被毀壞的

8、格子，木板不可覆蓋彼此，問(wèn)是否能把每個(gè)格子都蓋住。應(yīng)用9所有沒(méi)有被毀壞的格子都看成圖中的點(diǎn)按格子的“奇偶性”分成兩類如果兩個(gè)格子相鄰，則在這兩個(gè)點(diǎn)上連邊若存在完備匹配則所有的格子可以被覆蓋應(yīng)用10A機(jī)器有n個(gè)模式，B機(jī)器有m個(gè)模式。現(xiàn)有k個(gè)任務(wù)需要做，可以用A