網(wǎng)絡(luò)流資料(超全)

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