網(wǎng)路的最大流和最小截

1、16.4 網(wǎng)路的最大流和最小截網(wǎng)路的最大流和最小截 6.4.1 網(wǎng)路的最大流的概念網(wǎng)路的最大流的概念 網(wǎng)路流一般在有向圖上討論網(wǎng)路流一般在有向圖上討論 定義網(wǎng)路上支路的定義網(wǎng)路上支路的容量容量為其最大通過能力，記為為其最大通過能力，記為 cij ，支路上的實際支路上的實際流量流量記為記為 fij 圖中規(guī)定一個發(fā)點圖中規(guī)定一個發(fā)點s s，一個收點，一個收點t t 節(jié)點沒有容量限制，流在節(jié)點不會存儲節(jié)點沒有容量限制，流在節(jié)點不會存儲 容量限制條件容量限制條件：0 fij cij 平衡條件平衡條件： tifvtsisifvffijijvbvjivavij)(,0)()()( 滿足上述條件的網(wǎng)路流稱為

2、滿足上述條件的網(wǎng)路流稱為可行流可行流，總存在，總存在最大可行流最大可行流 當支路上當支路上 fij = cij ，稱為，稱為飽和弧飽和弧 最大流問題也是一個線性規(guī)劃問題最大流問題也是一個線性規(guī)劃問題via(vi)b(vi)2 6.4.2 截集與截集容量截集與截集容量定義定義：把網(wǎng)路分割為兩個成分的弧的最小集合，其中一：把網(wǎng)路分割為兩個成分的弧的最小集合，其中一 個成分包含個成分包含 s 點，另一個包含點，另一個包含 t 點點 。 一般包含一般包含 s 點的成分中的節(jié)點集合用點的成分中的節(jié)點集合用v表示，包含表示，包含 t 點點的成分中的節(jié)點集合用的成分中的節(jié)點集合用v表示表示 截集容量截集容量

3、是指截集中正向弧的容量之和是指截集中正向弧的容量之和 vjviijcvvc),( 福特福特-富克森定理富克森定理：網(wǎng)路的最大流等于最小截集容量：網(wǎng)路的最大流等于最小截集容量st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(5,0)3 6.4.3 確定網(wǎng)路最大流的標號法確定網(wǎng)路最大流的標號法 從任一個初始可行流出發(fā)，如從任一個初始可行流出發(fā)，如 0 流流 基本算法：找一條從基本算法：找一條從 s 到到 t 點的點的增廣鏈增廣鏈(augmenting path) 若在當前可行流下找不到增廣鏈，則已得到最大流若在當前可行流下找不到增廣鏈，則已得到最大流 增

4、廣鏈中與增廣鏈中與 s 到到 t 方向一致的弧稱為方向一致的弧稱為前向弧前向弧，反之，反之后向弧后向弧 增廣過程：前向弧增廣過程：前向弧 f ij=fij +q q , , 后向弧后向弧 f ij=fij q q 增廣后仍是可行流增廣后仍是可行流 st5432(3,0)(5,3)(1,1)(5,1)(1,1)q qs2=4q q5t=2q q45=3q q43=1q q32=1增增廣廣量量 q q = min q qij= min(4,1,1,3,2)= 1st5432(3,1)(5,4)(1,0)(5,2)(1,0) 后后向向弧弧前前向向弧弧ijijijijffcq q4 最大流最小截的標號

5、法步驟最大流最小截的標號法步驟第一步：標號過程，找一條增廣鏈第一步：標號過程，找一條增廣鏈1、給源點給源點 s 標號標號s+,q q(s)= ，表示從，表示從 s 點有無限流出潛力點有無限流出潛力2、找出與已標號節(jié)點找出與已標號節(jié)點 i 相鄰的所有未標號節(jié)點相鄰的所有未標號節(jié)點 j，若，若(1) (i, j)是前向弧且飽和，則節(jié)點是前向弧且飽和，則節(jié)點 j 不標號；不標號；(2) (i, j)是前向弧且未飽和，則節(jié)點是前向弧且未飽和，則節(jié)點 j 標號為標號為i+,q q(j)，表示從節(jié)點，表示從節(jié)點 i 正正向向流出，可增廣流出，可增廣 q q(j)=minq q(i), cij fij ；(

6、3) (j, i)是后向弧，若是后向弧，若 fji=0，則節(jié)點，則節(jié)點 j 不標號；不標號；(4) (j, i)是后向弧，若是后向弧，若 fji0，則節(jié)點，則節(jié)點 j 標號為標號為i ,q q(j)，表示從節(jié)點，表示從節(jié)點 j 流流向向 i，可增廣，可增廣 q q(j)=minq q(i), fji ；3、重復(fù)步驟重復(fù)步驟 2，可能出現(xiàn)兩種情況：，可能出現(xiàn)兩種情況：(1) 節(jié)點節(jié)點 t 尚未標號，但無法繼續(xù)標記，說明網(wǎng)路中已不存在增廣鏈，尚未標號，但無法繼續(xù)標記，說明網(wǎng)路中已不存在增廣鏈，當前流當前流 v(f) 就是最大流；所有獲標號的節(jié)點在就是最大流；所有獲標號的節(jié)點在 v 中，未獲標號節(jié)中

7、，未獲標號節(jié)點在點在 v 中，中，v 與與 v 間的弧即為最小截集；算法結(jié)束間的弧即為最小截集；算法結(jié)束(2)節(jié)點節(jié)點 t 獲得標號，找到一條增廣鏈，由節(jié)點獲得標號，找到一條增廣鏈，由節(jié)點 t 標號回溯可找出該增標號回溯可找出該增廣鏈；到第二步廣鏈；到第二步5 最大流最小截的標號法步驟最大流最小截的標號法步驟第二步：增廣過程第二步：增廣過程1、對、對增廣鏈中的前向弧，令增廣鏈中的前向弧，令 f =f+q q(t)，q q(t) 為節(jié)點為節(jié)點 t 的標記值的標記值2、對對增廣鏈中的后向弧，令增廣鏈中的后向弧，令 f =f q q(t)3、非增廣鏈上的所有支路流量保持不變、非增廣鏈上的所有支路流量

8、保持不變第三步：抹除圖上所有標號，回到第一步第三步：抹除圖上所有標號，回到第一步 以上算法是按廣探法描述的，但在實際圖上作業(yè)時，按深以上算法是按廣探法描述的，但在實際圖上作業(yè)時，按深探法進行更快捷探法進行更快捷 一次只找一條增廣鏈，增廣一次換一張圖一次只找一條增廣鏈，增廣一次換一張圖 最后一次用廣探法，以便找出最小截集最后一次用廣探法，以便找出最小截集6最大流最小截集的標號法舉例最大流最小截集的標號法舉例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)st134

