【正文】 ?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到其它各點(diǎn)的最短路。如果 vs表示油田， vt表示煉油廠，圖 廠的輸油管道網(wǎng)。 如果網(wǎng)絡(luò) G表示一個(gè)輸油管道網(wǎng)，則 cij表示管道輸油能力，而 fij表示管道當(dāng)前的實(shí)際流量，因此應(yīng)有 0?fij?cij，即管道中的流量不能超過該管道的最大通過能力（即管道的容量）。 （ 1）容量限制條件：對(duì) G中每條邊 (vi,vj)， 有 0?fij?cij。 可行流總是存在的，當(dāng)所有邊的流量 fij =0時(shí)，就得到一個(gè)可行流，它的流量 W = 0。 我們規(guī)定 μ的正方向從 vs到 vt，則鏈 μ上的邊被分為兩類：一類是邊的方向與鏈的正方向一致，稱它們?yōu)榍跋蜻叄?μ上上前向邊的全體記為 μ +。 52 例如圖 ，在聯(lián)結(jié) vs和 vt的鏈 μ={vs, v1, v2 ,v5, vt}中， (vs,v1)， (v2,v5)， (v5, vt)為前向邊， (v1,v2)為后向邊 。 則稱 μ是一條 增廣鏈 。 設(shè) S2={vs,v1}， T 2={ v2, v3, v4, v5, vt}則 (S2, T2)={ (vs,v2)， (v1,v4)}，其容量為 C (S2, T2)=20。如果把網(wǎng)絡(luò) G看成各種粗細(xì)不同的管道網(wǎng)，而最小割集就相當(dāng)于管道網(wǎng)中最細(xì)管道部分的總和。 推論 在任意一個(gè)容量網(wǎng)絡(luò)中，最大流的流量等于最小割集的容量。尋找關(guān)于可行流 f的增廣鏈可按下面介紹的標(biāo)號(hào)法來實(shí)現(xiàn)。 （ 2）選擇一個(gè)已標(biāo)號(hào)的頂點(diǎn) vi，對(duì)所有與 vi相鄰而沒有標(biāo)號(hào)的頂點(diǎn) vj按下列規(guī)則處理。 2 調(diào)整過程 首先按終點(diǎn) vt及其它頂點(diǎn)的第一個(gè)標(biāo)號(hào)，用反向追蹤法在網(wǎng)絡(luò)中找出增廣鏈。 61 ????????,39。因?yàn)?(vs,v2)?E，但 fs2=cs2，所以 v2不能標(biāo)號(hào)。 (vs,11) (v1,3) (v1,4) 66 vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) （ 4）檢查與 v2相鄰 且沒有標(biāo)號(hào) 的頂點(diǎn) v3， 因?yàn)?v2,v3)?E， 并且 f23=1c23=5，所以 v3可以獲得標(biāo)號(hào)(v2,δ3)，其中 δ3 min{δ2, c23f23 }=min{3,51}=3 。 (v4,4) 68 vs vt v4 v2 v3 v1 (15,4) (9,9) (3,3) (5,1) (6,5) (7,7) (10,5) (11,8) (4,0) (0,+∞) (vs,11) (v1,3) (v1,4) (v2,3) (v4,4) （ II）調(diào)整過程 由于 vt的第一個(gè)標(biāo)號(hào)為 v4，得到頂點(diǎn) v4，由 v4的第一個(gè)標(biāo)號(hào)為 v1，得到頂點(diǎn) v1，由 v1的第一個(gè)標(biāo)號(hào)為 vs，得到頂點(diǎn) vs ，由此得到關(guān)于可行流 f的增廣鏈 μ={vs, v1, v4 , vt}，其中 (vs,v1),(v1,v4) ,(v4,vt)為前向邊。 72 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,9) (v1,3) （ 3）檢查與 v1相鄰 且沒有標(biāo)號(hào) 的頂點(diǎn) v2， v3， v4，因?yàn)?(v2,v1)?E，并且 f210，所以 v2可以獲得標(biāo)號(hào)(v1,δ2)，其中 δ2 =min{δ1, f21}=min{9,3}=3。 因?yàn)?(v2,v4)?E，并且f24=5c24=6，所以 v4可以獲得標(biāo)號(hào) (v2,δ4)，其中 δ4 =min{δ2, c23f23} =min{3, 65}=1。 75 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,11) (v1,3) (v1,4) (v2,3) (v4,4) 76 vs vt v4 v2 v3 v1 (15,8) (9,9) (3,3) (5,1) (6,5) (7,7) (10,9) (11,8) (4,4) (0,+∞) (vs,7) (v1,3) (v2,1) (v2,3) (v3,3) （ II）調(diào)整過程 由于 vt的第一個(gè)標(biāo)號(hào)為 v3，得到頂點(diǎn) v3，由 v3的第一個(gè)標(biāo)號(hào)為 v2，得到頂點(diǎn) v2，由 v2的第一個(gè)標(biāo)號(hào)為 v1，得到頂點(diǎn) v1，由 v1的第一個(gè)標(biāo)號(hào)為 vs，得到頂點(diǎn) vs ，由此得到關(guān)于可行流 f的增廣鏈 μ={vs, v1, v2, v3, vt}，其中 (vs,v1),(v2,v3) ,(v3,vt)為前向邊， (v2,v3)為后向邊。 80 vs vt v4 v2 v3 v1 (15,11) (9,9) (3,0) (5,4) (6,5) (7,7) (10,9) (11,11) (4,4) (0,+∞) (vs,4) （ 3）檢查與 vs ， v1相鄰的頂點(diǎn) v2， v3 ， v4 ， 都不滿足標(biāo)號(hào)條件，所以標(biāo)號(hào)過程結(jié)束，這時(shí) vt沒有得到標(biāo)號(hào)，由此可知不存在從 vs到 vt的增廣鏈，所以圖中的可行流就是最大流，其流量 W=fs1+ fs2=11+9=2