二分圖最大匹配

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

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

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

3、M’。3－M為G的最大匹配當(dāng)且僅當(dāng)不存在相對(duì)于M的增廣路徑。匈牙利算法用增廣路求最大匹配(稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出)算法輪廓：(1)置M為空(2)找出一條增廣路徑P，通過(guò)取反操作獲得更大的匹配M’代替M(3)重復(fù)(2)操作直到找不出增廣路徑為止匈牙利算法程序清單：Functionfind(k:integer):integer;varst,sf,i,j,t:integer;queue,father:array[1..100]ofinteger;beginqueue[1]:=

4、k;st:=1;sf:=1;fillchar(father,sizeof(father),0);repeat匈牙利算法fori:=1tondoif(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[

5、j]:=i;match2[i]:=j;ift=0thenbreak;i:=t;j:=father[t];匈牙利算法end;find:=1;exit;end;end;inc(st);untilst>sf;find:=0;end;匈牙利算法在主程序中調(diào)用下面的程序即可得出最大匹配數(shù)。Bmatch:=0;ForI:=1tondoBmatch:=Bmatch+find(i);Writeln(Bmatch);一個(gè)關(guān)于二分圖的性質(zhì)：最大匹配數(shù)＋最大獨(dú)立集＝X＋Y最佳匹配如果邊上帶權(quán)的話，找出權(quán)和最大的匹配叫做求最佳匹

6、配。實(shí)際模型：某公司有職員x1,x2,…,xn,他們?nèi)プ龉ぷ鱵1,y2,…,yn,每個(gè)職員做各項(xiàng)工作的效益未必一致，需要制定一個(gè)分工方案，使得人盡其才，讓公司獲得的總效益最大。數(shù)學(xué)模型：G是加權(quán)完全二分圖，求總權(quán)值最大的完備匹配。KM算法窮舉的效率－n！，我們需要更加優(yōu)秀的算法。定理：設(shè)M是一個(gè)帶權(quán)完全二分圖G的一個(gè)完備匹配，給每個(gè)頂點(diǎn)一個(gè)可行頂標(biāo)(第i個(gè)x頂點(diǎn)的可行標(biāo)用lx[i]表示，第j個(gè)y頂點(diǎn)的可行標(biāo)用ly[j]表示)，如果對(duì)所有的邊(i,j)inG,都有l(wèi)x[i]+ly[j]>=w[i,j]成立(

7、w[i,j]表示邊的權(quán))，且對(duì)所有的邊(i,j)inM,都有l(wèi)x[i]+ly[j]=w[i,j]成立，則M是圖G的一個(gè)最佳匹配。證明很容易。KM算法對(duì)于任意的G和M，可行頂標(biāo)都是存在的：l(x)=maxw(x,y)l(y)=0欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹配；問(wèn)題是當(dāng)標(biāo)號(hào)之后的Gl無(wú)完備匹配時(shí)怎么辦？1957年（居然比匈牙利算法早？？？），Kuhn和Munkras給出了一個(gè)解決該問(wèn)題的有效算法，用逐次修改可行頂標(biāo)l(v)的辦法使對(duì)應(yīng)的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備

8、匹配。KM算法修改方法如下：先將一個(gè)未被匹配的頂點(diǎn)u(uin{x})做一次增廣路，記下哪些結(jié)點(diǎn)被訪問(wèn)那些結(jié)點(diǎn)沒有被訪問(wèn)。求出d=min{lx[i]+ly[j]-w[i,j]}其中i結(jié)點(diǎn)被訪問(wèn)，j結(jié)點(diǎn)沒有被訪問(wèn)。然后調(diào)整lx和ly：對(duì)于訪問(wèn)過(guò)的x頂點(diǎn)，將它的可行標(biāo)減去d，對(duì)于所有訪問(wèn)過(guò)的y頂點(diǎn)，將它的可行標(biāo)增加d。修改后的頂標(biāo)仍是可行頂標(biāo)，原來(lái)的匹配M仍然存在，相等子圖中至少出現(xiàn)了一條不屬于M的邊，所以造成M的逐漸增廣。KM算法