建模matlab圖論算法及其MATLAB程序代碼

求二部圖G的最大匹配的算法(匈牙利算法),其基本思想是：從G的任意匹配M開始,對X中所有M的非飽和點,尋找M增廣路.若不存在M增廣路,則M為最大匹配;若存在M 增廣路P,則將P中M與非M的邊互換得到比M多一邊的匹配M1,再對M1重復(fù)上G=(XYE)為二部圖,Xx1x2,xnY={y1y2,yn}.G的一初M(e∈E,M={e}是一個匹配).①令S,T=,MX\S的所有點,M是二部圖G的最大匹配.否則,任取Mu∈XS,SS∪{u},③記N(Sv|u∈Suv∈E}.N(ST,轉(zhuǎn)向②.y∈N(ST.y的飽和點,轉(zhuǎn)向④,④設(shè)xy∈M,SS∪{xT=T∪{y},⑤u yM增廣路,P,并令M=M⊕P,轉(zhuǎn)向①.M⊕P=M∪PM∩P,是對稱差.M增廣路P比較麻煩,XM的所有非飽和點(M中某條邊的端點)都給以標(biāo)號0和標(biāo)記*,X中所有有標(biāo)號的點都已去掉了標(biāo)記*,MG的最大匹配.X中一個既有標(biāo)號又有標(biāo)記*xi,xi的標(biāo)記*,轉(zhuǎn)向③.Gxi鄰接的點yj(xiyj∈E),yj都已有標(biāo)號,②,④對與xi鄰接且尚未給標(biāo)號的yj都給定標(biāo)號i.若所有的yj都是M的飽和點,則轉(zhuǎn)向⑤,否則逆向返回.即由其中M的任一個非飽和點yji找到xi,再由xi的標(biāo)號k找到y(tǒng)k,…,最后由yt的標(biāo)號s0的xs時結(jié)束,獲得M增廣路xsyt…xiyj,記P={xsyt,…,xiyj},MM⊕P,轉(zhuǎn)向①.⑤將yjMxk(xkyj∈M),給以標(biāo)號j和標(biāo)記*,例 求圖6-9中所示的二部圖G的最大匹配6-匈牙利算法的程序代碼如下11001101101100011000001

for(i=1:m)x(i)=0;end%X中點的標(biāo)號和標(biāo)記*for(i=1:n)y(i)=0;end%Y中點的標(biāo)號和標(biāo)記*for(i=1:m)pd=1;%XM的所有非飽和點 %XM0和標(biāo)記*,n+1表0標(biāo)號,標(biāo)號為負(fù)數(shù)時表示標(biāo)記* %X中存在一個既有標(biāo)號又有標(biāo)記*的點,X中一個既有標(biāo)號又有標(biāo)記* %X中所有有標(biāo)號的點都已去掉了標(biāo)記*,x(xi)=x(xi)*(-1);%xi的標(biāo)記* %xiyj

for(i=1:m)if(M(i,yy(j)))x(i)=- %將yjMxkxkyjM),j和標(biāo)記 while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j)));%Myj,if(j==n+1)break;end%X0的點時結(jié)束,M-P %MPM

