第十二章網(wǎng)絡(luò)流模型

1、一、基本概念一、基本概念定義定義1：一個有向圖：一個有向圖G =(V,A)，若對，若對G 的每一個弧的每一個弧(vi,vj) A , 均對應(yīng)均對應(yīng)一個非負(fù)數(shù)一個非負(fù)數(shù)c (vi,vj) 0 (或簡記或簡記cij ）,稱為此弧段的容量，則稱此圖稱為此弧段的容量，則稱此圖G 為網(wǎng)絡(luò)。為網(wǎng)絡(luò)。定義定義2：定義在弧集：定義在弧集A到非負(fù)實(shí)數(shù)集合上的一個函數(shù)到非負(fù)實(shí)數(shù)集合上的一個函數(shù)f 稱為稱為G上的網(wǎng)上的網(wǎng)絡(luò)流，它表示為絡(luò)流，它表示為f (vi,vj)| (vi,vj) A ,并稱并稱f (vi,vj)為弧為弧(vi,vj)上的流量上的流量或流值（簡記為或流值（簡記為fij )。定義定義3：滿足下列條

2、件的流量：滿足下列條件的流量f 稱為可行流稱為可行流（1）容量限制：對每一?。┤萘肯拗疲簩γ恳换?vi,vj) A ，f (vi,vj) c (vi,vj) ；（2）平衡條件：）平衡條件：對中間點(diǎn)，流出量對中間點(diǎn)，流出量=流入量，即對每個流入量，即對每個i (i s, t ) 有有:網(wǎng)絡(luò)中兩個特殊點(diǎn)：發(fā)點(diǎn)網(wǎng)絡(luò)中兩個特殊點(diǎn)：發(fā)點(diǎn)vs 和收點(diǎn)和收點(diǎn)vt 0AvvjiAvvijijjiff),(),()(),(fvfvAvvsjsjs記記：對于發(fā)點(diǎn)對于發(fā)點(diǎn) )(),(fvfvAvvjtttj ：對于收點(diǎn)對于收點(diǎn)稱稱為為這這個個可可行行流流的的流流量量)( fv定義定義4：所謂最大流問題就是求一個網(wǎng)絡(luò)

3、流：所謂最大流問題就是求一個網(wǎng)絡(luò)流f (vi,vj)| (vi,vj) A ,使使它符合下列諸式：它符合下列諸式：AvvcftsifftsffvMaxjiijijjjijijjjsjsj),(,., 0 0 二、最大流的增量算法二、最大流的增量算法稱稱為為中中頂頂點(diǎn)點(diǎn)的的一一切切弧弧的的集集合合中中頂頂點(diǎn)點(diǎn)指指向向則則從從點(diǎn)點(diǎn)收收的的一一個個子子集集，發(fā)發(fā)點(diǎn)點(diǎn)中中頂頂點(diǎn)點(diǎn)集集是是網(wǎng)網(wǎng)絡(luò)絡(luò)：設(shè)設(shè)定定義義 P P P,PP,vP, v V A)(V,GP5tsA),(),(| ),(PP,PP, P,P,PP,PP,PCP, , PP,jivvijjijijicCAvvvvvv即：即：中一切弧的容

4、量之和，中一切弧的容量之和，定義為定義為它的容量它的容量割集，記作割集，記作134326554124226收點(diǎn)收點(diǎn)發(fā)點(diǎn)發(fā)點(diǎn)8341PP,535242PP, 6 5 4P 3 2 1P),(),(),(C，結(jié)論結(jié)論1：任何割集的容量給出了流量的一個上界，即：任何割集的容量給出了流量的一個上界，即PP,Cv 結(jié)論結(jié)論2： （最大流最小割集定理）（最大流最小割集定理） min)(maxPP, Cfv增量算法的基本思想：給定網(wǎng)絡(luò)增量算法的基本思想：給定網(wǎng)絡(luò)G =(V,A)的一個流之后，如何構(gòu)造的一個流之后，如何構(gòu)造g =g(vi,vj),使使f+g的流的流v (f+g)能夠比能夠比v (f)有所增加。

5、對每條?。ㄓ兴黾?。對每條?。╲i,vj)來說，只要來說，只要f(vi,vj)0 ，也允許，也允許g 取負(fù)值，或者說，在反向弧上取正值。取負(fù)值，或者說，在反向弧上取正值。相對增量網(wǎng)：定義相對增量網(wǎng)：定義G 相對相對f 的增量網(wǎng)的增量網(wǎng)G(f)如下：其頂點(diǎn)與如下：其頂點(diǎn)與G 的頂點(diǎn)的頂點(diǎn)相同，其弧由相同，其弧由G 的弧的弧(vi,vj)與與f (vi,vj)的值來構(gòu)造兩條或一條弧如下：的值來構(gòu)造兩條或一條弧如下：（1）正向?。┱蚧?vi,vj) ：構(gòu)造條件為：構(gòu)造條件為f (vi,vj)0 ,該弧容量定義為該弧容量定義為c (vi,vj)=f (vi,vj)最大流的增量算法的步驟：最大流的增量

