1、6.4 網(wǎng)路的最大流和最小截網(wǎng)路的最大流和最小截 6.4.1 網(wǎng)路的最大流的概念網(wǎng)路流一般在有向圖上討論定義網(wǎng)路上支路的容量為其最大通過能力，記為 cij ，支路上的實(shí)際流量記為 fij 圖中規(guī)定一個(gè)發(fā)點(diǎn)s，一個(gè)收點(diǎn)t節(jié)點(diǎn)沒有容量限制，流在節(jié)點(diǎn)不會(huì)存儲(chǔ)容量限制條件：0 fij cij 平衡條件： tifvtsisifvffijijvBvjivAvij)(,0)()()( 滿足上述條件的網(wǎng)路流稱為可行流，總存在最大可行流滿足上述條件的網(wǎng)路流稱為可行流，總存在最大可行流 當(dāng)支路上當(dāng)支路上 fij = cij ，稱為飽和弧，稱為飽和弧 最大流問題也是一個(gè)線性規(guī)劃問題最大流問題也是一個(gè)線性規(guī)劃問題vi

2、A(vi)B(vi) 6.4.2 截集與截集容量截集與截集容量定義：把網(wǎng)路分割為兩個(gè)成分的弧的最小集合，其中一 個(gè)成分包含 s 點(diǎn)，另一個(gè)包含 t 點(diǎn) 。一般包含 s 點(diǎn)的成分中的節(jié)點(diǎn)集合用V表示，包含 t 點(diǎn)的成分中的節(jié)點(diǎn)集合用V表示截集容量是指截集中正向弧的容量之和 VjViijcVVC),( 福特福特-富克森定理：網(wǎng)路的最大流等于最小截集容量富克森定理：網(wǎng)路的最大流等于最小截集容量st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(5,0) 6.4.3 確定網(wǎng)路最大流的標(biāo)號(hào)法確定網(wǎng)路最大流的標(biāo)號(hào)法 從任一個(gè)初始可行流出發(fā)，如 0 流 基本算法：找

3、一條從 s 到 t 點(diǎn)的增廣鏈(augmenting path) 若在當(dāng)前可行流下找不到增廣鏈，則已得到最大流 增廣鏈中與 s 到 t 方向一致的弧稱為前向弧，反之后向弧 增廣過程：前向弧增廣過程：前向弧 fij=fij +q , 后向弧后向弧 fij=fij q 增廣后仍是可行流增廣后仍是可行流 st5432(3,0)(5,3)(1,1)(5,1)(1,1) s2=4 5t=2 45=3 43=1 32=1增增廣廣量量 = min ij= min(4,1,1,3,2)= 1st5432(3,1)(5,4)(1,0)(5,2)(1,0) 后后向向弧弧前前向向弧弧ijijijijffc 最大流最

4、小截的標(biāo)號(hào)法步驟最大流最小截的標(biāo)號(hào)法步驟第一步：標(biāo)號(hào)過程，找一條增廣鏈1、給源點(diǎn) s 標(biāo)號(hào)s+,q(s)=，表示從 s 點(diǎn)有無限流出潛力2、找出與已標(biāo)號(hào)節(jié)點(diǎn) i 相鄰的所有未標(biāo)號(hào)節(jié)點(diǎn) j，假設(shè)(1) (i, j)是前向弧且飽和，則節(jié)點(diǎn) j 不標(biāo)號(hào)；(2) (i, j)是前向弧且未飽和，則節(jié)點(diǎn) j 標(biāo)號(hào)為i+,q(j)，表示從節(jié)點(diǎn) i 正向流出，可增廣 q(j)=minq(i), cijfij ；(3) (j, i)是后向弧，假設(shè) fji=0，則節(jié)點(diǎn) j 不標(biāo)號(hào)；(4) (j, i)是后向弧，假設(shè) fji0，則節(jié)點(diǎn) j 標(biāo)號(hào)為i,q(j)，表示從節(jié)點(diǎn) j 流向 i，可增廣 q(j)=minq(i

5、), fji ；3、重復(fù)步驟 2，可能出現(xiàn)兩種情況：(1) 節(jié)點(diǎn) t 尚未標(biāo)號(hào)，但無法繼續(xù)標(biāo)記，說明網(wǎng)路中已不存在增廣鏈，當(dāng)前流 v(f) 就是最大流；所有獲標(biāo)號(hào)的節(jié)點(diǎn)在 V 中，未獲標(biāo)號(hào)節(jié)點(diǎn)在 V 中，V 與 V 間的弧即為最小截集；算法結(jié)束(2)節(jié)點(diǎn) t 獲得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn) t 標(biāo)號(hào)回溯可找出該增廣鏈；到第二步 最大流最小截的標(biāo)號(hào)法步驟最大流最小截的標(biāo)號(hào)法步驟第二步：增廣過程1、對(duì)增廣鏈中的前向弧，令 f=f+q(t)，q(t) 為節(jié)點(diǎn) t 的標(biāo)記值2、對(duì)增廣鏈中的后向弧，令 f=fq(t)3、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標(biāo)號(hào)，回到第一步以上算法是按廣

