運籌學(xué)_圖與網(wǎng)絡(luò)分析(編輯修改稿)
2025-06-19 22:15 本頁面
【文章內(nèi)容簡介】 沒有奇點時圖中含有歐拉圈，即沒有奇點的連通圖必含有歐拉圈。 v1 v2 v3 v4 v5 v6 E={v5， v2， v1， v3， v2， v4， v3， v5， v4， v6， v5} 對于不含奇點的連通圖，中國郵路問題就是要找圖中的歐拉圈。 v1 v2 v3 v4 v5 v6 含有奇點的連通圖中不含歐拉圈，此時，最優(yōu)的郵遞路線是什么呢？ 求解中國郵路問題的 奇偶點圖上作業(yè)法 ?奇偶點表上作業(yè)法 (1)找出奇點 (一定為偶數(shù)個 )， 在每兩個奇點之間找一條鏈 ， 在這些鏈經(jīng)過的所有邊上增加一條邊 ， 這樣所有的奇點變?yōu)榕键c ， 一定存在歐拉圈 ， 但是不一定是路線最短的 ， 所以需要檢驗和調(diào)整 。 (2)檢驗增加的邊的權(quán)值是否是最小的 。 定理 3 假設(shè) M是使得圖 G中不含奇點的所有增加邊 ， 則 M是權(quán)值總和為最小的增加邊的充分必要條件是： 1)圖 G中每條邊上最多增加一條邊； 2)在圖 G的每個圈上 ， 增加的邊的總權(quán)值不超過該圈總權(quán)值的一半 。 如果上述兩個條件都滿足則已經(jīng)找到權(quán)值最小的歐拉圈 否則轉(zhuǎn)入 3) 3)調(diào)整增加邊 。 如果 1)不滿足 ， 則從該條邊的增加邊中去掉 偶數(shù)條 ； 如果 2)不滿足 ， 則將這個圈上的增加邊去掉 ， 將該圈的其余邊上添加增 加邊 ， 轉(zhuǎn)入 (2) v1 v2 v3 v4 v5 v6 3 4 2 3 3 2 4 3 5 v1 v2 v3 v4 v5 v6 3 4 2 3 3 2 4 3 5 v1 v2 v3 v4 v5 v6 3 4 2 3 3 2 4 3 5 v1 v2 v3 v4 v5 v6 3 4 2 3 3 2 4 3 5 {v1， v6， v5， v4， v6， v2， v6， v3， v4，v3， v2， v1} 不滿足定理 3條件 網(wǎng)絡(luò) 對有向圖 D=(V,A)， 如果對于有向圖 D中的每一條弧(vi,vj) ∈ A， 都有一個數(shù) w(vi,vj) 與它對應(yīng) ， 此時稱 D為一個網(wǎng)絡(luò) ， 或稱賦權(quán)有向圖 。 有向網(wǎng)絡(luò)： 網(wǎng)絡(luò)中每個邊都是有向邊； 無向網(wǎng)絡(luò)： 網(wǎng)絡(luò)中每個邊都是無向邊； 混合網(wǎng)絡(luò)： 網(wǎng)絡(luò)中既有有向邊 ， 又有無向邊； 網(wǎng)絡(luò)最短路線問題： 尋找網(wǎng)絡(luò)中從起點 v1 到終點 vn 的最短路線 。 網(wǎng) 絡(luò) 最 短 路 問 題 1632611 04103246322V 1V 2V 4V 3V 5V 6V7V 8V 9?一般的最短路問題描述： 給定一個賦權(quán)有向圖 D=(V,A)， 對每一個弧 a=(vi,vj)， 相應(yīng)地有權(quán) w(a)=wij，又給定 D中的任何兩個頂點 vs和 vt ， 設(shè) P是從 vs到 vt的路 ， 定義路 P的權(quán)是 P中所有弧之和 ， 記為 w(P)， 最短路問題就是要在所有從 vs到 vt的路中 ， 求一條權(quán)最小的路 ， 即一條從 vs到 vt的路 P0使得： 0 P( P ) m i n ( P )ww?路 P0的權(quán)稱為從 vs到 vt的距離，記為 d(vs,vt)。 有向圖權(quán)值非負(fù) Dijkstra算法 Dijkstra算法的基本步驟 (權(quán)值非負(fù) ) v1標(biāo)號 (0)， v1稱為已標(biāo)號點，記標(biāo)號點集為 V1={v1} V2中找出與標(biāo)號點集 V1中的頂點 vi有弧相連 (并且以 vi為起點 )的點 vj， 2步選出的點中，選出滿足下面條件的點 vk，并給 vk標(biāo)號 (l,L1k)，其中 l為第一標(biāo)號， L1k為第二標(biāo)號 ? ?1 1 1 1 2m ink l l k i i j i jL L w L w v V , v V? ? ? ? ? ?為從 v1到 vk的最短路的長度， l表示在從 v1到 vk的最短路上，與 vk相鄰的點是 vl 4. 若最后一個頂點 vn未標(biāo)號，則轉(zhuǎn)回第 2步；若 vn已標(biāo)號，則從 vn開始，按照第一個標(biāo)號逆向追蹤，直到 v1，就得到從 v1到 vn的最短路， vn的第二個標(biāo)號表示最短路的長度。 求從 v1到 v8的最短路 1632611 04103246322V 1V 2V 4V 3V 5V 6V7V 8V 9(0) (1,1) (1,3) (3,5) (2,6) (5,10) (5,9) (5,12) 注： 在給頂點編號時，如果在多個為標(biāo)號點均取得最小值 Llk則對這多個點同時標(biāo)號，這些點的第二個標(biāo)號相同，但是第一個標(biāo)號不一定相同。 課堂練習(xí)： P225 6. a) 和 b) ? 有向圖某些權(quán)值為負(fù) 1. 先對圖中各個點按照 Dijkstra算法標(biāo)號 ， 稱之為第一次標(biāo)號 ， 令 m=1， 轉(zhuǎn)入第二步； 2. 對圖中除了 v1以外的所有點進(jìn)行 m+1次標(biāo)號 ， 記 L1k(m+1)為對頂點 vk的第 m+1次標(biāo)號的第二個標(biāo)號值 ， 計算公式如下： ? ?( 1 ) ( )11 m in ( , )mmk i ik i kL L w v v i k? ? ? ?存 在 弧 ， 包 括 L1k(m)= L1
法律信息相關(guān)推薦
鄂ICP備17016276號-1