最大流 最小費用流

《最大流 最小費用流》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、4-6最大流一、幾個概念定義（前向弧和背向?。┰谌我庖豁旤c之處，凡離開vi的有向弧稱為vi的前向弧，凡進入vi的有向弧稱為vi的背向弧。vivja稱有向弧a為vi點的前向弧，vj點的背(后)向弧。定義（道路或通路）在任意一網(wǎng)絡(luò)中，凡從始點v0（發(fā)點）開始到終點vn（收點）結(jié)束的一系列前向弧集合稱為道路。記為P。v0vnv2v1v0vnv2v1V0——V1——Vnv0vnv2v1v0vnv2v1V0——V1——Vnv0vnv2v1V0——Vnv0vnv2v1v0vnv2v1v0vnv2v1V0——V1——V2——Vnv0vnv2v1v0vnv2v1V0——V

2、2——Vnv0vnv2v1v0vnv2v1v0vnv2v1V0——V2——V1——Vn定義：（截集或割集）如果N表示某網(wǎng)絡(luò)中所有點的集合，將N分成兩個子集S與S，使得發(fā)點v0在S內(nèi)，收點vn在S內(nèi)，則稱（S，S）為分離發(fā)點與收點的截集。顯然，S?S=N，S?S=?，V0?S，Vn?S注：N分為發(fā)點集S、中轉(zhuǎn)點集R和收點集T。v0vnv2v1a截集a：v0v1，v0v2，v0vnv0vnv2v1b截集b：v1vn，v2vn，v0vnv0vnv2v1c截集c：v1vn，v1v2，v2v1，v0v2，v0vnv0vnv2v1d截集d：v0v1，v1v2，v2v1

3、，v2vn，v0vn定義（截集的容量）從S中各頂點到S中各頂點全部容量之和稱為截集的容量（截量），用（S，S）表示。截集a:Ca=C01+C02+C0n截集b:Cb=C1n+C2n+C0n截集c:Cc=C1n+C12+C02+C0n截集d:Cd=C01+C21+C2n+C0nv0vnv2v1cSS在截集c中邊v2v1是反向的，其容量視為零。v0vnv2v1dSS在截集d中邊v1v2是反向的，其容量視為零。定義（最小截量）一個網(wǎng)絡(luò)中，各種截集中容量最小的稱為最小截量，用minC(S,S)表示?，F(xiàn)在我們把一個網(wǎng)絡(luò)看成是一個自來水管網(wǎng)絡(luò)，煤氣管網(wǎng)絡(luò)，電力線網(wǎng)絡(luò)或

4、公路網(wǎng)絡(luò)，鐵路網(wǎng)絡(luò)，水運交通網(wǎng)絡(luò)等，都可以歸納成一個運輸問題，稱為網(wǎng)絡(luò)流，值得關(guān)心問題是在這樣一個網(wǎng)絡(luò)中最大流為多少？如果在一個網(wǎng)絡(luò)中，有多個發(fā)點或收點，則我們可以將其變?yōu)橹挥幸粋€發(fā)點和收點的網(wǎng)絡(luò)。這只需增加一個新的總發(fā)點和一個新的總收點。從總發(fā)點到各個發(fā)點分別連接一條容量為+∞的弧，從各個收點到總收點分別連接一條容量為+∞的弧。這樣就可將問題變?yōu)閱伟l(fā)點和單收點的網(wǎng)絡(luò)流問題。所以，以后我們只討論一個發(fā)點和一個收點的網(wǎng)絡(luò)流問題。在網(wǎng)絡(luò)中，將通過弧（vi,vj）的運量記作fij，并稱之為?。╲i,vj）上的流量?？尚辛鳎簩τ谌萘烤W(wǎng)絡(luò)D=（V，A，C），每條?。?/p>

5、vi,vj）都給定一個流量fij，當｛fij｝滿足下列條件時，稱為可行流。1°容量限制：對每條?。╲i,vj）∈A，有0≤fij≤cij2°平衡條件：對于中間點vi∈V，流入量等于流出量，即∑fji=∑fij對于發(fā)點vs和收點vt，則有vs發(fā)出總量等于vt收到總量，即∑fsj-∑fjs=∑fjt-∑ftj=v(f)稱v(f)為可行流｛fij｝的流量。jjjjjj定義（最大流）可行流f=（），使得達到最大值截量C與流f的關(guān)系任一有向網(wǎng)絡(luò)流，如果f是從發(fā)點到收點的流量，C(S,S)是任一個截集，則f?C(S,S)。等號什么時候成立？定理（最小截量最大流）任一有

6、向網(wǎng)絡(luò)流，從發(fā)點到收點的最大流量Maxf等于最小截量MinC(S,S)。即：Maxf=MinC(S,S)最大流算法設(shè)P=v0v1v2….vn為網(wǎng)絡(luò)中的一條通路，記E(P)=(所有P中的前向弧和背向弧)令?(P)=min?(i,j)其中?(i,j)=Cij-fij(vi,vj)是前向弧u+fij(vi,vj)是背向弧u-其中Cij是邊容量，fij是流過邊（vi，vj）的可行流，（0?fij?Cij）定義：若?(P)=0稱P為f的飽和的；若?(P)>0稱P為f的不飽和的。定義：一條從發(fā)點到收點的f不飽和通路u稱為f的增長道路（增流路或增廣路），即滿足：1.u+

7、(與u方向相同的弧)上：0?fij0在一個網(wǎng)絡(luò)中，f的增長道路的存在表示f不是最大流。所以。沿著P增加一個值為?(P)的附加流，得到一個新流：f(i,j)+?(P)(vi,vj)是前向弧u+f(i,j）=f(i,j)-?(P)(vi,vj)是背向弧u-f(i,j）其他新流f(i,j)的流值為：f=f+?(P)稱f為基于P的修改流；顯然f>f定理：當且僅當N中不包含f增長道路時，N中的流f是最大流。算法的基本思想：1從任一已知流(如零流)開始，遞推地構(gòu)造一個其值不斷增加的流的序列。2在每一個新流構(gòu)成之后，如果N

8、有f的可增長道路，則f不是最大流。3可得基于P的修改流f，并作為遞