6、探法描述的，但在實(shí)際圖上作業(yè)時(shí)，按深探法進(jìn)行更快捷一次只找一條增廣鏈，增廣一次換一張圖最后一次用廣探法，以便找出最小截集最大流最小截集的標(biāo)號(hào)法舉例最大流最小截集的標(biāo)號(hào)法舉例st134256(14,14)(9,9)(15,9)(16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+

7、,)(s+,5)(2+,2)(5,2)(4+,2)最大流最小截集的標(biāo)號(hào)法舉例最大流最小截集的標(biāo)號(hào)法舉例st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)st134256(14,14)(9,9)(15,12)(16,15)(3,1)(12,12)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)(s+,)(s+,3)(2,3)最小截集最小截集 最大流標(biāo)號(hào)法的復(fù)雜度討論最大流標(biāo)號(hào)法的復(fù)雜度討論stvu200020002000

8、20001找一條增廣鏈的計(jì)算量是容易估計(jì)的，不會(huì)超過O(n2)但是最多迭代多少次(即增廣的次數(shù))就很難估計(jì)，在最壞情況下，與邊的容量有關(guān)；如上圖：先增廣 s u v t , 然后增廣 s v u t，每次只能增廣 1 個(gè)單位，故要增廣4000次才能結(jié)束克服這種缺點(diǎn)的經(jīng)驗(yàn)方法：盡量先用段數(shù)少的增廣鏈盡量不重復(fù)前面出現(xiàn)過的增廣鏈 6.4.4 多端網(wǎng)路問題多端網(wǎng)路問題18764352(15, 0)(10, 0)(20,0)(5,0)(5,0)(5,0)(5,0)(5,0)(10,0)(10, 0)(10,0)(10,0)發(fā)點(diǎn)發(fā)點(diǎn)120發(fā)點(diǎn)發(fā)點(diǎn)220收點(diǎn)收點(diǎn)115收點(diǎn)收點(diǎn)220(5,0)1876435

9、2(15,10)(10,10)(20,5)(5,5)(5,5)(5,5)(5,5)(5,0)(10,5)(10,10)(10,5)(10,0)虛發(fā)點(diǎn)虛發(fā)點(diǎn)虛收點(diǎn)虛收點(diǎn)st(20,15)(20,15)(20,15)(15,15)(5,0) 6.4.5 最小費(fèi)用最大流最小費(fèi)用最大流雙權(quán)網(wǎng)路：每條弧不但有容量，還有單位流量的通過費(fèi)用兩種解法：一種基于最小費(fèi)用路徑算法；一種基于可行弧集的最大流算法基于最小費(fèi)用路徑算法：總是在當(dāng)前找到的最小費(fèi)用的路徑上增廣流；缺點(diǎn)是每次增廣后要改變弧的費(fèi)用，且出現(xiàn)負(fù)權(quán)值費(fèi)用的弧基于可行弧集的最大流算法：從 0 費(fèi)用弧集開始應(yīng)用最大流算法，然后根據(jù)計(jì)算信息提高費(fèi)用的限界P，使可行弧集增大，再應(yīng)用最大流算法，直至所有弧都進(jìn)入可行弧集。這種算法是一種主-對(duì)偶規(guī)劃的解法。使用這種方法的還有運(yùn)輸問題、匹配問題 6.4.5 以最短路為基礎(chǔ)匯總網(wǎng)路上的流以最短路為基礎(chǔ)匯總網(wǎng)路上的流13245電路交換網(wǎng)電路交換網(wǎng)13245傳輸網(wǎng)傳輸網(wǎng)在電路網(wǎng)中每?jī)牲c(diǎn)之間都有中繼電路群需求，但并不是任兩點(diǎn)都有物理傳輸鏈路根據(jù)兩點(diǎn)間最短傳輸路徑將該兩