最大流網(wǎng)絡(luò)基礎(chǔ)及應(yīng)用

一.引例方

下圖為聯(lián)結(jié)產(chǎn)品產(chǎn)地V1和銷地V6的交通網(wǎng)，每一邊(Vi,Vj)代表從Vi到Vj的線，產(chǎn)品經(jīng)這條邊由Vi輸送到Vj，邊旁的數(shù)字表示這條線的最大通行能力(簡稱容量)。產(chǎn)品經(jīng)過交通網(wǎng)從V1V6V1V6的產(chǎn)品數(shù)量最多。4444174823 1 3 該方案表示：2噸產(chǎn)品沿有向路P1(V1,V2,V4,V6)運到銷地；1噸產(chǎn)品沿有向路P2(V1,V2,V5,V6)運到銷地；2P3(V1,V3,V5,V6)5噸從V1運V6。V1V6，對其他頂點(中間點)來說，不能囤積物資，即運到它那兒的物資改進1：我們找到一條有向路P4(V1,V2,V3,V4,V6)可再增加1噸物資量，改進的方案如24241310213 24241410323 去完成，這樣有向路P6(V1,V3,V2,V4,V6)的運量可增加1(想為什么可以這樣做)。34341500423 二.網(wǎng)絡(luò)流圖與最大設(shè)G=(V,E)為一有向圖。當且僅當只有一個入度為0(d(z)=0)的點，在V中指定該頂點為源點(記為Z)，當且僅當有一個頂點出度為0的頂(記為Z’)，對于每一條邊(Vi,Vj)∈E，Cij>=0D=(V,E,C)(圖示參見引例)2對于網(wǎng)絡(luò)流圖D=(V,E,C)的每一條邊(Vi,Vj)給定一個非負數(shù)fij，且滿足下列條件①0<=fij<=Cij(容量限止條件②除源點和匯點外，其余頂點Vi∑fij=∑fki(中間點流量守恒，即平衡條件D=(V,E,C)D的可行流f。3D的可行流①當所有fij=0，稱為零流，零流一定是可行ZZ’ω三.求最大流的理論基D=(V,E,C)S是VS ②Z’S’S的補集，這樣把頂點集VSS’兩個部分，其中Z∈S,Z’∈S’<C(S,S’)：在割切(S,S’)SS’的邊容量和叫做這割切的容量。C(S,S’)=CZa+Cba+CbZ’+CdZ’=4+3+2+4=132Z到匯點Z’ω的最大值小于等于任何一個割切Maxω<=MinC(S,S’)?！苀ij- 當i=Z時 ∑(fij-fji)=i≠Z0i=Z時，由⑵式得 ⑶式中∑(fij-fji)Sfpq都一一對應(yīng)一項-即由⑶式得∑(fij-fji) 再由于0<=fij<Cijfij-ω=∑(fij-fji∑CijMaxω<=MinMaxω=Min在網(wǎng)絡(luò)流圖D=(V,E,C)Z到匯點Z’Z=V0,V1,...,Vn-1,Vn=Z’Di=0,1,...,n-1，恒有(Vi,Vi+1)或(Vi+1,Vi)邊是D的一條邊。則稱V0,V1,...,VnZZ’的道路。V1V1

Vn- 道邊的飽和：前向邊若fij=Cij，后向邊若fij=0,稱邊(Vi,Vj)為關(guān)于該道的飽和邊。若從Z到Z’的道所有的邊均不飽和，即對于P+若fij<Cij，P-有fij>0，則稱這條路為可增

Cij-fij 取δ=Min(δij)，為增量Pδδ，從而使得整個Maxω=Min設(shè)網(wǎng)絡(luò)流圖Df達到極大，我們構(gòu)造一個割切(S,S’) 和f是最大流的假設(shè)。②若x∈S，且fxy<Cxy，則x∈S，且fyx>0，則Z’∈S’(Z’d(Z’)=0)，ω=∑(fxy-fyxMaxω=Min四.求網(wǎng)絡(luò)最大流的算f是網(wǎng)絡(luò)流圖DZZ’fPf一將將F改為更大的F為最大取所有fij=0為第一個流從一個可行流出發(fā)(若網(wǎng)絡(luò)中沒有初始流，則可以設(shè)f是零流)1Vs表示源點，Vt表示匯點。改進量，第二個標號是為確定可改進量δ而設(shè)的。Vs標上(0,+∞)Vs是已標號而未檢查的點，其余都是未標號Vi，對一切未標號點Vj：⑴若存在弧(Vi,Vj)且fij<CijVj標號(Vi,L(Vj))L(Vj)=Min(L(Vi),Cij-⑵若存在弧(Vj,Vi)且fji>0Vj標號(-Vi,L(Vj))VtVsVtP，轉(zhuǎn)入增廣過程。2P上的頂點都已標號。因此多用“倒向追蹤”Vt開始，利用PVtl(Vt)(δ)作為改P上的流量。VkViVsP。fij作改進：

(Vi,Vj)為fij- (Vi,Vj)為②去掉所有的標號，對新的流F’=(fij’)重新進入標號過程Constmaxn=<網(wǎng)絡(luò)頂點數(shù) gtype=array[0..maxn,0..maxn]ofarc； ltype=array[0..maxn]of varlt:ltype; procedureread-graph；varI,j:integer; fori:=1tondoforj:=1ton functionvari:integer;whilei<=n)andnot((lt[i].l<>0)and(lt[i].p=0doinc(i);ifi>nthencheck:=0 else 標號過程，并返回是否找到可增廣道路及改進量afunctionford(vara:integer):boolean; {無增廣道路返回true}varI,j,m,x:integer; {從Vs開始} ifi=0thenexit; {true}forj:=1tondoifthenbeginif(g[I,j].f<g[I,j].c)thenif(g[j,i].f>0)thenlt[j].l:=-I; until {直到匯點Vt標號為止m:=t;a:=maxint; {從Vt倒推，改進量a賦初值} {求a}j:=m;iflt[j].l<0theniflt[j].l>0thenx:=g[m,j].c-g[m,j].f;ifa>xthena:=x;until {Vs為止 procedurefulkerson(a:integer);varm,j:integer; {Vt出發(fā)，逆向沿可增廣道路修正容量}j:=m;iflt[j].l<0theng[j,m].f:=g[j,m].f- {后向邊piflt[j].l>0then untilm=s; procedureanswer;varI,j:integer;fori:=1tonforj:=1ton n(‘(’,I,‘,’,j,‘)’,‘ vard:integer;s:=1; {假設(shè)源點為V1 ifsuccessthen else untilsuccess;⑦ dinicDinic算法的思想是分階段地在層次圖中改進流量。下面先介紹網(wǎng)絡(luò)圖的剩余圖及層次剩余圖：給定一個網(wǎng)絡(luò)流圖D1=(V1,E1,c)及一可行流f，與該網(wǎng)絡(luò)流圖D1=(V1,E1,c)關(guān)fuv，顯然該邊為前向邊。若fuv>0，那么邊(u,v) gvu=fuv，顯然該邊為后向邊D1中的每條邊在剩余圖D2中都化作了一條或兩條邊，D2中的每Vvguv的流量。見下圖。22(71252263DV31,E1661數(shù)字義(邊上1數(shù)字義(D3（V3E3（u,vu相連}。D2vsvt的任意一條簡單路徑（即不存在重復頂點或邊的路徑）1 26

V35334V3 1．dinic在層次圖內(nèi)用一次dfs在層次圖內(nèi)用一次dfs過程改進流NY算法結(jié)次圖，然后用dfs過程在層次圖內(nèi)擴展可增廣路徑，調(diào)整流量。增廣完畢后，進入下一個階level，level(u)+1=level(v)約束即可。2、DinicConstmaxn=<頂點數(shù)上限>

g:array[1..maxm*2]ofgtype; {以邊目表網(wǎng)絡(luò)流圖}first,first1:array[1..maxn]oflongint; {頂點Vi引出的首條邊序號first[i]}p,level,prt:array[1..maxnof 徑上頂點Vi引出的邊序號prt[i]}visited:array[1..maxn]oflongint; 0的反向邊(b,a)邊目表的的鏈表形式：將頂點Vi引出的所有邊在一個鏈表中，首條邊的序號為first[i]，順著next指針，依次頂點Vi引出的所有邊。Procedureadd(a,b,c:longint);Inc(tot);g[tot].x:=a;g[tot].y:=b;g[tot].next:=first[a];first[a]:=tot;{在a頂點引出的邊表首部插入該條邊} inc(tot);g[tot].x:=b;g[tot].y:=a;g[tot].c:=0; {0的邊(b,a)}g[tot].next:=first[b];first[b]:=tot; 構(gòu)建初始剩余圖，設(shè)f=0為零流。 Fori:=1tondo Fori:=1tomdo {i條邊(a,b)c,g中}ProcedureVarI,open,closed,temp,tp:longintopen，隊尾指針closedtp}Fori:=1tondolevel[i]:=maxw; Open:=1;closed:=0;p[open]:=vs;level[vs]:=1; {源點vs進入隊列，層次為1}Whileclosed<opendo {若隊列非空，則取出隊首頂點tp}Inc(closed);Iftp=vtthen Whiletemp<>-1doIfThenif(g[temp].f<g[temp].c)or((g[temp].c=0)and(g[temp].f>0)) make_levelVt的層次，(level[Vt]=maxw)Vs與Vt間無路可通，不存在可增廣路徑，當前流為最大流。只有源點。Dfs過程分兩個操作：dfs遍歷了。Proceduredfs_maxflow; whiletop>0ifp[top]=vtthen forj:=topdownto2do ifg[prt[p[j]]].f<g[prt[p[j]]].cthenmint:=g[prt[p[j]]].c-g[prt[p[j]]].felseifmint>g[prt[p[j]]].fthenmint:=g[prt[p[j]]].f;forj:=topdownto2 ifg[prt[p[j]]].f<g[prt[p[j]]].cthenifg[prt[p[j]]].f=g[prt[p[j]]].cthen {若棧的第jmint}ifg[prt[p[j]]].f=0thentj:=j; {tj前的棧元素} {取出棧頂元素tp和引出的首條邊temp}whiletemp<>-1do {若棧頂元素tp引出的后邊未搜索完}ifnotvisited[g[temp].yandlevel[g[temp].y]=level[tp]+1) if(g[temp].f<g[temp].c)or((g[temp].c=0)and {while循環(huán)} iftemp=-1then vs:=1;{設(shè)置源點和匯點}whiletruedo iflevel[vt]=maxwthen whiletemp<>-1do 五.sX集的每一個頂點xi引出一條容量為∞的有向邊（s,xiY集的每一個頂點yi向匯點t引出一條容量為∞的有向邊（yi,t）二分圖邊集E中的每條有向邊（xi,yi）1表中列出了n個項目。對于每個項目，規(guī)劃中都給出了它所需要的投資或預計的。由于輸入：第一行是項目數(shù)量接下來的第i+1行每行表示第i個項目的信息，每行的第一個數(shù)是ci（- 輸出：最大凈利潤6-122-12-3534ci表示該uvV’。滿足對任意有向邊（u,v）∈Eu∈V’，v∈V’V’中所有頂點權(quán)值之和最大。O（2n，本題也<2>s<3>scit