二分圖最大匹配及常用建圖方法(共8頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法藝術(shù)二分圖匹配剖析很多人說，算法是一種藝術(shù)。但是對(duì)于初學(xué)者的我，對(duì)算法認(rèn)識(shí)不是很深刻，但偶爾也能感受到他強(qiáng)大的魅力與活力。這讓我追求算法的腳步不能停止。下面我通過分析匈牙利算法以及常用建圖方式，與大家一起欣賞算法的美。匈牙利算法匈牙利算法是用來解決最大二分圖匹配問題的，所謂二分圖即 “一組點(diǎn)集可以分為兩部分，且每部分內(nèi)各點(diǎn)互不相連，兩部分的點(diǎn)之間可以有邊”。所謂最大二分圖匹配即 ”對(duì)于二分圖的所有邊，尋找一個(gè)子集，這個(gè)子集滿足兩個(gè)條件，1：任意兩條邊都不依賴于同一個(gè)點(diǎn)。2：讓這個(gè)子集里的邊在滿足條件一的情況下盡量多。首先可以想到的是，我們可以通過搜索，找出所有的這

2、樣的滿足上面條件的邊集，然后從所有的邊集中選出邊數(shù)最多的那個(gè)集合，但是我們可以感覺到這個(gè)算法的時(shí)間復(fù)雜度是邊數(shù)的指數(shù)級(jí)函數(shù)，因此我們有必要尋找更加高效的方法。目前比較有效的方法有匈牙利算法和通過添加匯點(diǎn)和源點(diǎn)的網(wǎng)絡(luò)流算法，對(duì)于點(diǎn)的個(gè)數(shù)都在200 到300 之間的數(shù)據(jù)，我們是采取匈牙利算法的，因?yàn)樾傺览惴▽?shí)現(xiàn)起來要比網(wǎng)絡(luò)流簡單些。下面具體說說匈牙利算法： 介紹匈牙利之前，先說說“增廣軌”。定義：若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬最大匹配邊集M的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對(duì)于M的一條增廣軌定義總是抽象的下面通過圖來理解它。 圖中的線段（2-3,

3、 3-1, 1-4）便是上面所說的p路徑，我們假定邊（1,3）是以匹配的邊，（2,3）（1,4）是未匹配的邊，則邊（4,1）邊（1,3）和 邊（3,2） 在路徑p上交替的出現(xiàn)啦，那么p就是相對(duì)于M的一條增廣軌，這樣我們就可以用邊1,4 和 邊2,3來替換邊1,3 那么以匹配的邊集數(shù)量就可以加1,。匈牙利算法就是同過不斷的尋找增廣軌實(shí)現(xiàn)的。很明顯如果二分圖的兩部分點(diǎn)分別為n和m，那么最大匹配的數(shù)目應(yīng)該小于等于MIN（n,m）; 因此我們可以枚舉任第一部分（的二部分也可以）里的每一個(gè)點(diǎn)，我們從每個(gè)點(diǎn)出發(fā)尋找增廣軌，最后吧第一部分的點(diǎn)找完以后，就找到了最大匹配的數(shù)目，當(dāng)然我們也可以通過記錄找出這些邊

4、。下面給出關(guān)于二分圖最大匹配的兩個(gè)定理 1:最大匹配數(shù) + 最大獨(dú)立集 = n + m 2:二分圖的最小覆蓋數(shù) = 最大匹配數(shù) 3:最小路徑覆蓋 = 最大獨(dú)立集 最大獨(dú)立集是指求一個(gè)二分圖中最大的一個(gè)點(diǎn)集，該點(diǎn)集內(nèi)的點(diǎn)互不相連。 最小頂點(diǎn)覆蓋是指 在二分圖中，用最少的點(diǎn)，讓所有的邊至少和一個(gè)點(diǎn)有關(guān)聯(lián)。 最小路徑覆蓋是指一個(gè)不含圈的有向圖G中，G的一個(gè)路徑覆蓋是一個(gè)其結(jié)點(diǎn)不相交的路徑集合P，圖中的每一個(gè)結(jié)點(diǎn)僅包含于P中的某一條路徑。路徑可以從任意結(jié)點(diǎn)開始和結(jié)束，且長度也為任意值，包括0下面給出二分圖最大匹配的偽代碼：/* usei 數(shù)組時(shí)標(biāo)記第二部分點(diǎn)中的第j個(gè)點(diǎn)是否使用過。 matchi 與第

5、二部分中的點(diǎn)i 匹配的點(diǎn)是 matchi*/Int GetAugmentPath ( number ) /通過number這個(gè)點(diǎn)尋找增廣軌，找到返回1找不到返回0；P relatednumber . next; / 與 number 相連的點(diǎn)；While（p != NULL）If not usedp then / p 點(diǎn)沒有被使用過If matchp = 0 or GetAugmentPath(matchp) / p點(diǎn)沒有和另一部分的點(diǎn)配對(duì) / 或 和p配對(duì)的那個(gè)點(diǎn)可以找到其它點(diǎn)和他配對(duì)（找到增廣軌 ）Return 1;p p . next / 與 number 相連的下幾個(gè)點(diǎn) Return

