【正文】 例 求解下圖所示網(wǎng)絡(luò)的中國郵路問題，圖中數(shù)字為該邊的長。 判定標準 1: 在最優(yōu)郵遞路線上 ， 圖中的每一條邊至多有一條重復(fù)邊 。 （ 3） 檢查圖中的每一個圈 ， 如果每一個圈的重復(fù)邊的總長不大于該圈總長的一半 ， 則已經(jīng)求得最優(yōu)方案 。 A B C D 二、 奇偶點圖上作業(yè)法 （ 1） 找出圖 G中的所有的奇頂點 ， 把它們兩兩配成對 ， 而每對奇點之間必有一條通路 ， 把這條通路上的所有邊作為重復(fù)邊追加到圖中去 ， 這樣得到的新連通圖必無奇點 。 定理 一個多重連通圖 G是歐拉圖的充分必要條件是 G中無奇點 。 若存在一條回路 ， 經(jīng)過每邊一次且僅一次 ， 則稱這條回路為歐拉回路 。對 f (k)重復(fù)上面步驟，返回（ 2）。 若不存在最短路 ， 則 f (k1)就是最小費用最大流；否則轉(zhuǎn) (4)。 （ 2） 一般地 ， 如果在第 k1步得到最小費用流 f (k1)，則構(gòu)造圖 L( f (k1) )。 ????尋找關(guān)于 f 的最小費用增廣鏈： 構(gòu)造一個關(guān)于 f 的賦權(quán)有向圖 L(f ) ，其頂點是原網(wǎng)絡(luò) G的頂點，而將 G中的每一條弧 ( vi, vj )變成兩個相反方向的?。?vi， vj） 和 (vj , vi)， 并且定義圖中弧的權(quán) lij為： ， 令 （ vj， vi） 為原來網(wǎng)絡(luò) G中（ vi， vj） 的反向弧，令 在網(wǎng)絡(luò) G中尋找關(guān)于 f 的最小費用增廣鏈等價于在 L(f )中尋求從 vs 到 vt 的最短路。 結(jié)論： 如果可行流 f在流量為 W(f )的所有可行流中的費用最小，并且 *是關(guān)于 f 的所有增廣鏈中的費用最小的增廣鏈，那么沿增廣鏈 *調(diào)整可行流 f， 得到的新可行流 f *也是流量為W(f*)的所有可行流中的最小費用流。 }),(mi n {1 ???? ?? jijiji vvfc}),(mi n {2 ??? ?? jiji vvf),m in ( 21 ??? ??????????????? ???????),(),(),(jijijijijijijivvfvvfvvff 求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為 ),( jiji fc(1 ,1) v2 v1 v4 v3 vs vt (3 , 3) (5 , 1) (1 , 1) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,1) (1 ,1) v2 v1 v4 v3 vs vt (3 , 3) (5 , 1) (1 , 1) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,1) （ 0， +∞） （ v1, 1） （ + vs , 4） （ v2 ， 1） （ +v2， 1） (+ v3 ， 1) (1 ,0) v2 v1 v4 v3 vs vt (3 , 3) (5 , 2) (1 , 0) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,2) (1 ,0) v2 v1 v4 v3 vs vt (3 , 3) (5 , 2) (1 , 0) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,2) （ 0， +∞） （ + vs , 3） )},(,),{( 4321 ts vvvvvv最小截集 2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 2v1v3v4v5v6v7v 13 (11) 9 (9) 4 (0) 5 (5) 6(6) 5 (5) 5 (4) 5 (4) 4 (4) 4 (3) 9 (9) 10 (7) 截集 1 截集 2 最小截量為： 9+6+5=20 1sv2v2sv1v1tv2tv3v70（ 70） 70（ 50） 130（ 100） 150（ 130） 150（ 150） 50（ 20） 50（ 50） 120（ 30） 100（ 100） svtv∞ （ 120 ） ∞ （ 230 ） ∞ （ 150 ） ∞ （ 200 ） 第五節(jié) 最小費用最大流問題 定義 已知網(wǎng)絡(luò) G =（ V， E， C， d） ， f是G上的一個可行流 ， 為一條從 vs到 vt的增廣鏈 ， 稱為鏈的費用 。 若 vt被標號 ， 則存在一條增廣鏈 ， 轉(zhuǎn)調(diào)整過程；若 vt未被標號 ， 而標號過程無法進行下去 ， 這時的可行流就是最大流 。 SS, SvSv ts ?? ,S),( SS ),( SS),( SSCvs v1 v2 v4 v3 vt 3 7 4 5 5 6 3 7 8 S ),( 2vvS s? ),( 431 tvvvvS ?? ?),(,),(,),(),( 32421 vvvvvvSS s?18567),( 23241 ??????? lllSSC s2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) ? ?),(),(),(),( 75423121 vvvvvvVV ?設(shè) ， ? ?5211 , vvvV ?則截集為 ? ?76432 , vvvvV ?不是該集中的弧和而 ),( ),( 5423 vvvv容量為 24 2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 設(shè) ， ? ?211 , vvV ?? 則截集為 ? ?765432 , vvvvvV ??? ?),(),(),(),( 52423121 vvvvvvVV ???容量為 20 （ 二 ） 、 求最大流的標號法 標號過程： 1． 給發(fā)點 vs 標號（ 0， +∞）。 如果把 V分成兩個非空集合 使 ， 則所有始點屬于 S， 而終點屬于 的弧的集合 ， 稱為由 S決定的截集 ,記作 。 ?? ? ???? ?????????????????),(0),(0jijijijijijivvcfvvcf?推論 可行流 f 是最大流的充分必要條件是不存在從 vs到 vt 的關(guān)于 f 的一條可增廣鏈。 ) , ( 63 vv 容量網(wǎng)絡(luò) G， 若 為網(wǎng)絡(luò)中從 vs到 vt的一條鏈 ， 給 定向為從 vs到 vt， 上的弧凡與 方向相同的稱為前向弧 ， 凡與 方向相反的稱為后向弧 ， 其集合分別用 和 表示 。 fij＞ 0 的弧為非零流弧，fij＝ 0 的弧叫做零流弧。 ? ? }{),( jiji fvvff ??稱滿足下列條件的流為可行流： （ 1）容量條件：對于每一個?。?vi ,vj） ∈ E 有 0 ? fij ? cij 。 我們把這樣的圖 D叫做一個容量網(wǎng)絡(luò) ， 簡稱網(wǎng)絡(luò) ， 記做 D=（ V， E， C） 。 年份 1 2 3 4 5 購置費 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費 5 7 12 18 25 年份 1 2 3 4 5 購置費 18 20 21 23 24 使用年數(shù) 0~1 1~2 2~3 3~4 4~5 維修費 5 7 12 18 25 28 v1 v2 v3 v4 v5 v6 23 25 26 29 30 42 60 85 32 44 62 33 45 30 四、 最大流問題 （ 一 ）