圖與網(wǎng)絡分析ppt課件-資料下載頁
2025-01-14 12:34本頁面
【正文】 ???????????00jijijiij ffdl當當Evv ji ?),(步驟： （ 1）取零流為初始可行流 ， f (0) ={0}。 （ 2） 一般地 ， 如果在第 k1步得到最小費用流 f (k1)，則構造圖 L( f (k1) )。 （ 3） 在 L( f (k1) )中 ， 尋求從 vs到 vt的最短路 。 若不存在最短路 ， 則 f (k1)就是最小費用最大流；否則轉 (4)。 （ 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) 。對 f (k)重復上面步驟，返回（ 2）。 例 求網(wǎng)絡的最小費用最大流，弧旁權是（ 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 課堂練習： 表 1給出某運輸問題的產(chǎn)銷平衡表與單位運價表。將此問題轉化為最小費用最大流問題，畫出網(wǎng)絡圖并求解數(shù)值解。 銷地 產(chǎn)地 1 2 3 產(chǎn)量 A 20 24 5 8 B 30 22 20 7 銷量 4 5 6 表 1： 中國郵遞員問題 連通圖 G中 ， 若存在一條道路 ， 經(jīng)過每邊一次且僅一次 ， 則稱這條路為歐拉道路 。 若存在一條回路 ， 經(jīng)過每邊一次且僅一次 ， 則稱這條回路為 歐拉回路 。 具有歐拉回路的圖稱為 歐拉圖 。 定理 一個多重連通圖 G是歐拉圖的充分必要條件是 G中無奇點 。 推論 一個多重連通圖 G有歐拉道路的充分必要條件是 G有且僅有兩個奇點 。 歐拉圖 A B C D 奇偶點圖上作業(yè)法 （ 1） 找出圖 G中的所有的奇頂點 ， 把它們兩兩配成對 ，而每對奇點之間必有一條通路 ， 把這條通路上的所有邊作為重復邊追加到圖中去 ， 這樣得到的新連通圖必無奇點 。 （ 2） 如果邊 e=（ u,v） 上的重復邊多于一條 ， 則可從重復邊中去掉偶數(shù)條 ， 使得其 重復邊至多為一條 ， 圖中的頂點仍全部都是偶頂點 。 （ 3） 檢查圖中的每一個圈 ， 如果 每一個圈的重復邊的總長不大于該圈總長的一半 ， 則已經(jīng)求得最優(yōu)方案 。 如果存在一個圈 ， 重復邊的總長大于該圈總長的一半時 ， 則將這個圈中的重復邊去掉 ， 再將該圈中原來沒有重復邊的各邊加上重復邊 ， 其它各圈的邊不變 ， 返回步驟 （ 2） 。 判定標準 1: 在最優(yōu)郵遞路線上 ， 圖中的每一條邊至多有一條重復邊 。 判定標準 2 : 在最優(yōu)郵遞路線上 ， 圖中每一個圈的重復邊總權小于或等于該圈總權的一半 。 例 求解下圖所示網(wǎng)絡的中國郵路問題，圖中數(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+ 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 課堂作業(yè)： P283
教學課件相關推薦
鄂ICP備17016276號-1