6、0; end GetAugmentPath;我們只需要在主程序中對(duì)某一部分點(diǎn)集的每個(gè)點(diǎn)進(jìn)行增廣軌的尋找；Int mainans 0 For I = 1 n / 枚舉第一部分的n個(gè)點(diǎn)；For j = 1 m usej false / 把第二部分的m個(gè)點(diǎn)表示為沒有使用過。if GetAugmentPath (i) thenans ans + 1/ 找到增廣軌就給邊數(shù)加一； 程序非常好寫，也非常好懂。1 2 3 4 5 6 7 1 2 3 4 5 6 7 8每次我們從上面的第i個(gè)點(diǎn)出發(fā)盡量去找一個(gè)能唯一和它匹配的點(diǎn)p，策略有兩種，一是直接在下面的點(diǎn)中找到一個(gè)點(diǎn)p，他沒有和上面的點(diǎn)匹配過（即match

7、p =0）。二是當(dāng)p和上面的某個(gè)點(diǎn)匹配過，即（matchp） 那么我們就從matchp出發(fā)，去給他找下面另外的點(diǎn)和他匹配，把p點(diǎn)留給點(diǎn)i。這樣我們不就多找到了一條？然而 對(duì)于匈牙利算法來說，難點(diǎn)并不在與程序本身，而是在如何把實(shí)際問題轉(zhuǎn)化為最大二分圖匹配的模型，然后再利用匈牙利算法解決。 下面我們說幾種常見的建圖模型。常見建圖模型法一 行列匹配法101010100 上圖是一個(gè)3 * 3 的矩陣，方格內(nèi)的1表示這個(gè)地方有敵人，0表示沒有敵人，現(xiàn)在我們有很多箭，每根箭可以殺死一行或者一列的敵人，問題是，我們要?dú)⑺浪械臄橙酥烈玫綆赘?？初看似乎和最大二分圖沒有什么相關(guān)聯(lián)的，然而如果我們轉(zhuǎn)換一下視角

8、，這樣思考：我們要?dú)⑺滥硞€(gè)敵人，只要讓他所在的位置有箭經(jīng)過就行。也就是所有的位置都被箭覆蓋就行，對(duì)就是覆蓋，就是頂點(diǎn)的最小覆蓋，既然是頂點(diǎn)的最小覆蓋，而且我們要?dú)⒌氖菙橙?，那么我們的點(diǎn)就應(yīng)該是敵人的位子，即（行列）對(duì)于上面那個(gè)圖我么可以建立下面這個(gè)模型有人在的坐標(biāo)是（1,1 1,3 2,2 3,1） 我們就用這幾個(gè)點(diǎn)的橫縱坐標(biāo)建圖 1 1 2 2 3 3 （每個(gè)點(diǎn)的橫坐標(biāo)是第一部分，縱坐標(biāo)是另一部分，被邊相連的兩個(gè)數(shù) 字表示一個(gè)點(diǎn)）上面我們說過，一個(gè)二分圖的最小頂點(diǎn)覆蓋就是要找到最少的邊把所有的頂點(diǎn)覆蓋，正好符合這個(gè)題的要求，上面還給出了一個(gè)性質(zhì)，即二分圖的最小頂點(diǎn)覆蓋是等于二分圖的最大匹配。

9、所以我們只需要對(duì)上面的那個(gè)二分圖就最大匹配就行，這樣把原本的問題轉(zhuǎn)變的很簡單了。法二 黑白染色法101111001又是一個(gè)圖，要求是把方格里的所有的1改為零，一次最多只能修改相鄰的兩個(gè)，為最少需要修改幾次？ 有是一個(gè)求最值得問題，但是似乎用于求最值的算法（貪心，動(dòng)態(tài)規(guī)劃）都派不上用場，既然在這里提出，那么他肯定能用二分圖最大匹配解決，關(guān)鍵是如何建圖？既然是每次只能拿相鄰的兩個(gè)，是兩個(gè)，正好我們匹配的時(shí)候也是找兩個(gè)進(jìn)行匹配，這是否就是這個(gè)題和最大二分圖匹配相聯(lián)系的地方呢？ 對(duì) 就是這里。但是每個(gè)點(diǎn)能和他四周的四個(gè)點(diǎn)匹配，那么我們?cè)趺窗阉械狞c(diǎn)分成來那個(gè)部分呢？ 對(duì) 就是要把第i個(gè)點(diǎn)放到第一部分，