elseM(P(i,1),P(i,2))=1;end;endPM中出現(xiàn)的邊加入if(pd)break;end;end%X中所有有標(biāo)號的點都已去掉了標(biāo)記*, %M,GXYEF)為完備的二部賦權(quán)圖L是其一個初始可行點標(biāo)記,L(x)max{F(xy)|y xL(y) yMGL的一個匹配①若X的每個點都是M的飽和點,M是最佳匹配.Mu∈X,uT=,②記NL(Sv|u∈Suv∈EL}.若NLST,則GL沒有完美匹配,轉(zhuǎn)向③.否則轉(zhuǎn)③調(diào)整可行點標(biāo)記,aL=min{L(x)+L(y F(xy)|x∈S,y∈Y\TL(v)a,LvLH(v)= a vL L=H,GL=GH,GLM,轉(zhuǎn)向①.④取y∈NLST,y是M的飽和點,轉(zhuǎn)向⑤.否則,⑤設(shè)xy∈M,SS∪{xT=T∪{y},55122464233502⑥在GL中的u y路是M增廣路,記為P,并令M55122464233502 else %Gl %M, %S={xi},T=for(i=1:jss)for(j=1:n)if(Gl(S(i),j))jsn=jsn+1;NlS(jsn)=j;%NL(S)={v|u∈S,uv∈EL} %NL(S)=T?if(jsn==jst&pd)al=InfNL(S)=T,alInf為∞for(i=1:jss)L(S(i),1)=L(S(i),1)-al;end%調(diào)整可行點標(biāo)記for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end% %GLelseGl(i,j)=0;end %Glelse%NL(S)≠T if(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj);%S=S∪{x},T=T∪{y}else%GlM-增廣路,M %MMaxZjpp%M的權(quán),f開始,Ford--Fulkerson⑴標(biāo)號過程vs以標(biāo)號∞s②選擇一個已標(biāo)號的點x,對于x的所有未給標(biāo)號的鄰接點y,按下列規(guī)則處理：當(dāng)yx∈E,且fyx＞0時,令y=min{fyx,x},并給y以標(biāo)號(x ,y).當(dāng)xy∈E,且fxy＜Cxy時,令y=min{C fxy,x},并給y以標(biāo)號(x+,y③重復(fù)②直到收點vt被標(biāo)號或不再有點可標(biāo)號時為止.vt得到標(biāo)號,說明存在一條可增廣鏈,轉(zhuǎn)⑵調(diào)整過程;vt未得到標(biāo)號,標(biāo)號過程已無法進(jìn)行時,說明f已經(jīng)是最大流⑵調(diào)整過程④決定調(diào)整量=vt,uvt⑤若u點標(biāo)號為(v+,u),則以fvu+代替fvu;若u點標(biāo)號為(v,u),則以f fvvs,則去掉所有標(biāo)號轉(zhuǎn)⑴重新標(biāo)號;uv, 算法終止后,令已有標(biāo)號的點集為S,則割集(S,S)為最小割,從而Wf=C(S, 例 求圖6-19所示網(wǎng)絡(luò)的最大流6-利用Ford--Fulkerson標(biāo)號法求最大流算法的程序代碼如下54300000000530000000320000000200000000400000003000000050000000 %No,dNo(1)=n+1;d(1)=Inf;%vs %對于未給標(biāo)號的點vj,vivj %vj,vjviNo(j)=-if(No(n)|pd)break;end;endvt得到標(biāo)號或者無法標(biāo)號,終止標(biāo)號過程if(pd)break;end%vt未得到標(biāo)號,f已是最大流, %進(jìn)入調(diào)整過程dvt elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end%后向弧調(diào)整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0;end;break;end %當(dāng)t的標(biāo)號為vs時,終止調(diào)整過程 %繼續(xù)調(diào)整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end%計算最大流量 %顯示標(biāo)號,由此可得最小割,GV,EC),取初始可行流f為零流,①構(gòu)造有向賦權(quán)圖GfVEfF),vivj∈EEfF的定義如下：當(dāng)fij=0時,vivj∈Ef,F(vivj)=bij;當(dāng)fij=Cij時vjvi∈EfFvjvi)=bij0＜fij＜Cij時,vivj∈Ef,Fvivj)=bij,vjvi∈Ef,Fvjvi)=bijGfVEfF)中發(fā)點vsvt,③;f是所求的最小費用最大流,停止③增流.同求最大流的方法一樣, f vv i

min{|vv∈},fff v ii

v i vv i Wf大于或等于預(yù)定的流量值,則適當(dāng)減少值,Wf等于預(yù)定的流量值,那么f是所求的最小費用流,停止;否則轉(zhuǎn)向①.GVEF)Ford算法vivj∈Ewij=F(vivj),wii=0,wij=+∞(i≠j).v1vi的最短路長記為iv1vivi的前一個點記為iFord①賦初值(1)=0,(i)=+∞,(i)= i=2,3,…,n②更新i),(i).i2,3,nj12,,n,如果i)＜jwji,(i)=(j),(i)= 終止判斷：若所有的i)都無變化,停止;在算法的每一步中,(i)都是從v1vi的最短路長度的上界.若不存在負(fù)長回路,則從v1vi的最短路長度是(i)的下界,n1次迭代后(i)將保持不變.n次迭后(i)仍在變化時,說明存在負(fù)長回路.例 在圖6-22所示網(wǎng)絡(luò)上,求s到t的最小費用最大流,括號內(nèi)

,b6-求最小費用最大流算法的程序代碼如下

008000041000006102030000020000 %wf表示最大流量,wf0表示預(yù)定的流量值 %用Ford算法求最短路,賦初值 %求有向賦權(quán)圖中vs到vt的最短路if(pd)break;end;end%Ford算法結(jié)束 %vsvt的最短路,算法終止.向賦權(quán)圖中不會含負(fù)權(quán)回路,所以不會出現(xiàn)k=n %進(jìn)入調(diào)整過程,dvt表示調(diào)整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t);%前向弧調(diào)整量elseif(a(s(t),t)<0)dvtt=f(t,s(t));end%后向弧調(diào)整量if(s(t)==1)break;end%tvs時,