6、算法的步驟：（1）選擇一個初始流）選擇一個初始流f 。例如，對一切。例如，對一切(vi,vj) A ，f (vi,vj) = 0 。（2）構(gòu)造）構(gòu)造G =(V,A) 的相對于的相對于f 的增量網(wǎng)絡(luò)的增量網(wǎng)絡(luò)G(f) 。（3）在增量網(wǎng)絡(luò)）在增量網(wǎng)絡(luò)G(f)上尋找從發(fā)點(diǎn)上尋找從發(fā)點(diǎn)vs 到收點(diǎn)到收點(diǎn)vt 的路。如果不存在的路。如果不存在這樣的路，轉(zhuǎn)到（這樣的路，轉(zhuǎn)到（4）。如果找到一條從）。如果找到一條從vs 到到vt 的路的路 , 以以表示表示上上所有容量所有容量c (vi,vj)的最小值（必為正），的最小值（必為正）， 稱為網(wǎng)絡(luò)流的增量。利用稱為網(wǎng)絡(luò)流的增量。利用修正網(wǎng)絡(luò)流如下：修正網(wǎng)絡(luò)流如下

7、：當(dāng)正向弧當(dāng)正向弧(vi,vj)時，時，f(vi,vj):=f(vi,vj)+ 當(dāng)負(fù)向弧當(dāng)負(fù)向弧(vi,vj) 時，時，f(vi,vj):=f(vi,vj) 修正修正 f 之后，轉(zhuǎn)（之后，轉(zhuǎn)（2）（4）以所得的）以所得的 f 作為最大流問題的解作為最大流問題的解134326554124226收點(diǎn)收點(diǎn)發(fā)點(diǎn)發(fā)點(diǎn)以上圖為例說明上述網(wǎng)絡(luò)流算法以上圖為例說明上述網(wǎng)絡(luò)流算法初始流：初始流：f(v1,v2)=4 , f(v1,v3)=1 , f(v2,v3)=2 , f(v2,v4)=1 , f(v2,v5)=1 ,f(v3,v5)=3 , f(v5,v4)=1 , f(v4,v6)=2 , f(v5,v6

8、)=3 ,且流量且流量v = 5構(gòu)造增量網(wǎng)絡(luò)構(gòu)造增量網(wǎng)絡(luò)G(f) :134326514121123收點(diǎn)收點(diǎn)發(fā)點(diǎn)發(fā)點(diǎn)4313找找G (f) 從從vs 到到vt 的路的路 及相應(yīng)增量及相應(yīng)增量 =(v1,v3),(v3,v2),(v2,v5),(v5,v6) =2 ，修正流，修正流 f ，得新的網(wǎng)絡(luò)流，得新的網(wǎng)絡(luò)流f ，其流量，其流量v=713,3432655,34,41,12,24,32,12,06,5收點(diǎn)收點(diǎn)發(fā)點(diǎn)發(fā)點(diǎn)在新的網(wǎng)絡(luò)圖中，每條弧上有兩個在新的網(wǎng)絡(luò)圖中，每條弧上有兩個數(shù)，第一個數(shù)與原圖相同，表示容數(shù)，第一個數(shù)與原圖相同，表示容量；第二個數(shù)為新流。量；第二個數(shù)為新流。對新的網(wǎng)絡(luò)流，構(gòu)造新

9、的網(wǎng)絡(luò)增量對新的網(wǎng)絡(luò)流，構(gòu)造新的網(wǎng)絡(luò)增量G(f) ，而在，而在G(f)上已找不到從上已找不到從vs 到到vt 的路。的路。734PP,5321PP,6542P1,3,P),(),(,C其流量其流量對應(yīng)的割集：對應(yīng)的割集：此時對圖中的流此時對圖中的流 f ，其流量為，其流量為7，所有它是最大流，所有它是最大流三、最小費(fèi)用的增量算法三、最小費(fèi)用的增量算法已知條件：在網(wǎng)絡(luò)已知條件：在網(wǎng)絡(luò)G =(V,A) 中，已知發(fā)點(diǎn)中，已知發(fā)點(diǎn)vs 和收點(diǎn)和收點(diǎn)vt ；流量；流量v ；容；容量量c (vi,vj)| (vi,vj) A ;每條弧每條弧(vi,vj)所相應(yīng)的代價(jià)所相應(yīng)的代價(jià)l (vi,vj) ，它的含

10、，它的含義是單位流量所相應(yīng)的費(fèi)用。義是單位流量所相應(yīng)的費(fèi)用。定義定義6 ：所謂最小費(fèi)用問題就是：要找出：所謂最小費(fèi)用問題就是：要找出f (vi,vj)| (vi,vj) A ,使得：使得：AvvvvcvvftsiAvvvvfAvvvvfvAvvvvfAvvvvftsvvfvvlzMinjijijijijijjjijijsjsjjjsjsAvvjijiji),(),(,),( | ),(),( | ),(),( | ),(),( | ),(.),(),(),(, ),0 0 最小費(fèi)用的增量算法的基本思想：利用增量網(wǎng)絡(luò)的最短路來修正網(wǎng)最小費(fèi)用的增量算法的基本思想：利用增量網(wǎng)絡(luò)的最短路來修正網(wǎng)絡(luò)流絡(luò)

