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

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

2、樣的滿足上面條件的邊集，然后從所有的邊集中選出邊數(shù)最多的那個集合，但是我們可以感覺到這個算法的時間復(fù)雜度是邊數(shù)的指數(shù)級函數(shù)，因此我們有必要尋找更加高效的方法。目前比較有效的方法有匈牙利算法和通過添加匯點和源點的網(wǎng)絡(luò)流算法，對于點的個數(shù)都在200 到300 之間的數(shù)據(jù)，我們是采取匈牙利算法的，因為匈牙利算法實現(xiàn)起來要比網(wǎng)絡(luò)流簡單些。下面具體說說匈牙利算法： 介紹匈牙利之前，先說說“增廣軌”。定義：若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬最大匹配邊集M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對于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就是相對于M的一條增廣軌，這樣我們就可以用邊1,4 和 邊2,3來替換邊1,3 那么以匹配的邊集數(shù)量就可以加1,。匈牙利算法就是同過不斷的尋找增廣軌實現(xiàn)的。很明顯如果二分圖的兩部分點分別為n和m，那么最大匹配的數(shù)目應(yīng)該小于等于MIN（n,m）; 因此我們可以枚舉任第一部分（的二部分也可以）里的每一個點，我們從每個點出發(fā)尋找增廣軌，最后吧第一部分的點找完以后，就找到了最大匹配的數(shù)目，當(dāng)然我們也可以通過記錄找出這些邊

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

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

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

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

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

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

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

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

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

13、 法五 一行變多行，一列變多列#上面是一個4*4的方格，方格內(nèi)的#表示墻，我們要在表格內(nèi)沒有墻的地方建立碉堡，而且要保證任何兩個碉堡之間互相不能攻擊，問最多能建多少個碉堡？是否感覺像第一個題呢？如果我們向第一個題那樣建圖，那么最后求出來的最大匹配也就是行和列的匹配。而且這個匹配滿足了所有匹配都是不同行不同列（匹配本身的性質(zhì)就是每個點至多屬于匹配中的某個邊）。但是這樣的建圖的話，我們墻怎么處理？ 有墻的地方就相當(dāng)于把這一行和這一列分成了兩行，兩列。例如# 等價于 還是一行 # 等價于 # #和 一行變成了兩行對就是這么分的。 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ōu)閮尚校ㄒ驗樯厦嬗辛硕泄讨荒軓牡谌虚_始）（因為第一列有了墻，固列數(shù)增加為5）（第3,4列有了墻，固列數(shù)增加到了6和7） 一行變多行，一列變多列后的圖然后我們按照這個編號見圖即可 1 1 2 2 3 3 4 4 5 5 6 6 7對這個圖求二分圖最大匹配即可。