【文章內容簡介】 ijkikj ldd ???2 5② 38 }m in { 4)1()2(4 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 5② 10② 39 }m in { 5)1()2(5 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 5② 10② 9③ 40 }m in { 6)1()2(6 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 5② 10② 9③ ∞ 41 )3(jd}m in { )2()3( ijij ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 5② 10② 9③ ∞ 0 2 5 10 8③ 10⑤ 42 )3(jd}m in { )3()4( ijij ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 5② 10② 9③ ∞ 0 2 5 10 8③ 10⑤ )4(jd0 2 5 10 8③ 9⑤ 43 )3(jd}m in { )4()5( ijij ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 5② 10② 9③ ∞ 0 2 5 10 8③ 10⑤ )4(jd0 2 5 10 8③ 9⑤ )5(jd0 2 5 10 8 9 44 例 5求圖 ， v1到其它各點的最短路。 圖 v1 v2 v3 v4 v5 v6 v7 v8 3 4 1 4 2 2 5 4 5 3 2 4 3 5 4 45 j i lij dj(1) dj(2) dj(3) dj(4) dj(5) dj(6) v1 v2 v3 v4 v5 v6 v7 v8 v1 0 3 4 0 0 0 0 0 0 v2 0 1 2 4 3 3 3 3 3 3 v3 0 5 4 2 2 2 2 2 v4 2 0 4 5 1 1 1 1 1 v5 0 2 3 7 5 5 5 5 v6 0 4 5 3 3 3 v7 3 4 0 5 9 7 7 7 7 v8 0 10 8 7 7 46 第四節(jié) 最大流問題 給定一個有向圖 G = (V,E)，每條邊(vi,vj)給定一個非負數 cij稱為邊 (vi,vj)容量。假設 G中只有一個入度為零的點 vs稱為發(fā)點，只有一個出度為零的點 vt稱為收點，其余點稱為中間點，這樣的有向圖稱為容量網絡，記為 G = (V,E,C)。 47 例如圖 。如果 vs表示油田， vt表示煉油廠，圖 廠的輸油管道網。邊上的數字表示該管道的最大輸油能力，中間點表示輸油泵站?，F在要問如何安排各管道輸油量，才能使從 vs到 vt輸油量最大？這就是本節(jié)所要介紹的最大流問題。 圖 v1 v2 v3 v4 vs vt 5 4 1 4 2 5 3 7 8 48 一、基本概念 給定一個容量網絡 G = (V,E,C)，所謂網絡 G上的流，是指每條邊 (vi,vj)上確定的一個數 f(vi,vj)，簡記為 fij，稱集合 f={fij}為網絡 G上的一個流。 如果網絡 G表示一個輸油管道網，則 cij表示管道輸油能力，而 fij表示管道當前的實際流量，因此應有 0?fij?cij，即管道中的流量不能超過該管道的最大通過能力（即管道的容量）。對網絡 G上的中間點表示一個轉送泵站，因此對中間點運出的總量與運進的總量應當相等。而對于發(fā)點的凈流出量和收點的凈流入量必相等，并且就是該運輸方案的總輸送量。 49 0?? ??kkijij ff? ? ??i kktsi Wff容量網絡 G = (V,E,C)中的一個流 f={fij}滿足下列條件，稱 f為可行流。 （ 1）容量限制條件：對 G中每條邊 (vi,vj)， 有 0?fij?cij。 （ 2）平衡條件：對于中間點 vi，有 （即流出量＝流入量）。 對于收點 vt與發(fā)點 vs，有 （即從 vs的凈輸出量與 vt的凈輸入量相等）。 W稱為可行流 f的流量。 可行流總是存在的，當所有邊的流量 fij =0時，就得到一個可行流，它的流量 W = 0。最大流問題就是在容量網絡中，尋找流量最大的可行流。 50 對于容量網絡 G給定一個可行流 f={fij}，當 fij = cij時，稱邊 (vi,vj)為飽和邊，當 fij cij時，稱邊 (vi,vj)為非飽和邊，當 fij =0時，稱邊 (vi,vj)為零流邊，當 fij 0時，稱邊 (vi,vj)為非零流邊。 設 μ是網絡 G中一條聯結發(fā)點 vs和收點 vt的鏈 。 我們規(guī)定 μ的正方向從 vs到 vt，則鏈 μ上的邊被分為兩類：一類是邊的方向與鏈的正方向一致，稱它們?yōu)榍跋蜻叄?μ上上前向邊的全體記為 μ +。 另一類邊與鏈的正方向相反，稱它們?yōu)楹笙蜻叄?μ上后向邊的全體記為 μ 。 51 v1 v2 v3 v4 v5 vs vt (13,7) (5,5) (9,9) (4,4) (6,6) (5,2) (5,0) (4,0) (5,5) (4,4) (9,7) (10,5) 圖 例如，在圖 ，其邊上的兩個數字分別表示邊的容量和流量，即 (cij , fij)。 (v2,v5)為飽和邊，(vs,v1)為非飽和邊，并且 (v2,v5)， (vs,v1)均為非零流邊， (v3,v5)是零流邊。 52 例如圖 ，在聯結 vs和 vt的鏈 μ={vs, v1, v2 ,v5, vt}