圖論中的一種理論與方法，研究網(wǎng)絡上的一類最優(yōu)化問題。1955年，T.E.哈里斯在研究鐵路最大通量時首先提出在一個給定的網(wǎng)絡上尋求兩點間最大運輸量的問題。1956年，L.R.福特和D.R.富爾克森等人給出了解決這類問題的算法，從而建立了網(wǎng)絡流理論。所謂網(wǎng)絡或容量網(wǎng)絡指的是一個連通的賦權有向圖D= (V、E、C)，其中V是該圖的頂點集，E是有向邊(即弧)集，C是弧上的容量。此外頂點集中包括一個起點和一個終點。網(wǎng)絡上的流就是由起點流向終點的可行流，這是定義在網(wǎng)絡上的非負函數(shù),它一方面受到容量的限制，另一方面除去起點和終點以外，在所有中途點要求保持流入量和流出量是平衡的。如果把下圖看作一個公路網(wǎng)，頂點vl...v6表示6座城鎮(zhèn)，每條邊上的權數(shù)表示兩城鎮(zhèn)間的公路長度?，F(xiàn)在要問：若從起點v1將物資運送到終點v6去，應選擇那條路線才能使總運輸距離最短□這樣一類問題稱為最短路問題。如果把上圖看作一個輸油管道網(wǎng)，v1表示發(fā)送點，v6表示接收點，其他點表示中轉站，各邊的權數(shù)表示該段管道的最大輸送量?，F(xiàn)在要問怎樣安排輸油線路才能使從v1到v6的總運輸量為最大。這樣的問題稱為最大流問題。最大流理論是由福特和富爾克森于1956年創(chuàng)立的，他們指出最大流的流值等于最小割(截集)的容量這個重要的事實，并根據(jù)這一原理設計了用標號法求最大流的方法，后來又有人加以改進，使得求解最大流的方法更加豐富和完善。最大流問題的研究密切了圖論和運籌學，特別是與線性規(guī)劃的聯(lián)系，開辟了圖論應用的新途徑。目前網(wǎng)絡流的理論和應用在不斷發(fā)展，出現(xiàn)了具有增益的流、多終端流、多商品流以及網(wǎng)絡流的分解與合成等新課題。網(wǎng)絡流的應用已遍及通訊、運輸、電力、工程規(guī)劃、任務分派、設備更新以及計算機輔助設計等眾多領域。網(wǎng)絡流算法一、網(wǎng)絡流的基本概念先來看一個實例。現(xiàn)在想將一些物資從S運抵T，必須經(jīng)過一些中轉站。連接中轉站的是公路，每條公路都有最大運載量。如下圖：每條弧代表一條公路，弧上的數(shù)表示該公路的最大運載量。最多能將多少貨物從S運抵T?這是一個典型的網(wǎng)絡流模型。為了解答此題，我們先了解網(wǎng)絡流的有關定義和概念。若有向圖G=(V,E)滿足下列條件：1、有且僅有一個頂點S,它的入度為零，即d-(S)=0,這個頂點S便稱為源點，或稱為發(fā)點。2、有且僅有一個頂點T,它的出度為零，即d+(T)=0，這個頂點T便稱為匯點，或稱為收點。3、 每一條弧都有非負數(shù)，叫做該邊的容量。邊(vi,vj)的容量用cij表示。則稱之為網(wǎng)絡流圖，記為G=(V,E,C)譬如圖5-1就是一個網(wǎng)絡流圖。可行流對于網(wǎng)絡流圖G,每一條弧(i,j)都給定一個非負數(shù)fij,這一組數(shù)滿足下列三條件時稱為這網(wǎng)絡的可行流，用f表示它。1、 每一條弧(i,j)有fijWcij。2、 除源點S和匯點T以外的所有的點vi,恒有：該等式說明中間點vi的流量守恒，輸入與輸出量相等。3、 對于源點S和匯點T有：這里V(f)表示該可行流f的流量。例如對圖5-1而言，它的一個可行流如下：流量V(f)=5。可改進路給定一個可行流彳=。若fij=cij,稱vvi,vj>為飽和弧；否則稱vvi,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-={vV4,V3>}給定一個可行流f，P是從S到T的一條道路，如果滿足：那么就稱P是f的一條可改進路。(有些書上又稱：可增廣軌)之所以稱作可改進，是因為可改進路上弧的流量通過一定的規(guī)則修改，可以令整個流量放大。具體方法下一節(jié)會重點介紹，此不贅述。3?割切要解決網(wǎng)絡最大流問題，必須先學習割切的概念和有關知識。G=(V,E,C)是已知的網(wǎng)絡流圖，設U是V的一個子集，W=V\U，滿足SU，TW。即U、W把V分成兩個不相交的集合，且源點和匯點分屬不同的集合。對于弧尾在U,弧頭在W的弧所構成的集合稱之為割切，用U,W)表示。把割切U,W)中所有弧的容量之和叫做此割切的容量，記為C(U,W),即:例如圖5-1中，令U={S,VI}，則W={V2,V3,V4,T},那么C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+vVl,V4>=8+4+4+l=17定理：對于已知的網(wǎng)絡流圖，設任意一可行流為f,任意一割切為(U,W),必有：V(f)<C(U,W)。通俗簡明的講：最大流小于等于最小割。這是流理論里最基礎最重要的定理。整個流的理論系統(tǒng)都是在這個定理上建立起來的，必須特別重視。下面我們給出證明。網(wǎng)絡流、可改進路、割切都是基礎的概念，應該扎實掌握。它們三者之間乍一看似乎風馬牛不相干，其實內在聯(lián)系是十分緊密的。二、求最大流何謂最大流？首先它必須是一個可行流；其次，它的流量必須達到最大。這樣的流就稱為最大流。譬如對圖5-1而言，它的最大流如下：下面探討如何求得最大流。在定義可改進路概念時，提到可以通過一定規(guī)則修改可改進路上弧的流量，可以使得總流量放大。下面我們就具體看一看是什么規(guī)則。對可改進路P上的弧<vi,vj>,分為兩種情況討論：第一種情況：vvi,vj>uP+,可以令fij增加一個常數(shù)delta。必須滿足fij+delta<cij,即delta<cij一fij。第二種情況：vvi,vj>uP-,可以令fij減少一個常數(shù)delta。必須滿足fij-delta>0,即delta<fij根據(jù)以上分析可以得出delta的計算公式：因為P+的每條弧都是非飽和弧，P-的每條弧都是非零流弧，所以delta>0。容易證明，按照如此規(guī)則修正流量，既可以使所有中間點都滿足流量守恒(即輸入量等于輸出量)，又可以使得總的流量有所增加(因為delta>0)。因此我們對于任意的可行流f,只要在f中能找到可改進路，那么必然可以將f改造成為流量更大的一個可行流。我們要求的是最大流，現(xiàn)在的問題是：倘若在f中找不到可改進路，是不是f就一定是最大流呢？答案是肯定的。下面我們給出證明。定理1可行流f是最大流的充分必要條件是：f中不存在可改進路。證明：首先證明必要性：已知最大流f,求證f中不存在可改進路。若最大流f中存在可改進路P,那么可以根據(jù)一定規(guī)則(詳見上文)修改P中弧的流量?？梢詫的流量放大，這與f是最大流矛盾。故必要性得證。再證明充分性：已知流f,并且f中不存在可改進路，求證f是最大流。我們定義頂點集合U,W如下：SUU,若xUU,且fxyvcxy，則yUU;若xUU,且fyx>0,則yUU。(這實際上就是可改進路的構造規(guī)則)W=V\U。由于f中不存在可改進路，所以TUW；又SUU,所以U、W是一個割切(U,W)。按照U的定義，若xUU,yUW,貝I」fxy=cxy。若xUW,yUU,貝I」fxy=0。所以，又因v(f)<C(U,W)所以f是最大流。得證。根據(jù)充分性證明中的有關結論，我們可以得到另外一條重要定理：最大流最小割定理：最大流等于最小割，即maxV(f)=minC(U,W)。至此，我們可以輕松設計出求最大流的算法：step1.令所有弧的流量為0,從而構造一個流量為0的可行流f(稱作零流)。step2.若f中找不到可改進路則轉step5；否則找到任意一條可改進路P。step3.根據(jù)P求delta。step4.以delta為改進量，更新可行流f。轉step2。step5.算法結束。此時的f即為最大流。三、最小費用最大流問題的模型流最重要的應用是盡可能多的分流物資，這也就是我們已經(jīng)研究過的最大流問題。然而實際生活中，最大配置方案肯定不止一種，一旦有了選擇的余地，費用的因素就自然參與到?jīng)Q策中來。圖5-8是一個最簡單的例子：弧上標的兩個數(shù)字第一個是容量，第二個是費用。這里的費用是單位流量的花費，譬如fs1=4,所需花費為3*4=12。容易看出，此圖的最大流(流量是8)為：fsl=f1t=5,fs2=f2t=3。所以它的費用是：3*5+4*5+7*3+2*3=62。一般的，設有帶費用的網(wǎng)絡流圖G=(V,E,C,W),每條弧vVi,Vj>對應兩個非負整數(shù)Cij、Wij,表示該弧的容量和費用。若流f滿足：流量V(f)最大。滿足a的前提下，流的費用Cost(f)=最小。就稱f是網(wǎng)絡流圖G的最小費用最大流。算法設計我們模仿求最大流的算法，找可改進路來求最小費用最大流。設P是流f的可改進路，定義為P的費用(為什么如此定義？)如果P是關于f的可改進路中費用最小的，就稱P是f的最小費用可改進路。求最小費用最大流的基本思想是貪心法。即：對于流f,每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。這樣的得到的最大流必然是費用最小的。算法可描述為：step1.令f為零流。step2.若無可改進路，轉step5；否則找到最小費用可改進路，設為P。step3.根據(jù)P求delta(改進量)。step4.放大f。轉step2。step5.算法結束。此時的f即最小費用最大流。至于算法的正確性，可以從理論上證明。讀者可自己思考或查閱有關運籌學資料。最小費用可改進路的求解求最小費用可改進路是求最小費用最大流算法的關鍵之所在，下面我們探討求解的方法。設帶費用的網(wǎng)絡流圖G=(V,E,C,W),它的一個可行流是f。我們構造帶權有向圖B=(V',E')，其中：1、 V'=V。2、 若vVi,Vj>uE,fijvCij，那么<Vi,Vj>uE'，權為Wij。若vVi,Vj>uE,fij>0，那么vVj,Vi>uE'，權為-Wij。顯然，B中從S到T的每一條道路都對應關于f的一條可改進路；反之，關于f的每條可改進路也能對應B中從S到T的一條路徑。即兩者存在一一映射的邏輯關系。故若B中不存在從S到T的路徑，則f必然沒有可改進路；不然，B中從S到T的最短路徑即為f的最小費用可改進路?，F(xiàn)在的問題變成：給定帶權有向圖B=(V',E'),求從S到T的一條最短路徑。考慮到圖中存在權值為負數(shù)的弧，不能采用Dijkstra算法；Floyd算法的效率又不盡如人意——所以，這里采用一種折衷的算法：迭代法。設Short[k]表示從S到k頂點的最短路徑長度；從S到頂點k的最短路徑中，頂點k的前趨記為Last[k]。那么迭代算法描述如下：(為了便于描述，令n=|V'|,S的編號為0,T的編號為n+1)step1.令Short[k]口+w(1<k<n+1),Short[0]口0。step2.遍歷每一條弧vVk,Vj>。若Short[k]+<k,j><Short[j],則令Short[j]口Short[k]+<k,j>,同時Last[j]口k。倘不存在任何一條弧滿足此條件則轉step4。step3.轉step2.step4.算法結束。若Short[n+1]=+<?,則不存在從S到T的路徑；否則可以根據(jù)Last記錄的有關信息得到最短路徑。一次迭代算法的時間復雜度為O(kn2)，其中k是一個不大于n的變量。在費用流的求解過程中，k大部分情況下都遠小于n。3、 思維發(fā)散與探索1?？筛倪M路費用：遞增！遞增？設f從零流到最大流共被改進了k次，每i次選擇的可改進路的費用為pi，那么會不會有pl<p2<p3< <pk呢？迭代法：小心死循環(huán)！嘿嘿……迭代法會出現(xiàn)死循環(huán)嗎？也就是說，構造的帶權有向圖B中會存在負回路嗎？費用：你在乎我是負數(shù)嗎？網(wǎng)絡流圖中的費用可以小于零嗎？容量：我管的可不僅是弧。網(wǎng)絡流圖中的容量都是對弧而言的，但若是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務仍然是求從S到T的最小費用最大流。你能解決嗎？四、 有上下界的最大流上面討論的網(wǎng)絡流都只對每條弧都限定了上界(其實其下界可以看成0),現(xiàn)在給每條弧vVi,Vj＞加上一個下界限制Aij(即必須滿足Aijfj)。例如圖5-9：弧上數(shù)字對第一個是上界，第二個是下界。若是撇開下界不看，此圖的最大流如圖5-10(a)所示,流量是6；但若是加入了下界的限制,它的最大流量就只有5了，具體方案見圖5-10(b)。那么有上下界的網(wǎng)絡最大流怎么求呢？一種自然的想法是去掉下界，將其轉化為只含上界的網(wǎng)絡流圖。這種美好的愿望是可以實現(xiàn)的。具體方法如下：設原網(wǎng)絡流圖為G=(V,E,C,A)，構造不含下界的網(wǎng)絡流圖G'=(V',E',C')：1、 V'=VU{S',T'}2、 對每個頂點x,令，若h-(x)主0，就添加一條弧＜S',x＞，其上界為h-(x)。3、 對每個頂點x,令，若h+(x)主0，就添加一條?。紉,T'＞,其上界為h+(x)。4、 對于任何vVi,Vj＞uE，都有＜Vi,Vj＞uE',其上界C'ij=Cij-Aij。5、 新增vT,S＞UE'，其上界CTS=在G'中以S'為源點、T'為匯點求得最大流F。若F中從S'發(fā)出的任意一條弧是非飽和弧,則原網(wǎng)絡流圖沒有可行流。否則可得原圖的一個可行流f=f+A,即所有的fij=fij+Aij。(其正確性很容易證明，留給讀者完成)然后再求可改進路(反向?。糣i,Vj＞必須滿足fij＞Aij，而非fij＞0),不斷放大f,直到求出最大流。我們看到，上幾節(jié)所討論的一種可行網(wǎng)絡流實際上是{Aij=0}的一種特殊網(wǎng)絡流，這里提出的模型更一般化了。解決一般化的復雜問題，我們采取的思路是將其轉化為特殊的簡單問題，加以研究、推廣，進而解決。這是一種重要的基本思想：化U—簡單有效?；谶@種思想，請讀者自行思考解決：1、 有上下界的最小流。2、 有上下界的最小費用最大流。五、 多源點、多匯點的最大流已知網(wǎng)絡流圖有n個源點S1、S2、......、Sn,m個匯點T1、T2、......、Tm,,求該圖的最大流。這樣的問題稱為多源點、多匯點最大流。它的解決很簡單：1、 增設一個超級源S'，對每個源點Si,新增?。糞',Si＞,容量