二分圖最大匹配及常用建圖方法

《二分圖最大匹配及常用建圖方法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

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

3、面所說的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,。匈牙利算法就是同過不斷的尋找增廣軌實(shí)現(xiàn)的。很明顯如果二分圖的兩部分點(diǎn)分別為n和m，那么最大匹配的數(shù)目應(yīng)該小于等于MIN（n,m）;因此我們可以枚舉任第一部分（的二部分也可以）里的每一個點(diǎn)，我們從每個點(diǎn)出發(fā)尋找增廣軌，最后吧第一部分的點(diǎn)找完以后，就找到了最大匹配的數(shù)目，當(dāng)然我們也可以通過記錄找出這些邊。下面給出關(guān)于二分圖最大匹配的兩個定

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

5、tPath(number)//通過number這個點(diǎn)尋找增廣軌，找到返回1找不到返回0；P?related[number].next;//與number相連的點(diǎn)；While（p!=NULL）{Ifnotused[p]then//p點(diǎn)沒有被使用過Ifmatch[p]==0orGetAugmentPath(match[p])//p點(diǎn)沒有和另一部分的點(diǎn)配對//或和p配對的那個點(diǎn)可以找到其它點(diǎn)和他配對（找到增廣軌）Return1;p?p.next//與number相連的下幾個點(diǎn)}Return0;}endGetAugmentPath;我們只需要在主程序中對某一部分點(diǎn)集的每個點(diǎn)進(jìn)行增廣軌的尋找；Intm

6、ain{ans?0ForI=1àn//枚舉第一部分的n個點(diǎn)；Forj=1àmuse[j]?false//把第二部分的m個點(diǎn)表示為沒有使用過。ifGetAugmentPath(i)thenans?ans+1//找到增廣軌就給邊數(shù)加一；}程序非常好寫，也非常好懂。123456712345678每次我們從上面的第i個點(diǎn)出發(fā)盡量去找一個能唯一和它匹配的點(diǎn)p，策略有兩種，一是直接在下面的點(diǎn)中找到一個點(diǎn)p，他沒有和上面的點(diǎn)匹配過（即match[p]=0）。二是當(dāng)p和上面的某個點(diǎn)匹配過，即（match[p]）那么我們就從match[p]出發(fā)，去給他找下面另外的點(diǎn)和他匹配，把p點(diǎn)留給點(diǎn)i。這樣我們不就多找到

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