三節(jié)Euler圖和Hamilton圖應(yīng)用ppt課件

1、 第三節(jié)第三節(jié) Euler圖和圖和 Hamilton 圖的應(yīng)用圖的應(yīng)用 郵遞員從郵局出發(fā)，到他所負(fù)責(zé)的地郵遞員從郵局出發(fā)，到他所負(fù)責(zé)的地段投寄信件。地段中的每條街至少經(jīng)過(guò)段投寄信件。地段中的每條街至少經(jīng)過(guò)一次。問(wèn)應(yīng)怎樣選擇投寄路線(xiàn)使所走的一次。問(wèn)應(yīng)怎樣選擇投寄路線(xiàn)使所走的路程最短？路程最短？中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題1111112111222222332 中國(guó)郵遞員問(wèn)題是由我國(guó)的管梅谷教授中國(guó)郵遞員問(wèn)題是由我國(guó)的管梅谷教授在在1960年首先提出的。年首先提出的。 用圖論的語(yǔ)言用圖論的語(yǔ)言, 這一問(wèn)題可表述為這一問(wèn)題可表述為: 在一在一個(gè)賦權(quán)連通無(wú)向圖個(gè)賦權(quán)連通無(wú)向圖G中，求一個(gè)權(quán)和最中，求一

2、個(gè)權(quán)和最小的包含每條邊至少一次的閉通路。這小的包含每條邊至少一次的閉通路。這樣的閉通路簡(jiǎn)稱(chēng)為最佳郵路。樣的閉通路簡(jiǎn)稱(chēng)為最佳郵路。 若若G是歐拉圖，那么每一條歐拉閉跡即為一是歐拉圖，那么每一條歐拉閉跡即為一條最佳郵路。條最佳郵路。 易證可以用加重邊的方法使任何連通圖易證可以用加重邊的方法使任何連通圖G轉(zhuǎn)轉(zhuǎn)變成歐拉圖變成歐拉圖 若不是歐拉圖，則在每條郵路中必有邊重復(fù)。若不是歐拉圖，則在每條郵路中必有邊重復(fù)。在在G中將邊中將邊e用用k條重邊代替且每一邊都賦權(quán)條重邊代替且每一邊都賦權(quán)W(e)，這樣的過(guò)程稱(chēng)為加重邊。，這樣的過(guò)程稱(chēng)為加重邊。 求最佳郵路的問(wèn)題可轉(zhuǎn)化為下列兩個(gè)問(wèn)題求最佳郵路的問(wèn)題可轉(zhuǎn)化為下

3、列兩個(gè)問(wèn)題: 第第2個(gè)問(wèn)題可用弗勞瑞算法解決。個(gè)問(wèn)題可用弗勞瑞算法解決。 對(duì)于第對(duì)于第1個(gè)問(wèn)題埃德蒙斯個(gè)問(wèn)題埃德蒙斯(J.Edmonds)和和約翰遜約翰遜(L.Johnson)于于1973年給出了一個(gè)年給出了一個(gè)有效算法。有效算法。(1)尋找權(quán)和最小重邊集尋找權(quán)和最小重邊集E, 使使G+E是歐拉圖是歐拉圖.(2)在在G+E中找一條歐拉閉跡中找一條歐拉閉跡. Jack Edmonds and Ellis L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming 1973,5(1):88-

4、124算法：算法：如果如果G是連通圖，轉(zhuǎn)是連通圖，轉(zhuǎn)2，否則返回?zé)o解并結(jié)束；，否則返回?zé)o解并結(jié)束；檢查檢查G中的奇點(diǎn)，構(gòu)成圖中的奇點(diǎn)，構(gòu)成圖H的頂點(diǎn)集；的頂點(diǎn)集；求出求出G中每對(duì)奇點(diǎn)之間的最短路徑長(zhǎng)度，作為圖中每對(duì)奇點(diǎn)之間的最短路徑長(zhǎng)度，作為圖H對(duì)應(yīng)頂點(diǎn)間的邊權(quán)；對(duì)應(yīng)頂點(diǎn)間的邊權(quán)；對(duì)對(duì)H進(jìn)行最小權(quán)匹配；進(jìn)行最小權(quán)匹配；把最小權(quán)匹配里的每一條匹配邊代表的路徑，加把最小權(quán)匹配里的每一條匹配邊代表的路徑，加入到圖入到圖G中得到圖中得到圖G；在在G中求歐拉回路，即所求的最優(yōu)路線(xiàn)。中求歐拉回路，即所求的最優(yōu)路線(xiàn)。求中國(guó)郵遞員問(wèn)題的一個(gè)簡(jiǎn)單算法求中國(guó)郵遞員問(wèn)題的一個(gè)簡(jiǎn)單算法表上作業(yè)法表上作業(yè)法判定標(biāo)準(zhǔn)判定

5、標(biāo)準(zhǔn)1 在最優(yōu)郵遞路線(xiàn)上，圖中的每在最優(yōu)郵遞路線(xiàn)上，圖中的每一條邊一條邊 至多有一條重復(fù)邊。至多有一條重復(fù)邊。判定標(biāo)準(zhǔn)判定標(biāo)準(zhǔn)2 在最優(yōu)郵遞路線(xiàn)上，圖中每在最優(yōu)郵遞路線(xiàn)上，圖中每一個(gè)圈的重復(fù)邊的總權(quán)小于或者等于該一個(gè)圈的重復(fù)邊的總權(quán)小于或者等于該圈總權(quán)的一半。圈總權(quán)的一半。 兩個(gè)判定標(biāo)準(zhǔn)兩個(gè)判定標(biāo)準(zhǔn)v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9v7v6v3v4v5v8v1v2255944346443v9

6、v8v7v6v5v4v3v2v1v10v910949718522210練習(xí)：練習(xí)： 設(shè)有設(shè)有n個(gè)城市個(gè)城市A1,A2,An, 每?jī)蓚€(gè)城市每?jī)蓚€(gè)城市間都有直航的航班。一個(gè)推銷(xiāo)員從間都有直航的航班。一個(gè)推銷(xiāo)員從A1乘乘飛機(jī)出發(fā)，每個(gè)城市都去一次，最后返飛機(jī)出發(fā)，每個(gè)城市都去一次，最后返回回A1。任何兩個(gè)城市的距離都是已知的，。任何兩個(gè)城市的距離都是已知的，問(wèn)應(yīng)如何安排旅行路線(xiàn)使總路程最短？問(wèn)應(yīng)如何安排旅行路線(xiàn)使總路程最短？旅行推銷(xiāo)員問(wèn)題旅行推銷(xiāo)員問(wèn)題(TSP) 旅行推銷(xiāo)員問(wèn)題用圖論的語(yǔ)言可敘述為旅行推銷(xiāo)員問(wèn)題用圖論的語(yǔ)言可敘述為: 在在賦權(quán)完全圖中，求權(quán)最小的哈密爾頓圈。賦權(quán)完全圖中，求權(quán)最小的哈密爾頓圈。 一個(gè)最直接的想法是將一個(gè)最直接的想法是將n階完全圖的階完全圖的(n-1)!個(gè)哈密爾頓圈全部排列出來(lái)，依次比較個(gè)哈密爾頓圈全部排列出來(lái)，依次比較它們的權(quán)的大小。但這種想法在實(shí)際上它們的權(quán)的大小。但這種想法在實(shí)際上是行不通的。因?yàn)殡S著是行不通的。因?yàn)殡S著n的增大，計(jì)算量的增大，計(jì)算量將急劇增加，即使是大容量高速計(jì)算機(jī)將