百科書名 : 數學與應用數學 : 影視 > 網絡流
目錄
定義
　　圖論中的一種理論與方法，研究網絡上的一類最優化問題 。1955年 ，T.E. 哈裏斯在研究鐵路最大通量時首先提出在一個給定的網絡上尋求兩點間最大運輸量的問題。1956年，L.R. 福特和 D.R. 富爾剋森等人給出瞭解决這類問題的算法，從而建立了網絡流理論。所謂網絡或容量網絡指的是一個連通的賦權有嚮圖 D＝ （V、E、C） ， 其中V 是該圖的頂點集，E是有嚮邊(即弧)集，C是弧上的容量。此外頂點集中包括一個起點和一個終點。網絡上的流就是由起點流嚮終點的可行流，這是定義在網絡上的非負函數，它一方面受到容量的限製，另一方面除去起點和終點以外，在所有中途點要求保持流入量和流出量是平衡的。如果把下圖看作一個公路網，頂點v1…v6表示6座城鎮，每條邊上的權數表示兩城鎮間的公路長度。現在要問 ：若從起點v1將物資運送到終點v6去 ，應選擇那條路綫才能使總運輸距離最短�這樣一類問題稱為最短路問題 。 如果把上圖看作一個輸油管道網 ， v1 表示發送點，v6表示接收點，其他點表示中轉站 ，各邊的權數表示該段管道的最大輸送量。現在要問怎樣安排輸油綫路才能使從v1到v6的總運輸量為最大。這樣的問題稱為最大流問題。
　　最大流理論是由福特和富爾剋森於 1956 年創立的 ，他們指出最大流的流值等於最小割(截集)的容量這個重要的事實，並根據這一原理設計了用標號法求最大流的方法，後來又有人加以改進，使得求解最大流的方法更加豐富和完善 。最大流問題的研究密切了圖論和運籌學，特別是與綫性規劃的聯繫，開闢了圖論應用的新途徑。
　　目前網絡流的理論和應用在不斷發展，出現了具有增益的流、多終端流、多商品流以及網絡流的分解與合成等新課題。網絡流的應用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等衆多領域。
求最大流算法
　　1、augment path，直譯為“增廣路”，其思想大致如下：
　　原有網絡為G，設有一輔助圖G'，其定義為V(G') = V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜索出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊<u,v>添加或擴大反方向的容量，大小就是剛纔減去的容量。一直到沒有路為止。此時輔助圖上的正嚮流就是最大流。
　　我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們衹需要註意到每次網絡中由Source到Sink的流都增加了，若容量都是整數，則這個算法必然會結束。
　　尋找通路的時候可以用DFS，BFS最短路等算法。就這兩者來說,BFS要比DFS快得多，但是編碼量也會相應上一個數量級。
　　增廣路方法可以解决最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次衹能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解决這個問題有一個復雜得多的算法，就是預推進算法。
　　2、push label，直譯為“預推進”算法。
　　3、壓入與重標記(Push-Relabel)算法
　　除了用各種方法在剩餘網絡中不斷找增廣路(augmenting)的Ford-Fulkerson係的算法外，還有一種求最大流的算法被稱為壓入與重標記(Push-Relabel)算法。它的基本操作有：壓入，作用於一條邊，將邊的始點的預流盡可能多的壓嚮終點；重標記，作用於一個點，將它的高度（也就是label）設為所有鄰接點的高度的最小值加一。Push-Relabel係的算法普遍要比Ford-Fulkerson係的算法快，但是缺點是相對難以理解。
　　Relabel-to-Front使用一個鏈表保存溢出頂點，用Discharge操作不斷使溢出頂點不再溢出。Discharge的操作過程是：若找不到可被壓入的臨邊，則重標記，否則對臨邊壓入，直至點不再溢出。算法的主過程是：首先將源點出發的所有邊充滿，然後將除源和匯外的所有頂點保存在一個鏈表裏，從鏈表頭開始進行Discharge，如果完成後頂點的高度有所增加，則將這個頂點置於鏈表的頭部，對下一個頂點開始Discharge。
　　Relabel-to-Front算法的時間復雜度是O(V^3)，還有一個叫Highest Label Preflow Push的算法復雜度據說是O(V^2*E^0.5)。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的算法是使用隊列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。
　　Push-Relabel類的算法有一個名為gap heuristic的優化，就是當存在一個整數0<k<V，沒有任何頂點滿足h[v]=k時，對所有h[v]>k的頂點v做更新，若它小於V+1就置為V+1。
　　cpp程序:
　　#include<cstdio>
　　const long maxn=1000+10;
　　const long maxm=440000+100;
　　const long maxnum=100000000;
　　long n,m,s=0,tot=0,list[maxn],p[maxn],g[maxn],gg[maxn],dis[maxn];
　　bool mark[maxn];
　　struct node
　　{
　　long k,f,c,next,g;
　　}d[maxm<<1];
　　void insert(long u,long v,long c)
　　{
　　d[tot].k=v;
　　d[tot].f=0;
　　d[tot].c=c;
　　d[tot].next=g;
　　g=tot;
　　d[tot].g=tot+1;
　　tot++;
　　d[tot].k=u;
　　d[tot].f=0;
　　d[tot].c=0;
　　d[tot].next=g[v];
　　g[v]=tot;
　　d[tot].g=tot-1;
　　tot++;
　　}
　　void bfs()
　　{
　　long x,u,v,h,t;
　　for (long i=0;i<n;i++)
　　dis=0;
　　h=0;
　　t=1;
　　list=0;
最小費用最大流
　　一．Ford和Fulkerson迭加算法.
　　基本思路：把各條弧上單位流量的費用看成某種長度,用求解最短路問題的方法確定一條自V1至Vn的最短路;在將這條最短路作為可擴充路,用求解最大流問題的方法將其上的流量增至最大可能值;而這條最短路上的流量增加後,其上各條弧的單位流量的費用要重新確定,如此多次迭代,最終得到最小費用最大流.
　　迭加算法：
　　1) 給定目標流量F或∞,給定最小費用的初始可行流=0
　　2) 若V(f)=F,停止,f為最小費用流;否則轉(3).
　　3) 構造 相應的新的費用有嚮圖W(fij),在W(fij)尋找Vs到Vt的最小費用有嚮路P(最短路),沿P增加流f的流量直到F,轉(2);若不存在從Vs到Vt的最小費用的有嚮路P,停止.f就是最小費用最大流.
　　具體解題步驟：
　　設圖中雙綫所示路徑為最短路徑，費用有嚮圖為W（fij）．
　　在圖(a)中給出零流 f,在圖(b)中找到最小費用有嚮路,修改圖(a)中的可行流,δ=min{4,3,5}=3,得圖(c),再做出(c)的調整容量圖,再構造相應的新的最小費用有嚮路得圖(d), 修改圖(c)中的可行流, δ=min{1,1,2,2}=1,得圖(e),以此類推,一直得到圖(h),在圖(h)中以無最小費用有嚮路,停止,經計算:
　　圖(h)中 最小費用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38
　　圖(g)中 最大流=5
　　最大流問題僅註意網絡流的流通能力，沒有考慮流通的費用。實際上費用因素是很重要的。例如在交通運輸問題中，往往要求在完成運輸任務的前提下，尋求一個使總運輸費用最省的運輸方案，這就是最小費用流問題。如果衹考慮單位貨物的運輸費用，那麽這個問題就變成最短路問題。由此可見，最短路問題是最小費用流問題的基礎。現已有一係列求最短路的成功方法。最小費用流(或最小費用最大流)問題 ，可以交替使用求解最大流和最短路兩種方法，通過迭代得到解决。
　　二．圈算法：
　　1) 利用Ford和Fulkson標號算法找出流量為F(<=最大流)的流f.
　　2) 構造f對應的調整容量的流網絡N'(f).
　　3) 搜索N'(f)中的負費用有嚮圖C(Floyd算法),若沒有則停止,否則轉(4).
　　4) 在C上找出最大的循環流,並加到N上去,同時修改N'(F)中C的容量,轉(3).
　　具體解題步驟:
　　利用Ford和Fulkson標號算法,得網絡的最大流F=5,見圖(a),由圖(a)構造相應的調整容量的流網絡(b),圖(b)中不存在負費用有嚮圖,故停止．經計算:
　　圖(b)中 最小費用= 4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38
　　圖(a)中 最大流為F=5
　　type
　　szbest=record
　　v,l:integer;
　　end;
　　szmap=record
　　c,f,w:integer;
　　end;
　　var
　　map:array[0..1000,0..1000] of szmap;
　　best:array[0..1000] of szbest;
　　i,j,ans,n,k,a,b,c,d,s,t:integer;
　　function find:boolean;
　　var i,j:integer;
　　flag:boolean;
　　begin
　　for i:=1 to n do best.v:=maxint;
　　best[s].v:=0;
　　repeat
　　flag:=true;
　　for i:=1 to n do
　　if best.v<maxint then
　　for j:=1 to n do
　　if (map[i,j].f<map[i,j].c)and(best.v+map
　　[i,j].w<best[j].v) then
　　begin
　　best[j].v:=best.v+map[i,j].w;
　　best[j].l:=i; flag:=false;
　　end;
　　until flag;
　　if best[t].v<maxint then exit(true) else exit(false);
　　end;
　　procedure updata;
　　var i,j:integer;
　　begin
　　i:=t;
　　while i<>s do begin
　　j:=best.l;
　　inc(map[j,i].f);
　　map[i,j].f:=-map[j,i].f;
　　i:=j;
　　end;
　　inc(ans,best[t].v);
　　end;
　　begin
　　assign(input,'g4.in');reset(input);
　　readln(n);
　　repeat
　　readln(a,b,c,d);
　　if a+b+c+d>0 then begin
　　map[a,b].c:=c; map[b,a].c:=0;
　　map[a,b].w:=d; map[b,a].w:=-d;
　　end;
　　until a+b+c+d=0;
　　s:=1; t:=n; ans:=0;
　　while find do updata;
　　writeln(ans);
　　for i:=1 to n do
　　for j:=1 to n do
　　if map[i,j].f>0 then writeln(i,' ',j,' ',map[i,j].w,'*',map
　　[i,j].f);
　　end.
網絡流算法
　　一、網絡流的基本概念
　　先來看一個實例。
　　現在想將一些物資從S運抵T，必須經過一些中轉站。連接中轉站的是公路，每條公路都有最大運載量。如下圖：
　　每條弧代表一條公路，弧上的數表示該公路的最大運載量。最多能將多少貨物從S運抵T？
　　這是一個典型的網絡流模型。為瞭解答此題，我們先瞭解網絡流的有關定義和概念。
　　若有嚮圖G=(V,E)滿足下列條件：
　　1、 有且僅有一個頂點S，它的入度為零，即d-(S) = 0，這個頂點S便稱為源點，或稱為發點。
　　2、 有且僅有一個頂點T，它的出度為零，即d+(T) = 0，這個頂點T便稱為匯點，或稱為收點。
　　3、 每一條弧都有非負數，叫做該邊的容量。邊(vi, vj)的容量用cij表示。
　　則稱之為網絡流圖，記為G = (V, E, C)
　　譬如圖5-1就是一個網絡流圖。
　　1．可行流
　　對於網絡流圖G，每一條弧(i,j)都給定一個非負數fij，這一組數滿足下列三條件時稱為這網絡的可行流，用f表示它。
　　1、 每一條弧(i,j)有fij≤cij。
　　2、 除源點S和匯點T以外的所有的點vi，恆有：
　　該等式說明中間點vi的流量守恆，輸入與輸出量相等。
　　3、 對於源點S和匯點T有：
　　這裏V(f)表示該可行流f的流量。
　　例如對圖5-1而言，它的一個可行流如下：
　　流量V(f) = 5。
　　2．可改進路
　　給定一個可行流f=。若fij = cij，稱<vi, vj>為飽和弧；否則稱<vi, vj>為非飽和弧。若fij = 0，稱<vi, vj>為零流弧；否則稱<vi, vj>為非零流弧。
　　定義一條道路P，起點是S、終點是T。把P上所有與P方向一致的弧定義為正嚮弧，正嚮弧的全體記為P+；把P上所有與P方向相悖的弧定義為反嚮弧，反嚮弧的全體記為P-。
　　譬如在圖5-1中，P = (S, V1, V2, V3, V4, T)，那麽
　　P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
　　P- = {<V4, V3>}
　　給定一個可行流f，P是從S到T的一條道路，如果滿足：
　　那麽就稱P是f的一條可改進路。（有些書上又稱：可增廣軌）之所以稱作“可改進”，是因為可改進路上弧的流量通過一定的規則修改，可以令整個流量放大。具體方法下一節會重點介紹，此不贅述。
　　3．割切
　　要解决網絡最大流問題，必須先學習割切的概念和有關知識。
　　G = (V, E, C)是已知的網絡流圖，設U是V的一個子集，W = VU，滿足S U，T W。即U、W把V分成兩個不相交的集合，且源點和匯點分屬不同的集合。
　　對於弧尾在U，弧頭在W的弧所構成的集合稱之為割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，記為C（U，W），即：
　　例如圖5-1中，令U = {S, V1}，則W = {V2, V3, V4, T}，那麽
　　C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4>=8+4+4+1=17
　　定理：對於已知的網絡流圖，設任意一可行流為f，任意一割切為(U, W)，必有：V(f) ≤ C(U, W)。
　　通俗簡明的講：“最大流小於等於最小割”。這是“流理論”裏最基礎最重要的定理。整個“流”的理論係統都是在這個定理上建立起來的，必須特別重視。
　　下面我們給出證明。
　　網絡流、可改進路、割切都是基礎的概念，應該紮實掌握。它們三者之間乍一看似乎風馬牛不相幹，其實內在聯繫是十分緊密的。
　　二、求最大流
　　何謂最大流？首先它必須是一個可行流；其次，它的流量必須達到最大。這樣的流就稱為最大流。譬如對圖5-1而言，它的最大流如下：
　　下面探討如何求得最大流。
　　在定義“可改進路”概念時，提到可以通過一定規則修改“可改進路”上弧的流量，可以使得總流量放大。下面我們就具體看一看是什麽“規則”。
　　對可改進路P上的弧<vi, vj>，分為兩種情況討論：
　　第一種情況：<vi, vj>∈P+，可以令fij增加一個常數delta。必須滿足fij + delta ≤ cij，即delta ≤ cij – fij。
　　第二種情況：<vi, vj>∈P-，可以令fij減少一個常數delta。必須滿足fij - delta ≥ 0，即delta ≤ fij
　　根據以上分析可以得出delta的計算公式：
　　因為P+的每條弧都是非飽和弧，P-的每條弧都是非零流弧，所以delta > 0。
　　容易證明，按照如此規則修正流量，既可以使所有中間點都滿足“流量守恆”（即輸入量等於輸出量），又可以使得總的流量有所增加（因為delta > 0）。
　　因此我們對於任意的可行流f，衹要在f中能找到可改進路，那麽必然可以將f改造成為流量更大的一個可行流。我們要求的是最大流，現在的問題是：倘若在f中找不到可改進路，是不是f就一定是最大流呢？
　　答案是肯定的。下面我們給出證明。
　　定理1 可行流f是最大流的充分必要條件是：f中不存在可改進路。
　　證明：
　　首先證明必要性：已知最大流f，求證f中不存在可改進路。
　　若最大流f中存在可改進路P，那麽可以根據一定規則（詳見上文）修改P中弧的流量。可以將f的流量放大，這與f是最大流矛盾。故必要性得證。
　　再證明充分性：已知流f，並且f中不存在可改進路，求證f是最大流。
　　我們定義頂點集合U, W如下：
　　（a） S∈U，
　　（b） 若x∈U，且fxy<cxy，則y∈U;
　　若x∈U，且fyx>0，則y∈U。
　　（這實際上就是可改進路的構造規則）
　　（c） W = V U。
　　由於f中不存在可改進路，所以T∈W；又S∈U，所以U、W是一個割切（U, W）。
　　按照U的定義，若x∈U，y∈W，則fxy = cxy。若x∈W，y∈U，則fxy = 0。
　　所以，
　　又因 v(f)≤C(U,W)
　　所以f是最大流。得證。
　　根據充分性證明中的有關結論，我們可以得到另外一條重要定理：
　　最大流最小割定理：最大流等於最小割，即max V(f) = min C(U, W)。
　　至此，我們可以輕鬆設計出求最大流的算法：
　　step 1. 令所有弧的流量為0，從而構造一個流量為0的可行流f（稱作零流）。
　　step 2. 若f中找不到可改進路則轉step 5；否則找到任意一條可改進路P。
　　step 3. 根據P求delta。
　　step 4. 以delta為改進量，更新可行流f。轉step 2。
　　step 5. 算法結束。此時的f即為最大流。
　　三、最小費用最大流
　　1．問題的模型
　　流最重要的應用是盡可能多的分流物資，這也就是我們已經研究過的最大流問題。然而實際生活中，最大配置方案肯定不止一種，一旦有了選擇的餘地，費用的因素就自然參與到决策中來。
　　圖5-8是一個最簡單的例子：弧上標的兩個數字第一個是容量，第二個是費用。這裏的費用是單位流量的花費，譬如fs1=4，所需花費為3*4=12。
　　容易看出，此圖的最大流（流量是8）為：fs1 = f1t = 5, fs2 = f2t = 3。所以它的費用是：3*5+4*5+7*3+2*3 = 62。
　　一般的，設有帶費用的網絡流圖G = (V, E, C, W)，每條弧<Vi, Vj>對應兩個非負整數Cij、Wij，表示該弧的容量和費用。若流f滿足：
　　(a) 流量V(f)最大。
　　(b) 滿足a的前提下，流的費用Cost(f) = 最小。
　　就稱f是網絡流圖G的最小費用最大流。
　　2．算法設計
　　我們模仿求最大流的算法，找可改進路來求最小費用最大流。
　　設P是流f的可改進路，定義 為P的費用（為什麽如此定義？）。如果P是關於f的可改進路中費用最小的，就稱P是f的最小費用可改進路。
　　求最小費用最大流的基本思想是貪心法。即：對於流f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。這樣的得到的最大流必然是費用最小的。
　　算法可描述為：
　　step 1. 令f為零流。
　　step 2. 若無可改進路，轉step 5；否則找到最小費用可改進路，設為P。
　　step 3. 根據P求delta（改進量）。
　　step 4. 放大f。轉step 2。
　　step 5. 算法結束。此時的f即最小費用最大流。
　　至於算法的正確性，可以從理論上證明。讀者可自己思考或查閱有關運籌學資料。
　　2．最小費用可改進路的求解
　　求“最小費用可改進路”是求最小費用最大流算法的關鍵之所在，下面我們探討求解的方法。
　　設帶費用的網絡流圖G = (V, E, C, W)，它的一個可行流是f。我們構造帶權有嚮圖B = (V’, E’)，其中：
　　1、 V’ = V。
　　2、 若<Vi, Vj>∈E，fij<Cij，那麽<Vi, Vj>∈E’，權為Wij。
　　若<Vi, Vj>∈E，fij>0，那麽<Vj, Vi>∈E’，權為-Wij。
　　顯然，B中從S到T的每一條道路都對應關於f的一條可改進路；反之，關於f的每條可改進路也能對應B中從S到T的一條路徑。即兩者存在一一映射的邏輯關係。
　　故若B中不存在從S到T的路徑，則f必然沒有可改進路；不然，B中從S到T的最短路徑即為f的最小費用可改進路。
　　現在的問題變成：給定帶權有嚮圖B = (V’, E’)，求從S到T的一條最短路徑。
　　考慮到圖中存在權值為負數的弧，不能采用Dijkstra算法；Floyd算法的效率又不盡如人意——所以，這裏采用一種折衷的算法：迭代法。
　　設Short[k]表示從S到k頂點的最短路徑長度；從S到頂點k的最短路徑中，頂點k的前趨記為Last[k]。那麽迭代算法描述如下：（為了便於描述，令n = |V’|，S的編號為0，T的編號為n+1）
　　step 1. 令Short[k]  +∞（1≤k≤n+1），Short  0。
　　step 2. 遍歷每一條弧<Vk, Vj>。若Short[k] + <k, j> < Short[j]，則令Short[j]  Short[k] + <k, j>，同時Last[j]  k。倘不存在任何一條弧滿足此條件則轉step 4。
　　step 3. 轉step 2.
　　step 4. 算法結束。若Short[n + 1]= +∞，則不存在從S到T的路徑；否則可以根據Last記錄的有關信息得到最短路徑。
　　一次迭代算法的時間復雜度為O(kn2)，其中k是一個不大於n的變量。在費用流的求解過程中，k大部分情況下都遠小於n。
　　3．思維發散與探索
　　1）可改進路費用：“遞增！遞增？”
　　設f從零流到最大流共被改進了k次，每i次選擇的可改進路的費用為pi，那麽會不會有p1≤p2≤p3≤……≤pk呢？
　　2）迭代法：“小心死循環！嘿嘿……”
　　迭代法會出現死循環嗎？也就是說，構造的帶權有嚮圖B中會存在負回路嗎？
　　3）費用：“你在乎我是負數嗎？”
　　網絡流圖中的費用可以小於零嗎？
　　4）容量：“我管的可不僅是弧。”
　　網絡流圖中的“容量”都是對弧而言的，但若是給每個頂點也加上一個容量限製：即通過此頂點的流量的上限；任務仍然是求從S到T的最小費用最大流。你能解决嗎？
　　四、有上下界的最大流
　　上面討論的網絡流都衹對每條弧都限定了上界（其實其下界可以看成0），現在給每條弧<Vi, Vj>加上一個下界限製Aij（即必須滿足Aij≤fij）。
　　例如圖5-9：
　　弧上數字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖5-10(a)所示，流量是6；但若是加入了下界的限製，它的最大流量就衹有5了，具體方案見圖5-10(b)。
　　那麽有上下界的網絡最大流怎麽求呢？
　　一種自然的想法是去掉下界，將其轉化為衹含上界的網絡流圖。這種美好的願望是可以實現的。具體方法如下：
　　設原網絡流圖為G = (V, E, C, A)，構造不含下界的網絡流圖G’ = (V’, E’, C’)：
　　1、 V’ = V∪{S’, T’}
　　2、 對每個頂點x，令 ，若h-(x)≠0，就添加一條弧<S’, x>，其上界為h-(x)。
　　3、 對每個頂點x，令 ，若h+(x)≠0，就添加一條弧<x, T’>，其上界為h+(x)。
　　4、 對於任何<Vi, Vj>∈E，都有<Vi, Vj>∈E’，其上界C’ij = Cij – Aij。
　　5、 新增<T, S>∈E’，其上界CTS = +∞。
　　在G’中以S’為源點、T’為匯點求得最大流f’。若f’中從S’發出的任意一條弧是非飽和弧，則原網絡流圖沒有可行流。否則可得原圖的一個可行流f = f’ + A，即所有的fij = f’ij + Aij。（其正確性很容易證明，留給讀者完成）
　　然後再求可改進路（反嚮弧<Vi, Vj>必須滿足fij≥Aij，而非fij≥0），不斷放大f，直到求出最大流。
　　我們看到，上幾節所討論的一種可行網絡流實際上是{Aij = 0}的一種特殊網絡流，這裏提出的模型更一般化了。解决一般化的復雜問題，我們采取的思路是將其轉化為特殊的簡單問題，加以研究、推廣，進而解决。這是一種重要的基本思想：化歸——簡單有效。基於這種思想，請讀者自行思考解决：
　　1、 有上下界的最小流。
　　2、 有上下界的最小費用最大流。
　　五、多源點、多匯點的最大流
　　已知網絡流圖有n個源點S1、S2、……、Sn，m個匯點T1、T2、……、Tm，，求該圖的最大流。這樣的問題稱為多源點、多匯點最大流。
　　它的解决很簡單：
　　1、 增設一個“超級源”S’，對每個源點Si，新增弧<S’, Si>，容量為無窮大。
　　2、 增設一個“超級匯”T’，對每個匯點Ti，新增弧<Ti, T’>，容量為無窮大。
　　3、 以S’為源點、T’為匯點求最大流f。
　　4、 將f中的S’和T’去掉，即為原圖的最大流。
　　算法正確性顯然。
　　六、頂點有容量限製的最大流
　　上一節已經提出了這個問題，即對於進出每個頂點的流量也規定一個上限，這樣的最大流如何求？
　　既然我們已經解决了“邊限製”問題，現在何不把“點限製”問題轉化為“邊限製”呢？具體辦法如下：
　　1、 對除源點和匯點之外的每個頂點i拆分成兩個頂點i’和i’’。新增一條弧<i’, i’’>，其容量為點i的流量限製。
　　2、 對於原圖中的弧<i, j>，我們將其變換成<i’’, j’>。
　　3、 對變換後的圖求最大流即可。
　　這裏我們又一次運用到了化歸的思想：將未知的“點限製”問題轉化為已知的“邊限製”問題。
　　七、網絡流與二部圖的匹配
　　{二部圖和匹配的定義可參見本書專門介紹二部圖匹配的章節}
　　設二部圖為G = (X, Y, E)。
　　增設點S’，對於所有i∈X，新增弧<S’, Xi>，容量為1；增設點T’，對於所有i∈Y，新增一條弧<Yi, T’>，容量也為1。原圖中所有的弧予以保留，容量均為+∞。對新構造出來的網絡流圖以S’為源點、T’為匯點求最大流：流量即為最大匹配數；若弧<Xi, Yj>（i∈X，j∈Y）的流量非零，它就是一條匹配邊。
　　二部圖最大匹配問題解决。
　　那麽二部圖的最佳匹配問題又如何？
　　仍然按照上述方法構圖。同時令原圖中弧的費用保持不變；新增弧的費用置為0。然後以S’為源點、T’為匯點求最小費用最大流即可。最大流的費用即為原二部圖最佳匹配的費用。
　　八、網絡流的應用（略）
百科大全
　　wangluoliu
　　網絡流
　　network flows
　　圖論中一種理論和方法，研究網絡上的一類最優化問題。T.E.哈裏斯於1955年研究鐵路網的最大通過能力時首先提出，在一個給定的網絡上尋求某兩點間的最大運輸量問題。1956年，L.R.福特和D.R.富爾剋森給出了算法，從而建立了網絡流理論。
　　在網絡流問題中，網絡是由一個有嚮圖□ ＝(□，□)和一個定義在弧集□上的已知非負函數□所組成，其中點集□中有兩個指定的點□□□和□□,分別稱為發點和收點,而□中其他的點都稱為中間點；□稱為網絡的容量函數。用□□表示函數□在弧□＝(□□，□□)上的函數值,並稱之為弧(□□,□□)的容量。
　　設□是定義在集合□上的非負函數。用□□□表示□在弧□=(□□,□□)上的函數值,並稱為在弧□上從□□到□□的流量。若函數□滿足以下兩個條件,則稱函數□為網絡上的流,簡稱網絡流：①在每一條弧上，流量□□□不超過容量□□,即0≤□□≤□□；②在任何一個中間點□□上，從□□流出的總流量等於流入□□的總流量，即□，式中□是對所有以□□為起點的弧求和,□是對所有以□□為終點的弧求和。條件②稱為流的平衡條件。
　　對任意給定的流□,易見，發點的淨出量等於收點的淨收量，即 □。淨出量是指從□□流出的總流量減去流入□□的總流量的差；淨收量是指從□□流入的總流量減去從□□流出的總流量的差。以□(□)表示□□的淨出量或□□的淨收量，並稱為□□(在網絡上)的流量。如圖1網絡流中的a表示一個網絡，箭頭表示弧的方向,弧上的數表示容量。b、c表示網絡a上的兩個流，弧上的數字表示該弧的流量。b的流量為4，c的流量為5。
　　由網絡中的點組成的序列 □若對每一對相繼點□□、□□或者(□□,□□)或者(□□,□□)是網絡中的弧,則稱□是一條連結□□到□□的鏈。設□是一條連接□□到□□的鏈,從□□出發，沿□走到□□時，則鏈□中與走嚮有相同方向的弧稱為前嚮弧；有相反方向的稱為後嚮弧。如果對於給定的流□,它在□ 的每條前嚮弧上的流量都小於容量，在每條後嚮弧上的流量都大於零，則稱鏈 □是關於流□的一個增廣鏈。例如，在圖1 網絡流b中,□＝{□□,□□,□□,□□,□□}是一個增廣鏈。(□□,□□)、(□□,□□)是前嚮弧，其上的流量都小於容量；(□□,□□),(□□,□□)是後嚮弧，其上的流量都大於零。如果在此增廣鏈的前嚮弧上，流量都增加1,後嚮弧上流量都減少1，就可從b變到c，從而使流量從4增加到5。
　　在網絡上尋求一個使流量 □(□)達到最大的流□，稱之為網絡最大流問題。它是網絡流理論中的一個主要研究課題,已獲得一些重要結果：①流□是最大流的充分必要條件是,不存在關於□的增廣鏈。從而將尋求最大流問題化為判斷有無增廣鏈問題。易見，圖1網絡流中的b不是最大流。福特和富爾剋森提出了一種標號法，即對網絡上的點給以標號，從□□出發沿網絡上的弧嚮□□探尋增廣鏈的方法。②若各弧上的容量都是正整數，則必存在各弧上的流量都是整數的最大流。③設□是含有□□而不含□□的點集,(X,□)表示起點在□中而終點不在□中的弧的集合，並稱為分離□□和□□的截集，簡稱截集。網絡中去掉一個截集後,就沒有從□□到□□的定嚮鏈。(X,□)中所有弧的容量之和,稱為這個截集的截量,記作□(X,□)。使截量最小的截集稱為最小截集。網絡流理論中有一個基本的對偶定理:最大流的流量等於最小截集的截量。圖1網絡流的c是一個流量達到最大的流（流量為5），截集{(□□,□□),(□□,□□)}是一個最小截集（截量為5）,這裏□＝{□□,□□}。
　　最小費用流問題是常見的一類重要的
英文解釋
  1. :  Network Flow
相關詞
經濟學算法管理學
包含詞
網絡流量網絡流氓
網絡流行網絡流言
網絡流量器網絡流媒體
網絡流行字網絡流行語
網絡流行詞網絡流理論
網絡流通量增益網絡流
網絡流量分析網絡流量控製
網絡流行用語網絡流行詞彙
網絡流量管理網絡流行語言
網絡流行新詞網絡流量監控
網絡流量管理器網絡流量監控器
網絡流量控製器網絡流量監視器
網絡流量分析工具網絡流量監測與控製
實用網絡流量分析技術網絡流量監控v3.0
網絡流量監視器v1.11.網絡流行語
通信網絡流量控製與激勵價控策略研究nettank--網絡流量分析工具v1.0