9、256(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+, )(s+,5)(2+,2)(5 ,2)(4+,2)7最大流最小截集的標號法舉例最大流最小截集的標號法舉例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)

10、(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)最小截集最小截集8 最大流標號法的復(fù)雜度討論最大流標號法的復(fù)雜度討論stvu20002000200020001找一條增廣鏈的計算量是容易估計的，不會超過找一條增廣鏈的計算量是容易估計的，不會超過o(n2)但是最多迭代多少次但是最多迭代多少次(即增廣的次數(shù)即增廣的次數(shù))就很難估計，在最壞情就很難估計，在最壞情況下，與邊的容量有關(guān)；如上圖：先增廣況下，與邊的容量有關(guān)；如上圖：先增廣 s u v t , 然后增廣然后增廣 s v u t，每次只能增廣

11、，每次只能增廣 1 個單位，故要增個單位，故要增廣廣4000次才能結(jié)束次才能結(jié)束克服這種缺點的經(jīng)驗方法：克服這種缺點的經(jīng)驗方法： 盡量先用段數(shù)少的增廣鏈盡量先用段數(shù)少的增廣鏈 盡量不重復(fù)前面出現(xiàn)過的增廣鏈盡量不重復(fù)前面出現(xiàn)過的增廣鏈9 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ā)點發(fā)點120發(fā)點發(fā)點220收點收點115收點收點220(5,0)18764352(15,10)(10,10)(20,5)(5,5)(5,5)(5,5)(5,5)(5,0)

12、(10,5)(10,10)(10,5)(10,0)虛發(fā)點虛發(fā)點虛收點虛收點st(20,15)(20,15)(20,15)(15,15)(5,0)10 6.4.5 最小費用最大流最小費用最大流雙權(quán)網(wǎng)路雙權(quán)網(wǎng)路：每條弧不但有容量，還有單位流量的通過費用：每條弧不但有容量，還有單位流量的通過費用兩種解法：一種基于最小費用路徑算法；一種基于可行弧集兩種解法：一種基于最小費用路徑算法；一種基于可行弧集的最大流算法的最大流算法基于最小費用路徑算法基于最小費用路徑算法：總是在當前找到的最小費用的路徑：總是在當前找到的最小費用的路徑上增廣流；缺點是每次增廣后要改變弧的費用，且出現(xiàn)負權(quán)上增廣流；缺點是每次增廣后

13、要改變弧的費用，且出現(xiàn)負權(quán)值費用的弧值費用的弧基于可行弧集的最大流算法基于可行弧集的最大流算法：從：從 0 費用弧集開始應(yīng)用最大流費用弧集開始應(yīng)用最大流算法，然后根據(jù)計算信息提高費用的限界算法，然后根據(jù)計算信息提高費用的限界p，使可行弧集增，使可行弧集增大，再應(yīng)用最大流算法，直至所有弧都進入可行弧集。這種大，再應(yīng)用最大流算法，直至所有弧都進入可行弧集。這種算法是一種主算法是一種主-對偶規(guī)劃的解法。使用這種方法的還有運輸對偶規(guī)劃的解法。使用這種方法的還有運輸問題、匹配問題問題、匹配問題11 6.4.5 以最短路為基礎(chǔ)匯總網(wǎng)路上的流以最短路為基礎(chǔ)匯總網(wǎng)路上的流13245電路交換網(wǎng)電路交換網(wǎng)13245傳輸網(wǎng)傳輸網(wǎng)在電路網(wǎng)中每兩點之間都有中繼電路群需求，但并不是任在電路網(wǎng)中每兩點之間都有中繼電路群需求，但并不是任兩點都有物理傳輸鏈路兩點都有物理傳輸鏈路根據(jù)兩點間最短傳輸路徑將該兩點間的電路需求量加載到根據(jù)兩點間最短傳輸路徑將該兩點間的電路需求量加載到這條傳