【正文】 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 6 4 3 4 5 5 l12+2 l23+2 l36+2 l89+2 l78+l69+l14+2 l47=51 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 。 判定標準 2 : 在最優(yōu)郵遞路線上 ， 圖中每一個圈的重復邊總權小于或等于該圈總權的一半 。 如果存在一個圈 ， 重復邊的總長大于該圈總長的一半時 ， 則將這個圈中的重復邊去掉 ， 再將該圈中原來沒有重復邊的各邊加上重復邊 ， 其它各圈的邊不變 ， 返回步驟 （ 2） 。 （ 2） 如果邊 e=（ u,v） 上的重復邊多于一條 ， 則可從重復邊中去掉偶數條 ， 使得其重復邊至多為一條 ， 圖中的頂點仍全部都是偶頂點 。 推論 一個多重連通圖 G有歐拉道路的充分必要條件是 G有且僅有兩個奇點 。 具有歐拉回路的圖稱為歐拉圖 。 例 求網絡的最小費用最大流，弧旁權是（ bij , cij） (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 3 vs v2 v1 vt v3 1 6 4 1 2 2 (1) L(f (0)) (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 0 vs v2 v1 vt v3 3 0 0 3 3 3 (2) f ( 1) ?1=3 W(f(1))=3 － 1 (3) L(f (1)) － 2 3 vs v2 v1 vt v3 1 6 4 1 2 － 1 － 2 1 vs v2 v1 vt v3 4 0 0 3 4 3 (4 ) f ( 2) ?2=1 W(f(2))=4 (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) (5) L(f (2)) － 3 vs v2 v1 vt v3 － 1 4 1 2 － 2 － 2 3 － 1 6 6 1 vs v2 v1 vt v3 4 0 1 4 5 3 (6 ) f ( 3) ?3=1 W(f(3))=5 (7) L(f (3)) vs v2 v1 vt v3 － 3 － 1 4 1 2 － 2 3 － 1 6 1 vs v2 v1 vt v3 4 3 4 4 5 0 (8 ) f ( 4) ?4=3 W(f(4))=8 0 vs v2 v1 vt v3 4 4 5 5 5 0 ?5=1 W(f(5))=9 (10 )f ( 5) － 1 2 3 － 1 vs v2 v1 vt v3 － 3 4 1 2 6 (9) L( f ( 4)) 4 6 3 － 1 2 － 1 4 (11) L( f ( 5)) 1 2 6 － 4 vs v2 v1 vt v3 － 6 第六節(jié) 中國郵遞員問題 一 、 歐拉回路與道路 定義 連通圖 G中 ， 若存在一條道路 ， 經過每邊一次且僅一次 ， 則稱這條路為歐拉道路 。 （ 4） 如果存在最短路 ， 則在可行流 f (k－ 1)的圖中得到與此最短路相對應的增廣鏈 ， 在增廣鏈上 ， 對 f (k－ 1)進行調整 ， 調整量為： ?????? ?? ???? )(m i n,)(m i nm i n)1()1( kjikjiji ffc ??????????????????????????),(),(),()1()1()1()(jikjijikjijikjikjivvfvvfvvff令 得到新可行流 f (k) 。 （ 3） 在 L( f (k1) )中 ， 尋求從 vs到 vt的最短路 。 ??????????jijijijijiji cfcfdl當當???????????00jijijiij ffdl當當Evv ji ?),(步驟： （ 1）取零流為初始可行流 ， f (0) ={0}。當 f * 是最大流時，就是最小費用最大流。 ?? ?? ???? ?jiji ddfd )(若 * 是從 vs到 vt的增廣鏈中費用最小的增廣鏈，則稱 * 是最小費用增廣鏈。 Evv ij ?),( 0?ijf),( jiv ?? ),m i n ( iijj f ?? ?Evv ji ?),( ijij cf ?),( jiv ?? ),m i n ( ijijij fc ?? ??調整過程 設 1． 令 2． 去掉所有標號 ， 回到第一步 ， 對可行流重新標號 。 2． 取一個已標號的點 vi， 對于 vi一切未標號的鄰接點 vj 按下列規(guī)則處理： （ 1）如果邊 ，且 ，那么給 vj 標號 ，其中： （ 2） 如果邊 ， 且 ， 那么給 vj 標號 ， 其中： 3． 重復步驟 2， 直到 vt被標號或標號過程無法進行下去 ， 則標號結束 。 截集 中所有弧的容量之和 ，稱為這個截集的容量 ， 記為 。 即 中的每一條弧都是非飽和弧 ??即 中的每一條弧都是非零流弧 ??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) ? ?7766633232211 ),(,),(,),(,),(, vvvvvvvvvvvvv??? ?),(),(),( 766321 vvvvvv??? ? ?),( 23 vv????是一個增廣鏈 顯然圖中增廣鏈不止一條 容量網絡 G =（ V， E， C） ， vs為始點 ，vt為終點 。 f 是一個可行流 ， 如果滿足： 則稱 為從 vs到 vt 的關于 f 的一條增廣鏈。 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) 圖中 為零流弧，其余為非飽和弧。 （ 2） 平衡條件： 對于發(fā)點 vs， 有 對于收點 vt ， 有 對于中間點，有 ? ?? ???Evv Evvsjjsjs sjWff),( ),(? ?? ????Evv Evvtjjtjt tjWff),( ),(? ?? ???Evv Evvijjiji ijff),( ),(0可行流中 fij＝ cij 的弧叫做飽和弧， fij＜ cij的弧叫做非飽和弧。 網絡 D上的流，是指定義在弧集合 E上的一個函數 其中 f(vi ,vj) =fij 叫做弧 (vi， vj)上的流量。 對于 D中的每一個弧 （ vi , vj） ∈ E ,都有一個非負數 cij,叫做弧的容量 。計劃期（五年）內中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內的總費用最小。所以工廠在每年年初都要決定設備是否更新。 求解步驟： 1） 畫賦權有向圖： 設 Vi 表示第 i年初 ， (Vi ,Vj )表示第 i 年初購買新設備用到第 j年初 （ j1年底 ） ， 而 Wi j 表示相應費用 ，