1、2020/9/3,山東交通學(xué)院信息工程系,1,最大流量問題,本節(jié)內(nèi)容 相關(guān)概念與基本定理 求解網(wǎng)絡(luò)最大流方法,2020/9/3,山東交通學(xué)院信息工程系,2,流量網(wǎng)絡(luò)定義,給定一個n個頂點(diǎn)加權(quán)連通圖，該圖具有如下特性： 包含1個沒有輸入邊的頂點(diǎn)；該點(diǎn)稱為源點(diǎn)。 包含1個沒有輸出邊的頂點(diǎn)；該點(diǎn)稱為匯點(diǎn)。 每條有向邊的權(quán)重uij是一個正整數(shù)，稱為該邊的容量(這個數(shù)字表示該邊所代表的鏈路把物質(zhì)從i送到j(luò)的數(shù)量上限)。 滿足以上特性的有向圖稱為流量網(wǎng)絡(luò)。,2020/9/3,山東交通學(xué)院信息工程系,3,設(shè)源點(diǎn)與匯點(diǎn)分別是物質(zhì)流中惟一的出發(fā)地和目的地。 進(jìn)入中間點(diǎn)物質(zhì)總量必須等于離開物質(zhì)總量，這個條件稱為能

2、量守恒要求。 如果用xij來標(biāo)記通過邊(i,j)傳輸量，則：,2020/9/3,山東交通學(xué)院信息工程系,4,容量約束： 對于每條邊(i,j)E來說，0 xijuij 可行解： 一個給定一個網(wǎng)絡(luò)的流，使得它滿足流量守恒約束和容量約束。 最大流量問題：,2020/9/3,山東交通學(xué)院信息工程系,5,最大流量求解方法,最大流量問題求解有兩種方法 單純形法 增益路徑法,2020/9/3,山東交通學(xué)院信息工程系,6,增益路徑法,從流量0開始，試著找一條可以傳輸更多流量的、從源點(diǎn)到匯點(diǎn)的路徑。這樣路徑稱為流量增益。,如果找到了一條流量增益路徑，沿路徑調(diào)整邊上的流量，以得到更大的流量值。迭代,直到找不到為止

3、。,2020/9/3,山東交通學(xué)院信息工程系,7,增益路徑的實(shí)現(xiàn)舉例,沿路徑12 3 6，最多把流量增加2個單位。 由于不能再進(jìn)一步增加，算法結(jié)束，得到結(jié)果（b）。 但此時不為最優(yōu)結(jié)果，沿路徑14 32 5 6流量還能增加。,2020/9/3,山東交通學(xué)院信息工程系,8,擴(kuò)展增益路徑法,為求流量x的增益路徑，需考慮兩類邊： 前向邊：從i連向j，該邊具有正的未使用的容量rij=uij-xij。 后向邊：從j連向i，該邊具有正的流量xji,i,j,未使用的容量rij=uij-xij,i,j,流量xji,前向邊,后向邊,2020/9/3,山東交通學(xué)院信息工程系,9,擴(kuò)展增益路徑法,對于給定容量的增益

4、路徑，設(shè)r是所有前向邊中未使用的容量和后向邊中具有正的容量xji 中的最小值。 如果在每條前向邊上增加容量r，在向后邊上減去r，得到一個更大的可行流量。,2020/9/3,山東交通學(xué)院信息工程系,10,擴(kuò)展增益路徑的實(shí)現(xiàn)舉例,上圖b中，增益路徑14 32 5 6。(1,4),(4,3),(2,5),(5,6)是前向邊，(3,2)是后向邊，最小值r=1，根據(jù)r值進(jìn)行調(diào)整，得到c。,2020/9/3,山東交通學(xué)院信息工程系,11,增益路徑法性能退化,路徑生成次序如果不恰當(dāng)，會對該方法效率產(chǎn)生巨大的影響，如下圖： 沿路徑12 3 4對流量0進(jìn)行增益，會得到(b)中值為1的流量。 沿路徑1 32 4對

