圖論旅行商ppt課件-資料下載頁
2025-05-06 23:19本頁面
【正文】 Dijkstra算法的過程。（求 min 改為求 max） 26 中國郵路問題 例 某郵遞員負(fù)責(zé)在若干街道投遞郵件?，F(xiàn)從郵局出發(fā)，經(jīng)過每一條街道最后返郵局，問如何行走，使得投遞線路最短。這就是“中國郵路”問題。 中國郵路問題 : 設(shè) G是一個連通的正權(quán)簡單 圖，問如何在 G中添加重復(fù)邊，使 G有歐拉回路，且重復(fù)邊的總長最小。 27 2. 算法 定理 設(shè) G是無向連通圖，適當(dāng)加邊使 G存在最佳郵路的充要條件是 : (1) G中每條邊最多加重復(fù)邊一條 。 (2) 在 G的任意一個回路上 ,重復(fù)邊的長度之和不超過該回路長度的一半 . 證： 必要性 . 若某邊的重復(fù)邊至少有兩條，則去掉其中兩條后各結(jié)點仍然為偶點，故仍然存在 Euler回路 。 28 若 G的某回路 C上所加重復(fù)邊的長度之和超過了該回路長度的一半，則重新刪增重復(fù)邊： 將 C中原有重復(fù)邊全部刪除，而對 C中原來沒有重復(fù)邊的邊，每邊增加一條重復(fù)邊 。 這樣，各點度數(shù)為偶的性質(zhì)不變，故仍含 Euler回路，且總路長下降，矛盾。 充分性 . (略 ) 29 算法 (1) 適當(dāng)加邊，使所有結(jié)點成為偶點 (度數(shù)為偶數(shù)的點 )，并且每邊的重復(fù)邊不超過一條。 (2) 檢查每個回路，若回路中重復(fù)邊長之和大于整個回路長的一半，則在該回路上作邊的刪增：使重復(fù)邊不重復(fù)，使不重復(fù)邊重復(fù)。 若所有回路都滿足要求 (重復(fù)邊長之和不大于整個回路長的一半 ), 則終止迭代。 例 () 30 3. 有向圖的中國郵路問題 對于有向圖來說 , 中國郵路問題可能無解。其原因是 G中可能含有出度 (正度 )或入度 (負(fù)度 )為 0的結(jié)點，可能進(jìn)得去出不來或出得去回不來。 如果各結(jié)點的正、負(fù)度相等，則 G中存在有向 Euler回路。它經(jīng)過每邊一次且僅一次，因此任一條 Euler回路都是中國郵路。 以下通過一個例，介紹它的求解方法。 31 v1 v2 v3 v4 v5 8 5 1 2 3 2 5 7 (1)添加總發(fā)點vs總收點 vt，求 vs到 vt的 2條有向最短路，將它們添加到原圖中去。 例 求有向圖的中國郵路問題。 vs vt v1 v2 v3 v4 v5 8 5 1 2 3 2 5 7 0 0 0 0 32 (2)求 vs到 vt的一條有向最短路，將它們添加到原圖中去 , 去掉首尾的邊。 vs 0 vt v1 v2 v3 v4 v5 8 5 1 2 3 2 5 7 0 5 (3)求 vs到 vt的最后一條有向最短路，將它們添加到原圖中去 , 去掉首尾的邊。 v1 v2 v3 v4 v5 8 5 1 2 3 2 5 7 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1