行遍性問題-最佳災情巡視路線第9講行遍性

1、 數(shù)學建模與數(shù)學實驗行遍性問題行遍性問 題一、中 國 郵 遞 員 問 題 圖（一）（二） 中 國 郵 遞 員 問 問 題二、 圖（一） 問 題（二）三、建模案例：最佳災情巡視路線題定義 設圖 G =（V，E）， M E，若 M則稱 M 是 G 的一個匹配.的邊互不相鄰，若頂點 v 與 M 的一條邊關聯(lián)，則稱 v 是 M飽和的設 M 是 G 的一個匹配，若 G 的每個頂點都是 M飽和的，則稱 M 是 G 的理想匹配.割邊的定義：設G連通，eE(G),若從G中刪除邊e后，圖G-e不連通，則稱邊e為圖G的割邊e1v1v2e2V5割邊e4e8e7e6vV64ve9V73G的邊e是割邊的充要條件是e不含

2、在G的圈中e5e3圖定義 設 G=(V,E)是連通無向圖（）經(jīng)過 G 的每邊至少一次的閉通路稱為巡回（）經(jīng)過 G 的每邊正好一次的巡回稱為巡回（）存在巡回的圖稱為圖（）經(jīng)過 G 的每邊正好一次的道路稱為道路e1v1e1v2e2v1v2e2e4e4vv44vv33道路：v1e1v2e2v3e5v1e4v4e3v3巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e6e5 e3e5e3定理 對于非空連通圖 G，下列命題等價：（）G 是圖（）G 無奇次頂點（）G 的邊集能劃分為圈e1v1e1v2e2v1v2e2e4e4vv44vv33

3、圖非圖道路的充要條設 G 是非平凡連通圖，則 G 有推論件是 G 最多只有兩個奇次頂點中國郵遞員問題-定義郵遞員發(fā)送郵件時，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行郵遞員問題.程最短的路線這就若將投遞區(qū)的街道用邊表示，街道的長度用邊權表示，郵局街道交叉口用點表示，則一個投遞區(qū)一個賦權連通無向圖中國郵遞員問題轉化為：在一個非負連通圖中，尋求一個權最小的巡回這樣的巡回稱為最佳巡回中國郵遞員問題-算法圖1、G 是G此時的任何一個巡回便是最佳巡回問題歸結巡回為在圖中確定一個Fleury 算法：求圖的巡回Fleury算法-基本：從任一點出發(fā)，每當一條邊時，先

4、要進行檢查如果可供的邊不只一條，則應選一條不是未的邊集的導出子圖的邊，直到?jīng)]有邊可選擇為止.割邊作為Fleu ry 算法 算法步驟 ：（）任選一個頂點 v 0 ，令道路 w 0 =v 0（）假定道路 wi=v 0 e 1 v 1 e 2 eivi 已經(jīng)選好，則從 Ee 1 ,e 2 , ,ei中選 一條邊 ei+ 1 ，使： a） ei+1與 vi 相關聯(lián) b） 除非不能選擇，否則一定要使的割邊 ei+1不是 G i=G E-e 1,e 2, ,ei（）第（ ）步不能進行時就停止 e1v1v2e2e10V5e4e8e7e6vV64ve9V732、G 不是圖若G不是圖，則G的任何一個巡回經(jīng)過某些

5、邊必定多于一次解決這類問題的一般方法是，在一些點對之間引入重復邊（重復邊與它平行的邊具有相同的權），使原圖成為圖，但希望所有添加的重復邊的權的總和為最小情形 G 正好有兩個奇次頂點（）用 Dijkstra 算法求出奇次頂點 u 與 v 之間的最短路徑 P（）令 G*=G P，則 G*為（）用 Fleury 算法求出 G*的圖巡回，這就是 G 的最佳巡回e1v1v2V5e4e2e8e7e6vV64ve9V73情形 G 有n 個奇次頂點（n ）Edmonds 最小對集算法：基本先將奇次頂點配對，要求最佳配對，即點對之間距離總和圖 G*，G*最小再沿點對之間的最短路徑添加重復邊得的巡回便是原圖的最佳

6、巡回算法步驟：（）用 Floyd 算法求出的所有奇次頂點之間的最短路徑和距離G（）以的所有奇次頂點為頂點集（個數(shù)為偶數(shù)），作一完備圖，邊上的權為兩端點在原圖 G 中的最短距離，將此完備圖記為 G1（）求出G1的最小權理想匹配M，得到奇次頂點的最佳配對圖 G*（）在 G 中沿配對頂點之間的最短路徑添加重復邊得（）用 Fleury 算法求出 G*的巡回，這就是 G 的最佳巡回例 求右圖所示投遞區(qū)的一條最佳郵遞路線1圖中有 v4、v7、v8、v9 四個奇次頂點用dyo Fl 算法求出它們之間的最短路徑和距：離4v4d,7v)v5Pv 4 vv73v8,2 v(7,d4,v8 vv) vP PP PP

7、4,v 4v7,v7,v8,v( d3v 6963v 448v v9) ) v8,v(vv9,49v8 v v9 vv9 v( d( d( dvv 7878v) vv 7979v) vv 8989以 v4、v7、v8、v9 為頂點，它們之間的距離為邊權構造完備圖 G1求出 G1 的最小權完美匹配 M=(v4,v7(),v8,v9)在 G 中沿 v4 到 v7 的最短路徑添加重復邊，沿 v8 到 v9 的最短路徑 v8v9 添圖 G2G2 中一條歐拉巡回就是 G 的一條最佳巡回其加重復邊，得權值為圖定義 設 G=(V,E)是連通無向圖（）經(jīng)過 G 的每個頂點正好一次的路徑，稱為 G 的一條路徑（

8、）經(jīng)過 G 的每個頂點正好一次的圈，稱為 G 的哈密爾頓圈或 H 圈（）含 H 圈的圖稱為圖或 H 圖問題-定義需要某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點問如何安排旅行路線使總行程最小這就是問題若用頂點表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權表示距離（或時間、費用），于是問題就成為在圖中尋找一條經(jīng)過每個頂點至少一次的最短閉通路問題圖G=(V,E)中，定義在（）權最小的圈稱為最佳H圈（）經(jīng)過每個頂點至少一次的權最小的閉通路稱為最佳回路一般說來，最佳路，同樣最佳圈不一定是最佳回路也不一定是最佳回圈H回路，長22回路，長4最佳圖G=(V,E)中，若對任意 x,y,zV，z x,z y,都定理在有 w(x,y) w(x,z)+w(z,y)，則圖 G 的最佳 H 圈也是最佳回路回路問題可轉化為最佳 H 圈問題方法是由給最佳定的圖 G=(V,E)構造一個以V為頂點集的完備圖 G=(V,E)，E的每條邊(x,y)的權等于頂點 x 與 y 在圖中最短路的權即： x,y E,w(x,y)=mindG(x,y)圖 G 的最佳回路的權與 G的最佳 H 圈的權相同定理問題近似算法：二邊逐次修（）任取初始 H 圈: C0=v1,v2,vi, ,vj,vn,v1：（）對所有的 i ,j，1i+1jn,若w(vi, vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)則在 C0 中刪去邊(vi