5、流量0進(jìn)行擴(kuò)展增益，會得到(c)中值為2的流量。,共迭代2U次才能得到最大流量值2U。,2020/9/3,山東交通學(xué)院信息工程系,12,增益路徑法性能退化,2次得到最大流量值方法： 沿路徑12 4 對流量0進(jìn)行增益。 沿路徑13 4 對流量0進(jìn)行增益。,增益路徑法依賴于路徑生成次序，生成次序不恰當(dāng)，會對該方法效率產(chǎn)生巨大的影響。,2020/9/3,山東交通學(xué)院信息工程系,13,最短增益路徑法,基本思想：用廣度優(yōu)先查找，用數(shù)量最少的邊來生成增益路徑。 具體策略：兩個記號來標(biāo)記一個新的(未標(biāo)記)頂點(diǎn) 第一個標(biāo)記指出從源點(diǎn)到被標(biāo)記頂點(diǎn)還能增加多少流量。 第二個標(biāo)記指出另一個頂點(diǎn)的名字。,2020/9

6、/3,山東交通學(xué)院信息工程系,14,兩個記號來標(biāo)記一個新的(未標(biāo)記)頂點(diǎn) 第一個標(biāo)記指出從源點(diǎn)到被標(biāo)記頂點(diǎn)還能增加多少流量。 第二個標(biāo)記指出另一個頂點(diǎn)的名字。 第二個標(biāo)記加上+或-號，用來指出該頂點(diǎn)是通過前向邊還是后向邊得到的。,2020/9/3,山東交通學(xué)院信息工程系,15,如果未標(biāo)記頂點(diǎn)j是由從i到j(luò)的有向邊和遍歷隊(duì)列中的前面頂點(diǎn)i相連接，而且j具有大于0的未使用容量rij=uij-xij,那么頂點(diǎn)j就標(biāo)記為lj,i+，其中l(wèi)j=minli,rij。,2020/9/3,山東交通學(xué)院信息工程系,16,如果未標(biāo)記頂點(diǎn)j是由從j到i的有向邊和遍歷隊(duì)列中的前面頂點(diǎn)i相連接，而且j具有大于0的流量x

7、ij,那么頂點(diǎn)j就標(biāo)記為lj,i-，其中l(wèi)j=minli,xij。,2020/9/3,山東交通學(xué)院信息工程系,17,處理2結(jié)點(diǎn)時，由于從1到2未使用容量為2，因此2頂點(diǎn)標(biāo)記為min,2,1+. 處理3結(jié)點(diǎn)時，由于從2到3未使用容為5，因此3頂點(diǎn)標(biāo)記為min2,5,2+. 這種標(biāo)記的遍歷結(jié)束于匯點(diǎn)6，沿著路徑12 3 6用2對流量進(jìn)行增益。,2020/9/3,山東交通學(xué)院信息工程系,18,下一次迭代時過程。 這種標(biāo)記的遍歷結(jié)束于匯點(diǎn)6，沿著路徑14 3 25 6用1對流量進(jìn)行增益。,2020/9/3,山東交通學(xué)院信息工程系,19,再一次迭代時 由于沒有增益路徑(匯點(diǎn)沒有被標(biāo)記)，當(dāng)前流量已經(jīng)是最

8、大的了。,2020/9/3,山東交通學(xué)院信息工程系,20,標(biāo)號法步驟如下： 第一步 找出一個初始可行流fij(0),例如所有弧的流量fij(0) =0. 第二步 利用廣度優(yōu)先搜對點(diǎn)進(jìn)行標(biāo)號找出一條增益路徑。 （1） 起點(diǎn)標(biāo)號（） （2）選一個點(diǎn)vi已標(biāo)號且另一端未標(biāo)號的弧沿著某條鏈向收點(diǎn)檢查 （a）如果弧是前向弧且有fijcij，則vj標(biāo)號 j=cijfij （b）如果弧是后向弧且有fij0，則vj標(biāo)號j=fij,2020/9/3,山東交通學(xué)院信息工程系,21,當(dāng)收點(diǎn)已得到標(biāo)號時，說明已找到增益路徑，依據(jù)v的標(biāo)號反向追蹤得到一條增益路徑。當(dāng)收點(diǎn)不能得到標(biāo)號時，說明不存在增益路徑，計算結(jié)束 第三

