圖與網絡分析（graphtheoryandnetworkanalysis）-預覽頁
【正文】 條邊的兩個端點是相同的 ,那么稱為這條邊是環(huán)。 有向完全圖則是指任意兩個頂點之間有且僅有一條有向邊的簡單圖。 以點 v為端點的邊的個數稱為點 v 的度（次），記作 。通常把這種賦權的圖稱為網絡。若鏈中所含的邊均不相同，則稱此鏈為簡單鏈；所含的點均不相同的鏈稱為初等鏈 , 也稱通路。 v1 v2 v3 v4 v5 v6 一個連通的無圈的無向圖叫做樹。 （ 3） 樹 中任意兩個頂點之間，恰有且僅有一條鏈（初等鏈）。圖 G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。 一般設已有 {e1，e2， … ， ek}， 找一條與 {e1， e2， … ， ek}中任何一些邊不構成圈的邊 ek+1， 重復這個過程，直到不能進行為止。 v1 v2 v3 v4 v5 v6 6 5 1 5 7 2 3 4 4 5 v1 v2 v3 v4 v5 v6 1 2 3 4 4 v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 最短路的一般提法為：設 為連通圖，圖中各邊 有權 （ 表示 之間沒有邊）， 為圖中任意兩點，求一條路 ，使它為從 到 的所有路中總權最短。 vi 為剛得到 P標號的點，考慮點 vj， 其中 ，且 vj為 T標號。 v1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 解 （ 1） 首先給 v1以 P標號 ， 給其余所有點 T標號 。 min L(μ)=10 ⑧ P=T=10 由此看到，此方法不僅求出了從 V1 到 V8 的最短路長，同時也求出了從 V1 到 任意一點 的最短路長。 則 v1到 vi的這條路必然也是 v1到 vi的所有路中的最短路 。 解： （ 1） 分析：可行的購置方案 （ 更新計劃 ） 是很多的 ， 如： 1） 每年購置一臺新的 ， 則對應的費用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購置新的 ， 一直用到第五年年底 ， 則總費用為： 11+5+6+8+11+18 = 59 顯然不同的方案對應不同的費用。所以工廠在每年年初都要決定設備是否更新。 對于 D中的每一個弧 （ vi , vj） ∈ E ,都有一個非負數 cij,叫做弧的容量 。 （ 2） 平衡條件： 對于發(fā)點 vs， 有 對于收點 vt ， 有 對于中間點，有 ? ?? ???Evv Evvsjjsjs sjWff),( ),(? ?? ????Evv Evvtjjtjt tjWff),( ),(? ?? ???Evv Evvijjiji ijff),( ),(0可行流中 fij＝ cij 的弧叫做飽和弧， fij＜ cij的弧叫做非飽和弧。 f 是一個可行流 ， 如果滿足： 則稱 為從 vs到 vt 的關于 f 的一條增廣鏈。 截集 中所有弧的容量之和 ，稱為這個截集的容量 ， 記為 。 Evv ij ?),( 0?ijf),( jiv ?? ),m in ( iijj f ?? ?Evv ji ?),( ijij cf ?),( jiv ?? ),m in ( ijijij fc ?? ??調整過程 設 1． 令 2． 去掉所有標號 ， 回到第一步 ， 對可行流重新標號 。當 f * 是最大流時，就是最小費用最大流。 （ 3） 在 L( f (k1) )中 ， 尋求從 vs到 vt的最短路 。 例 求網絡的最小費用最大流，弧旁權是（ 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中 ， 若存在一條道路 ， 經過每邊一次且僅一次 ， 則稱這條路為歐拉道路 。 推論 一個多重連通圖 G有歐拉道路的充分必要條件是 G有且僅有兩個奇點 。 如果存在一個圈 ， 重復邊的總長大于該圈總長的一半時 ， 則將這個圈中的重復邊去掉 ， 再將該圈中原來沒有重復邊的各邊加上重復邊 ， 其它各圈的邊不變 ， 返回步驟 （ 2） 。 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)評公示相關推薦
鄂ICP備17016276號-1