二分圖匹配——匈牙利算法和km算法簡介

《二分圖匹配——匈牙利算法和km算法簡介》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、二分圖匹配匈牙利算法和KM算法簡介二分圖的概念二分圖又稱作二部圖，是圖論中的一種特殊模型。設(shè)G=(V,{R})是一個無向圖。如頂點(diǎn)集V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點(diǎn)都分屬兩個不同的子集。則稱圖G為二分圖。112233445最大匹配給定一個二分圖G，在G的一個子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個頂點(diǎn)，則稱M是一個匹配。選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題(maximalmatchingproblem)如果一個匹配中，圖中的每個頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。匈牙利算法求最

2、大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個算法的復(fù)雜度為邊數(shù)的指數(shù)級函數(shù)。因此，需要尋求一種更加高效的算法。增廣路的定義(也稱增廣軌或交錯軌)：若P是圖G中一條連通兩個未匹配頂點(diǎn)的路徑，并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。匈牙利算法由增廣路的定義可以推出下述三個結(jié)論：1－P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。2－P經(jīng)過取反操作可以得到一個更大的匹配M’。3－M為G的最大匹配當(dāng)且僅當(dāng)不存在相對于M的增廣路徑。匈牙利算法用增廣路求最大匹配(稱作匈

3、牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出)算法輪廓：(1)置M為空(2)找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M(3)重復(fù)(2)操作直到找不出增廣路徑為止匈牙利算法程序清單：Functionfind(k:integer):integer;varst,sf,i,j,t:integer;queue,father:array[1..100]ofinteger;beginqueue[1]:=k;st:=1;sf:=1;fillchar(father,sizeof(father),0);repeat匈牙利算法fori:=1tondoi

4、f(father[i]=0)and(a[queue[st],i]=1)thenbeginifmatch2[i]<>0thenbegininc(sf);queue[sf]:=match2[i];father[i]:=queue[st];endelse匈牙利算法beginj:=queue[st];whiletruedobegint:=match1[j];match1[j]:=i;match2[i]:=j;ift=0thenbreak;i:=t;j:=father[t];匈牙利算法end;find:=1;exit;end;end;inc(st);untils

5、t>sf;find:=0;end;匈牙利算法在主程序中調(diào)用下面的程序即可得出最大匹配數(shù)。Bmatch:=0;ForI:=1tondoBmatch:=Bmatch+find(i);Writeln(Bmatch);一個關(guān)于二分圖的性質(zhì)：最大匹配數(shù)＋最大獨(dú)立集＝X＋Y最佳匹配如果邊上帶權(quán)的話，找出權(quán)和最大的匹配叫做求最佳匹配。實(shí)際模型：某公司有職員x1,x2,…,xn,他們?nèi)プ龉ぷ鱵1,y2,…,yn,每個職員做各項工作的效益未必一致，需要制定一個分工方案，使得人盡其才，讓公司獲得的總效益最大。數(shù)學(xué)模型：G是加權(quán)完全二分圖，求總權(quán)值最大的完備匹配。KM算法窮

6、舉的效率－n！，我們需要更加優(yōu)秀的算法。定理：設(shè)M是一個帶權(quán)完全二分圖G的一個完備匹配，給每個頂點(diǎn)一個可行頂標(biāo)(第i個x頂點(diǎn)的可行標(biāo)用lx[i]表示，第j個y頂點(diǎn)的可行標(biāo)用ly[j]表示)，如果對所有的邊(i,j)inG,都有l(wèi)x[i]+ly[j]>=w[i,j]成立(w[i,j]表示邊的權(quán))，且對所有的邊(i,j)inM,都有l(wèi)x[i]+ly[j]=w[i,j]成立，則M是圖G的一個最佳匹配。證明很容易。KM算法對于任意的G和M，可行頂標(biāo)都是存在的：l(x)=maxw(x,y)l(y)=0欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹

7、配；問題是當(dāng)標(biāo)號之后的Gl無完備匹配時怎么辦？1957年（居然比匈牙利算法早？？？），Kuhn和Munkras給出了一個解決該問題的有效算法，用逐次修改可行頂標(biāo)l(v)的辦法使對應(yīng)的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備匹配。KM算法修改方法如下：先將一個未被匹配的頂點(diǎn)u(uin{x})做一次增廣路，記下哪些結(jié)點(diǎn)被訪問那些結(jié)點(diǎn)沒有被訪問。求出d=min{lx[i]+ly[j]-w[i,j]}其中i結(jié)點(diǎn)被訪問，j結(jié)點(diǎn)沒有被訪問。然后調(diào)整lx和ly：對于訪問過的x頂點(diǎn)，將它的可行標(biāo)減去d，對于所有訪問過的y頂點(diǎn)，將它的可行標(biāo)增加d。修改后的頂標(biāo)仍是可行頂

8、標(biāo)，原來的匹配M仍然存在，相等子圖中至少出現(xiàn)了一條不屬于M的邊，所以造成M的逐漸增廣。KM算法