10、第I個(gè)點(diǎn)周圍的四個(gè)點(diǎn)放到第二部分，再把這四個(gè)點(diǎn)周圍的16點(diǎn)放到第1部分有了這樣的思想，我們只需對(duì)原圖做這樣的改動(dòng)：黑白染色使四周和中間的顏色不同。白1黑白5黑2白3黑4白黑白6圖中黑白的意思是就是把點(diǎn)分類，圖里的1,2,3,4,5,6表示的就是上面那個(gè)0,1圖的1的個(gè)數(shù)然后建圖，把相鄰的點(diǎn)相連，比如說1和2 2和3 。白色 黑色 1 3 25 46然后要把所有一改為零，也就是要對(duì)每個(gè)點(diǎn)都操作，每個(gè)點(diǎn)都要有，那不就是最小頂點(diǎn)覆蓋嗎？對(duì)，這個(gè)問題有解決了。法三 反建法問題背景：一個(gè)極度封建的老師要帶同學(xué)們出去玩，但是他怕在途中同學(xué)之間發(fā)生戀情老師研究了一下發(fā)現(xiàn)，滿足下面幾種條件的兩個(gè)同學(xué)之間發(fā)生戀

11、情的可能性很小1身高差 40 2性別相同3愛好不同的音樂 4愛好同類型的運(yùn)動(dòng)顯然如果我們用滿足上面條件的同學(xué)之間建邊那么最后建立起來的就不是二分圖了。稍微觀察一下，男生之間我們是隨便帶的，女生也是，因?yàn)樗麄儽舜诵詣e相同。因此我們就可以把男女分為兩部分，那么男女之間如何建邊？如果我們把男女滿足不發(fā)生戀情的連起來，那么求出來的最大匹配沒有代表性，不能得到我們想要的結(jié)果。因此我們用反建法，把男女中可能發(fā)生戀情的建立邊。也就是說把身高差=40 或 愛好相同音樂 或 愛好不同類型運(yùn)動(dòng)的男女同學(xué)之間用邊連起來。 然后求一個(gè)最大獨(dú)立集，最大獨(dú)立集的原則不就是找到一個(gè)點(diǎn)集，使得集合內(nèi)的點(diǎn)互不相連且點(diǎn)盡量多嗎？

12、我們把可能發(fā)生戀情的男女相連，那么最大獨(dú)立集不就是我們要找的不可能發(fā)生戀情的人的集合嗎？ 那么， 這個(gè)問題解決了！法四 拆點(diǎn)法拆點(diǎn)法是用于解決最小路徑覆蓋問題的，給出一個(gè)圖 要找到幾條路徑，可以把所有的點(diǎn)經(jīng)過，并且路徑之間不可以交叉。我們的做法是把點(diǎn)拆成兩部分（點(diǎn)1 拆為x1,y1. 點(diǎn)2拆為x2,y2）如果我們對(duì)這個(gè)圖求二分圖的最大匹配，你會(huì)發(fā)現(xiàn)每個(gè)匹配對(duì)應(yīng)著一個(gè)路徑覆蓋，因此，此二分圖的最大匹配即：原圖中的最小路徑覆蓋上的邊的個(gè)數(shù)（路徑是由0條，1條或多條邊組成的）。那么原圖的最小路徑覆蓋數(shù) = 原圖頂點(diǎn)數(shù) 最小路徑上的邊數(shù) 也就是 原圖的最小路徑覆蓋數(shù) = 原圖頂點(diǎn)數(shù) 二分圖最大匹配數(shù)。

13、 法五 一行變多行，一列變多列#上面是一個(gè)4*4的方格，方格內(nèi)的#表示墻，我們要在表格內(nèi)沒有墻的地方建立碉堡，而且要保證任何兩個(gè)碉堡之間互相不能攻擊，問最多能建多少個(gè)碉堡？是否感覺像第一個(gè)題呢？如果我們向第一個(gè)題那樣建圖，那么最后求出來的最大匹配也就是行和列的匹配。而且這個(gè)匹配滿足了所有匹配都是不同行不同列（匹配本身的性質(zhì)就是每個(gè)點(diǎn)至多屬于匹配中的某個(gè)邊）。但是這樣的建圖的話，我們墻怎么處理？ 有墻的地方就相當(dāng)于把這一行和這一列分成了兩行，兩列。例如# 等價(jià)于 還是一行 # 等價(jià)于 # #和 一行變成了兩行對(duì)就是這么分的。 1,11,2#1,4#2,22,32,43,13,2#4,1#4,34,4 原圖 1,11,2#2,4#3,23,33,44,54,2#5,5#6,66,7（因?yàn)橛辛藟λ缘谝恍凶優(yōu)閮尚校ㄒ驗(yàn)樯厦嬗辛硕泄讨荒軓牡谌虚_始）（因?yàn)榈谝涣杏辛藟Γ塘袛?shù)增加為5）（第3,4列有了墻，固列數(shù)增加到了6和7） 一行變多行，一列變多列后的圖然后我們按照這個(gè)編號(hào)見圖即可 1 1 2 2 3 3 4 4 5 5 6 6 7對(duì)這個(gè)圖求二分圖最大匹配即可。