9、步 調(diào)整流量 (1) 求增廣鏈上點(diǎn)的vi標(biāo)號的最小值，得到調(diào)整量號 (2) 調(diào)整流量,2020/9/3,山東交通學(xué)院信息工程系,22,fij+ （vi，vj）u+ f1= fij （vi，vj)u- fij （vi，vj ) u 得到新的可行流f1，去掉所有標(biāo)號，返回到第二步從發(fā)點(diǎn)重新標(biāo)號尋找增益路徑，直到收點(diǎn)不能標(biāo)號為止。,2020/9/3,山東交通學(xué)院信息工程系,23,定義：（截集或割集） 如果N表示某網(wǎng)絡(luò)中所有點(diǎn)的集合，將N分成兩個子集S與S，使得發(fā)點(diǎn)v0在S內(nèi)，收點(diǎn)vn在S 內(nèi)，則稱（S，S）為分離發(fā)點(diǎn)與收點(diǎn)的割集。顯然，SS=N ，SS=，V0 S ，VnS,2020/9/3,山東交

10、通學(xué)院信息工程系,24,v0,vn,v2,v1,a,割集a：v0v1，v0v2，v0vn,2020/9/3,山東交通學(xué)院信息工程系,25,v0,vn,v2,v1,b,割集b：v1vn，v2vn，v0vn,2020/9/3,山東交通學(xué)院信息工程系,26,v0,vn,v2,v1,c,割集c：v1vn，v1v2，v2v1，v0v2 ，v0vn,2020/9/3,山東交通學(xué)院信息工程系,27,v0,vn,v2,v1,d,割集d：v0v1，v1v2，v2v1，v2vn，v0vn,2020/9/3,山東交通學(xué)院信息工程系,28,定義（割的容量）從S中各頂點(diǎn)到S中各頂點(diǎn)全部容量之和稱為割的容量（截量），用（

11、S，S）表示。,2020/9/3,山東交通學(xué)院信息工程系,29,割集a: Ca=C01+C02+C0n 割集b: Cb=C1n+C2n+C0n 割集c: Cc=C1n+C12+ C02+ C0n 割集d: Cd=C01+C21+ C2n+ C0n,2020/9/3,山東交通學(xué)院信息工程系,30,v0,vn,v2,v1,c,S,S,在截集c中邊v2v1是反向的，其容量視為零。,2020/9/3,山東交通學(xué)院信息工程系,31,v0,vn,v2,v1,d,S,S,在截集d中邊v1v2是反向的，其容量視為零。,2020/9/3,山東交通學(xué)院信息工程系,32,定義（最小截量） 一個網(wǎng)絡(luò)中，各種截集中容量最小的稱為最小截量，用min C(S,S)表示。,2020/9/3,山東交通學(xué)院信息工程系,33,現(xiàn)在我們把一個網(wǎng)絡(luò)看成是一個自來水管網(wǎng)絡(luò)，煤氣管網(wǎng)絡(luò)，電力線網(wǎng)絡(luò)或公路網(wǎng)絡(luò)，鐵路網(wǎng)絡(luò)，水運(yùn)交通網(wǎng)絡(luò)等，都可以歸納成一個運(yùn)輸問題，稱為網(wǎng)絡(luò)流，值得關(guān)心問題是在這樣一個網(wǎng)絡(luò)中最大流為多少？,2020/9/3,山東交通學(xué)院信息工程系,34,定義（流）若對網(wǎng)絡(luò)N，函數(shù)f滿足如下條件： （1）0 fij Cij (i,j)E(N) （2）f-(vi) = f+(vi) iV(N) 則稱f為N的一個網(wǎng)絡(luò)流，簡稱流。,2020/9/3,山東交通學(xué)