11、流 f ，使流量有所增加的情況下，仍保持為最小費(fèi)用流。增量網(wǎng)，使流量有所增加的情況下，仍保持為最小費(fèi)用流。增量網(wǎng)絡(luò)的構(gòu)造與前面方法相同，但要補(bǔ)充弧的代價(jià)如下：絡(luò)的構(gòu)造與前面方法相同，但要補(bǔ)充弧的代價(jià)如下：（1）正向?。┱蚧?vi,vj) 上，有上，有c (vi,vj)= c (vi,vj) f (vi,vj) ， l (vi,vj) =l (vi,vj) （2）反向?。┓聪蚧?vi,vj) 上，有上，有c (vi,vj)=f (vi,vj) ，l (vi,vj) =l(vi,vj) 最小費(fèi)用流的增量算法的理論根據(jù)：最小費(fèi)用流的增量算法的理論根據(jù)：設(shè)設(shè) f 是網(wǎng)絡(luò)是網(wǎng)絡(luò)G = (V,A)的最小

12、費(fèi)用流，的最小費(fèi)用流，f 的流量為的流量為v ， 是增量網(wǎng)是增量網(wǎng)G(f)上從上從發(fā)點(diǎn)發(fā)點(diǎn)vs 到收點(diǎn)到收點(diǎn)vt 的以的以l( , )為代價(jià)的最短路，為代價(jià)的最短路， 為為 上所上所有弧的容量的最小值。又設(shè)有弧的容量的最小值。又設(shè)0 ，考慮沿，考慮沿 增加流量增加流量 ，用適當(dāng)方，用適當(dāng)方式修正式修正 f 。那么，修正后的網(wǎng)絡(luò)流必是流量為。那么，修正后的網(wǎng)絡(luò)流必是流量為v + 的最小費(fèi)用流。的最小費(fèi)用流。例例2：求右圖中最小費(fèi)用最大流，：求右圖中最小費(fèi)用最大流，圖中每條弧圖中每條弧 邊上第邊上第1個數(shù)是費(fèi)用，個數(shù)是費(fèi)用，第第2個數(shù)是容量。個數(shù)是容量。v1vtvsv3v2（2，4）（1，7）（6

13、，2）（2，5）（3，10）（1，8）（4，10）取初始流量取初始流量f =0為初始為初始可行流可行流構(gòu)造增量網(wǎng)絡(luò)構(gòu)造增量網(wǎng)絡(luò)G(f)，并，并以以lij 為權(quán)，求從為權(quán)，求從vs 到到vt 的最短路（雙箭頭）的最短路（雙箭頭）v1vtvsv3v2（2，4）（1，7）（6，2）（2，5）（3，10）（1，8）（4，10）v1vtvsv3v20005550在在G (f)中中 從從vs 到到vt 的最的最短路短路 為為 =(vs,v2),(v2,v1),(v1,vt) =5，修正流，修正流 f ，得新，得新的網(wǎng)絡(luò)流的網(wǎng)絡(luò)流f ，其流量，其流量v=5v1vtvsv3v2（2，4）（-1，5）（6，2）

14、（-2，5）（3，10）（1，3）（4，10）（1，2）（-1，5）v1vtvsv3v20005572在在G (f)中中 從從vs 到到vt 的最的最短路短路 為為 =(vs,v1),(v1,vt) =2 ，修正流，修正流 f ，得新，得新的網(wǎng)絡(luò)流的網(wǎng)絡(luò)流f ，其流量，其流量v=7v1vtvsv3v2（2，4）（-1，7）（6，2）（-2，5）（3，10）（1，3）（4，8）（-1，5）（-4，2）在在G (f)中中 從從vs 到到vt 的最的最短路短路 為為 =(vs,v2),(v2,v3),(v3,vt) =3 ，修正流，修正流 f ，得新，得新的網(wǎng)絡(luò)流的網(wǎng)絡(luò)流f ，其流量，其流量v=10v1vtvsv3v23035872v1vtvsv3v2（2，1）（-1，7）（6，2）（-2，5）（3，7）（-1，8）（4，8）（- 4，2）（- 2，3）（- 3，3）在在G (f)中中 從從vs 到到vt 的最的最短路短路 為為 =(vs,v1),(v1,v2), (v2,v3),(v3,vt) =1 ，修正流，修正流 f ，得新，得新的網(wǎng)絡(luò)