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