第三節(jié)Euler圖和Hamilton圖應(yīng)用

1、第三節(jié)Euler圖和Hamilton圖應(yīng)用1111112111222222332 中國郵遞員問題是由我國的管梅谷教授中國郵遞員問題是由我國的管梅谷教授在在1960年首先提出的。年首先提出的。 用圖論的語言用圖論的語言, 這一問題可表述為這一問題可表述為: 在一在一個賦權(quán)連通無向圖個賦權(quán)連通無向圖G中，求一個權(quán)和最中，求一個權(quán)和最小的包含每條邊至少一次的閉通路。這小的包含每條邊至少一次的閉通路。這樣的閉通路簡稱為最佳郵路。樣的閉通路簡稱為最佳郵路。 若若G是歐拉圖，那么每一條歐拉閉跡即為一是歐拉圖，那么每一條歐拉閉跡即為一條最佳郵路。條最佳郵路。 易證可以用加重邊的方法使任何連通圖易證可以用加重

2、邊的方法使任何連通圖G轉(zhuǎn)轉(zhuǎn)變成歐拉圖變成歐拉圖 若不是歐拉圖，則在每條郵路中必有邊重復(fù)。若不是歐拉圖，則在每條郵路中必有邊重復(fù)。在在G中將邊中將邊e用用k條重邊代替且每一邊都賦權(quán)條重邊代替且每一邊都賦權(quán)W(e)，這樣的過程稱為加重邊。，這樣的過程稱為加重邊。 求最佳郵路的問題可轉(zhuǎn)化為下列兩個問題求最佳郵路的問題可轉(zhuǎn)化為下列兩個問題: 第第2個問題可用弗勞瑞算法解決。個問題可用弗勞瑞算法解決。 對于第對于第1個問題埃德蒙斯個問題埃德蒙斯(J.Edmonds)和和約翰遜約翰遜(L.Johnson)于于1973年給出了一個年給出了一個有效算法。有效算法。(1)尋找權(quán)和最小重邊集尋找權(quán)和最小重邊集E,

3、 使使G+E是歐拉圖是歐拉圖.(2)在在G+E中找一條歐拉閉跡中找一條歐拉閉跡. Jack Edmonds and Ellis L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming 1973,5(1):88-124算法：算法：如果如果G是連通圖，轉(zhuǎn)是連通圖，轉(zhuǎn)2，否則返回?zé)o解并結(jié)束；，否則返回?zé)o解并結(jié)束；檢查檢查G中的奇點，構(gòu)成圖中的奇點，構(gòu)成圖H的頂點集；的頂點集；求出求出G中每對奇點之間的最短路徑長度，作為中每對奇點之間的最短路徑長度，作為圖圖H對應(yīng)頂點間的邊權(quán)；對應(yīng)頂點間的邊

4、權(quán)；對對H進行最小權(quán)匹配；進行最小權(quán)匹配；把最小權(quán)匹配里的每一條匹配邊代表的路徑，把最小權(quán)匹配里的每一條匹配邊代表的路徑，加入到圖加入到圖G中得到圖中得到圖G；1. 在在G中求歐拉回路，即所求的最優(yōu)路線。中求歐拉回路，即所求的最優(yōu)路線。求中國郵遞員問題的一個簡單算法求中國郵遞員問題的一個簡單算法表上作業(yè)法表上作業(yè)法判定標準判定標準1 在最優(yōu)郵遞路線上，圖中的每在最優(yōu)郵遞路線上，圖中的每一條邊一條邊 至多有一條重復(fù)邊。至多有一條重復(fù)邊。判定標準判定標準2 在最優(yōu)郵遞路線上，圖中每在最優(yōu)郵遞路線上，圖中每一個圈的重復(fù)邊的總權(quán)小于或者等于該一個圈的重復(fù)邊的總權(quán)小于或者等于該圈總權(quán)的一半。圈總權(quán)的一半

5、。 兩個判定標準兩個判定標準v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v8v7v6v5v4v3v2v1v10v910949718522210練習(xí)：練習(xí)： 設(shè)有設(shè)有n個城市個城市A1,A2,An, 每兩個城市間每兩個城市間都有直航的航班。一個推銷員從都有直航的航班。一個推銷員從A1乘飛乘飛機出發(fā)，每個城市都去一次，最后返回機出發(fā)，每個城市都去

6、一次，最后返回A1。任何兩個城市的距離都是已知的，。任何兩個城市的距離都是已知的，問應(yīng)如何安排旅行路線使總路程最短？問應(yīng)如何安排旅行路線使總路程最短？旅行推銷員問題旅行推銷員問題(TSP) 旅行推銷員問題用圖論的語言可敘述為旅行推銷員問題用圖論的語言可敘述為: 在在賦權(quán)完全圖中，求權(quán)最小的哈密爾頓圈。賦權(quán)完全圖中，求權(quán)最小的哈密爾頓圈。 一個最直接的想法是將一個最直接的想法是將n階完全圖的階完全圖的(n-1)!個哈密爾頓圈全部排列出來，依次比較個哈密爾頓圈全部排列出來，依次比較它們的權(quán)的大小。但這種想法在實際上它們的權(quán)的大小。但這種想法在實際上是行不通的。因為隨著是行不通的。因為隨著n的增大，計算量的增大，計算量將急劇增加，即使是大容量高速計算機將急劇增加，即使