【正文】 ,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é) 最小費(fèi)用最大流問題 定義 已知網(wǎng)絡(luò) G =（ V， E， C， d） ， f是 G上的一個(gè)可行流 ， 為一條從 vs到 vt的增廣鏈 ， 稱為鏈的費(fèi)用 。 ?? ?? ???? ?jiji ddfd )(若 * 是從 vs到 vt的增廣鏈中費(fèi)用最小的增廣鏈，則稱 * 是最小費(fèi)用增廣鏈。 結(jié)論： 如果可行流 f在流量為 W(f )的所有可行流中的費(fèi)用最小，并且 *是關(guān)于 f 的所有增廣鏈中的費(fèi)用最小的增廣鏈，那么沿增廣鏈 *調(diào)整可行流 f， 得到的新可行流 f *也是流量為W(f*)的所有可行流中的最小費(fèi)用流。當(dāng) f * 是最大流時(shí)，就是最小費(fèi)用最大流。 ????尋找關(guān)于 f 的最小費(fèi)用增廣鏈： 構(gòu)造一個(gè)關(guān)于 f 的賦權(quán)有向圖 L(f ) ，其頂點(diǎn)是原網(wǎng)絡(luò) G的頂點(diǎn)，而將 G中的每一條弧 ( vi, vj )變成兩個(gè)相反方向的?。?vi， vj） 和 (vj , vi)， 并且定義圖中弧的權(quán) lij為： ， 令 （ vj， vi） 為原來網(wǎng)絡(luò) G中（ vi， vj） 的反向弧，令 在網(wǎng)絡(luò) G中尋找關(guān)于 f 的最小費(fèi)用增廣鏈等價(jià)于在 L(f )中尋求從 vs 到 vt 的最短路。 ??????????jijijijijiji cfcfdl當(dāng)當(dāng)???????????00jijijiij ffdl當(dāng)當(dāng)Evv ji ?),(步驟： （ 1）取零流為初始可行流 ， f (0) ={0}。 （ 2） 一般地 ， 如果在第 k1步得到最小費(fèi)用流 f (k1)，則構(gòu)造圖 L( f (k1) )。 （ 3） 在 L( f (k1) )中 ， 尋求從 vs到 vt的最短路 。 若不存在最短路 ， 則 f (k1)就是最小費(fèi)用最大流；否則轉(zhuǎn) (4)。 （ 4） 如果存在最短路 ， 則在可行流 f (k－ 1)的圖中得到與此最短路相對(duì)應(yīng)的增廣鏈 ， 在增廣鏈上 ， 對(duì) f (k－ 1)進(jìn)行調(diào)整 ， 調(diào)整量為： ?????? ?? ???? )(m i n,)(m i nm i n)1()1( kjikjiji ffc ??????????????????????????),(),(),()1()1()1()(jikjijikjijikjikjivvfvvfvvff令 得到新可行流 f (k) 。對(duì) f (k)重復(fù)上面步驟，返回（ 2）。 例 求網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁權(quán)是（ 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é) 中國(guó)郵遞員問題 一 、 歐拉回路與道路 定義 連通圖 G中 ， 若存在一條道路 ， 經(jīng)過每邊一次且僅一次 ， 則稱這條路為歐拉道路 。 若存在一條回路 ， 經(jīng)過每邊一次且僅一次 ， 則稱這條回路為歐拉回路 。 具有歐拉回路的圖稱為歐拉圖 。 定理 一個(gè)多重連通圖 G是歐拉圖的充分必要條件是 G中無奇點(diǎn) 。 推論 一個(gè)多重連通圖 G有歐拉道路的充分必要條件是 G有且僅有兩個(gè)奇點(diǎn) 。 A B C D 二、 奇偶點(diǎn)圖上作業(yè)法 （ 1） 找出圖 G中的所有的奇頂點(diǎn) ， 把它們兩兩配成對(duì) ， 而每對(duì)奇點(diǎn)之間必有一條通路 ， 把這條通路上的所有邊作為重復(fù)邊追加到圖中去 ， 這樣得到的新連通圖必?zé)o奇點(diǎn) 。 （ 2） 如果邊 e=（ u,v） 上的重復(fù)邊多于一條 ， 則可從重復(fù)邊中去掉偶數(shù)條 ， 使得其重復(fù)邊至多為一條 ， 圖中的頂點(diǎn)仍全部都是偶頂點(diǎn) 。 （ 3） 檢查圖中的每一個(gè)圈 ， 如果每一個(gè)圈的重復(fù)邊的總長(zhǎng)不大于該圈總長(zhǎng)的一半 ， 則已經(jīng)求得最優(yōu)方案 。 如果存在一個(gè)圈 ， 重復(fù)邊的總長(zhǎng)大于該圈總長(zhǎng)的一半時(shí) ， 則將這個(gè)圈中的重復(fù)邊去掉 ， 再將該圈中原來沒有重復(fù)邊的各邊加上重復(fù)邊 ， 其它各圈的邊不變 ， 返回步驟 （ 2） 。 判定標(biāo)準(zhǔn) 1: 在最優(yōu)郵遞路線上 ， 圖中的每一條邊至多有一條重復(fù)邊 。 判定標(biāo)準(zhǔn) 2 : 在最優(yōu)郵遞路線上 ， 圖中每一個(gè)圈的重復(fù)邊總權(quán)小于或等于該圈總權(quán)的一半 。 例 求解下圖所示網(wǎng)絡(luò)的中國(guó)郵路問題，圖中數(shù)字為該邊的長(zhǎng)。 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