1、行遍性問題,安徽工業(yè)大學(xué)數(shù)理學(xué)院,行遍性問題,一、中國郵遞員問題,二、推銷員問題,1、歐拉圖,2、中國郵遞員問題,1、哈密爾頓圖,2、旅行商問題,歐拉圖,18世紀(jì)時(shí)，歐洲有一個(gè)風(fēng)景秀麗的小城哥尼斯堡(今俄羅斯加里寧格勒)，那里的普萊格爾河上有七座橋。將河中的兩個(gè)島和河岸連結(jié)，城中的居民經(jīng)常沿河過橋散步，于是提出了一個(gè)問題：一個(gè)人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點(diǎn)？大家都試圖找出問題的答案，但是誰也解決不了這個(gè)問題這就是哥尼斯堡七橋問題，一個(gè)著名的圖論問題。,1727年20歲瑞士數(shù)學(xué)家歐拉，被俄國請(qǐng)去在圣彼得堡（原列寧格勒）的科學(xué)院做研究。他的德國朋友告訴了他這個(gè)曾經(jīng)令許多

2、人困惑的問題。,1736年歐拉發(fā)表了圖論的第一篇著名論文“哥尼斯堡七橋問題”,歐拉巧妙地把哥尼斯堡城圖化為下圖所示圖G，他把陸地設(shè)為圖G中的結(jié)點(diǎn)，把橋畫成相應(yīng)地聯(lián)結(jié)陸地即結(jié)點(diǎn)的邊。于是，通過哥尼斯堡城中每座橋恰好一次問題，等價(jià)于在圖G中從某一結(jié)點(diǎn)出發(fā)找出一條路，它通過每條邊恰好一次后回到原出發(fā)結(jié)點(diǎn)，亦即等價(jià)于在圖G中尋找一個(gè)圈，它通過G中每一條邊恰好一次。,歐拉圖,巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1,歐拉道路：v1e1v2e2v3e5v1e4v4e3v3,歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1,定義1: 設(shè)G=(V,E)是連通無向圖,1、經(jīng)過G的

3、每邊至少一次的閉通路稱為巡回,2、經(jīng)過G的每邊正好一次的巡回稱為歐拉巡回(圈),3、存在歐拉巡回的圖稱為歐拉圖,4、經(jīng)過G的每邊正好一次的道路稱為歐拉道路,歐拉圖,非歐拉圖,定理1: 對(duì)于非空連通圖G，下列命題等價(jià)：,1、G是歐拉圖,2、G無奇次頂點(diǎn),3、G的邊集能劃分為圈,推論1: 設(shè)G是非平凡連通圖，則G有歐拉道路的充要條件是G最多只有兩個(gè)奇次頂點(diǎn),中國郵遞員問題-定義,郵遞員發(fā)送郵件時(shí)，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行程最短的路線這就是中國郵遞員問題.,若將投遞區(qū)的街道用邊表示，街道的長度用邊權(quán)表示，郵局街道交叉口用點(diǎn)表示，則一個(gè)投遞

4、區(qū)構(gòu)成一個(gè)賦權(quán)連通無向圖中國郵遞員問題轉(zhuǎn)化為：在一個(gè)非負(fù)加權(quán)連通圖中，尋求一個(gè)權(quán)最小的巡回這樣的巡回稱為最佳巡回,定義: 設(shè)圖G =(V，E)，ME，若M的邊互不相鄰，則稱M是G 的一個(gè)匹配.,若頂點(diǎn)v與M的一條邊關(guān)聯(lián)，則稱v是M飽和的,設(shè)M是G的一個(gè)匹配，若G的每個(gè)頂點(diǎn)都是M飽和的，則稱M是G的理想匹配.,G的邊e是割邊的充要條件是e不含在G的圈中,設(shè)G連通，eE(G),若從G中刪除邊e后，圖G-e不連通，則稱邊e為圖G的割邊,割邊的定義：,割邊,中國郵遞員問題-算法,1、G是歐拉圖,此時(shí)G的任何一個(gè)歐拉巡回便是最佳巡回問題歸結(jié)為在歐拉圖中確定一個(gè)歐拉巡回,Fleury算法：求歐拉圖的歐拉巡

5、回,Fleury算法-基本思想：從任一點(diǎn)出發(fā)，每當(dāng)訪問一條邊時(shí)，先要進(jìn)行檢查如果可供訪問的邊不止一條，則應(yīng)選一條不是未訪問的邊集的導(dǎo)出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止.,b) 除非不能選擇，否則一定要使ei+1不是Gi=GE-e1,e2, ,ei 的割邊,Fleury算法算法步驟：,1、任選一個(gè)頂點(diǎn)v0，令道路w0=v0,2、假定道路wi=v0e1v1e2eivi已經(jīng)選好，則從Ee1,e2, ,ei中選一條邊ei+1，使：,a) ei+1與vi相關(guān)聯(lián),3、第2步不能進(jìn)行時(shí)就停止,若G不是歐拉圖，則G的任何一個(gè)巡回經(jīng)過某些邊必定多于一次,解決這類問題的一般方法是，在一些點(diǎn)對(duì)之間引入重復(fù)

6、邊（重復(fù)邊與它平行的邊具有相同的權(quán)），使原圖成為歐拉圖，但希望所有添加的重復(fù)邊的權(quán)的總和為最小,2、G不是歐拉圖,情形G正好有兩個(gè)奇次頂點(diǎn),1、用Dijkstra算法求出奇次頂點(diǎn)u與v之間的最短路徑P,2、令G*=GP，則G*為歐拉圖,3、用Fleury算法求出G*的歐拉巡回，這就是G的最佳巡回,情形2G有2n個(gè)奇次頂點(diǎn)（n2）,Edmonds最小對(duì)集算法：,基本思想：,先將奇次頂點(diǎn)配對(duì)，要求最佳配對(duì)，即點(diǎn)對(duì)之間距離總和最小再沿點(diǎn)對(duì)之間的最短路徑添加重復(fù)邊得歐拉圖G*，G*的歐拉巡回便是原圖的最佳巡回,算法步驟：,1、用Floyd算法求出的所有奇次頂點(diǎn)之間的最短路徑和距離,2、以G的所有奇次頂

7、點(diǎn)為頂點(diǎn)集（個(gè)數(shù)為偶數(shù)），作一完備圖，邊上的權(quán)為兩端點(diǎn)在原圖G中的最短距離，將此完備加權(quán)圖記為G1,3、求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)的最佳配對(duì),4、在G中沿配對(duì)頂點(diǎn)之間的最短路徑添加重復(fù)邊得歐拉圖G*,5、用Fleury算法求出G*的歐拉巡回，這就是G的最佳巡回,例求右圖所示投遞區(qū)的一條最佳郵遞路線,1、圖中有v4、v7、v8、v9四個(gè)奇次頂點(diǎn),用步驟3求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)的最佳配對(duì),2、以v4、v7、v8、v9為頂點(diǎn)，它們之間的距離為邊權(quán)構(gòu)造完備圖G1,3、求出G1的最小權(quán)完美匹配M=(v4,v7),(v8,v9),4、在G中沿v4到v7的最短路徑添加重復(fù)邊，

8、沿v8到v9的最短路徑v8v9添加重復(fù)邊，得歐拉圖G2G2中一條歐拉巡回就是G的一條最佳巡回其權(quán)值為64,與歐拉圈非常類似的問題是哈密爾頓圈的問題。1859年，愛爾蘭數(shù)學(xué)家哈密爾頓(W.R.Hamilton)首先提出“環(huán)球周游”問題。他用一個(gè)正十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)大城市，這個(gè)正十二面體同構(gòu)于一個(gè)平面圖，要求旅游者能否找到沿著正十二面體的棱，從某個(gè)頂點(diǎn)(城市)出發(fā)，經(jīng)過每個(gè)頂點(diǎn)(城市)恰好一次，然后回到出發(fā)頂點(diǎn)?這便是著名的哈密爾頓問題。,哈密爾頓圖,哈密爾頓圖,定義: 設(shè)G=(V,E)是連通無向圖,1、經(jīng)過G的每個(gè)頂點(diǎn)正好一次的路徑，稱為G的一條哈密爾頓路徑,2、經(jīng)過G的每個(gè)頂

9、點(diǎn)正好一次的圈，稱為G的哈密爾頓圈或H圈,3、含H圈的圖稱為哈密爾頓圖或H圖,按圖中所給的編號(hào)進(jìn)行旅游，便是哈密爾頓問題的解。,對(duì)于任何連通圖也有類似的問題。,哈密爾頓圖盡管在形式上與歐拉圖極其相似，但其結(jié)論上卻有很大不同，至今還沒有得到關(guān)于哈密爾頓圖的非平凡的充要條件，這是圖論尚未解決的主要問題之一,最小Hamilton回路與旅行商問題,設(shè)G=(V,E,w)，其中V是頂點(diǎn)集，E是邊集，w為定義在E上的權(quán)（非負(fù)）。,G的一個(gè)Hamilton回路是頂點(diǎn)集V上的一個(gè)循環(huán)排列p=v1v2vnvn+1(v1=vn+1)，其中vivi+1E，w(p)定義為p上所有邊權(quán)之和，當(dāng)w(p)達(dá)到最小時(shí)，p稱為最

10、小Hamilton回路。,G的一個(gè)旅行商路線是頂點(diǎn)集V的可重復(fù)的但不遺漏的一個(gè)循環(huán)排列，多旅行商路線則是頂點(diǎn)集可重復(fù)的但總體上不遺漏的多個(gè)循環(huán)排列。,Hamilton回路（圈）,旅行商線路,若G是連通的但不是完全圖時(shí)，G可能不存在Hamilton回路，更不存在最小Hamilton回路，但若G是連通的，就一定存在最優(yōu)旅行商路線。,右圖不存在Hamilton回路，但最優(yōu)旅行商線路為v1v2 v4 v5 v4 v3 v1,若G完全圖時(shí)，則G一定存在Hamilton回路，且亦存在最小Hamilton回路，但該最小Hamilton回路未必就是最優(yōu)旅行商路線。,試考察右圖,右圖的最小Hamilton回路為

11、： v1 v2 v3 v4 v5v1,右圖的最優(yōu)旅行商路線為： v1 v2 v3 v4 v1 v5v1,最小Hamilton回路長19，最優(yōu)旅行商路線長17。,問題：在什么條件下，最小Hamilton回路就是最優(yōu)旅行商線路？,定理,若完全圖G=(V,E,w)的權(quán)滿足三角不等式,則G的最小Hamilton回路就是最優(yōu)旅行商路線,最優(yōu)旅行商路線無法直接求，要設(shè)法將其化為求最小Hamilton回路，由上面的結(jié)論，設(shè)法將圖化為完全圖且邊權(quán)滿足三角不等式。,方法如下（若G是非完全圖）,1）將G=(V,E,w)化為完全圖G=(V,E,w)，其中wij用vi到vj的最短路代替，這樣G的邊權(quán)就滿足了三角不等式

12、。,2）求G的最小Hamilton回路。,3）將求出的最小Hamilton回路中的邊vivj用相應(yīng)的vi到vj的最短路代回，即求出了最優(yōu)旅行商路線。,問題轉(zhuǎn)化為如何求Hamilton圈問題。,求Hamilton圈為一難解問題，現(xiàn)已從理論上證明了其無有效算法。所以僅能求近似解。,一種近似算法（改良圈法）,1）在完全圖上任取一Hamilton圈，不妨設(shè)為C=v1v2vnv1,2）檢查是否存在ij，使vi-1vjE(G), vivj+1E(G)且成立wi,j+1+wi-1,jwi-1,i+wj,j+1,若成立則有改良圈C1=v1v2vi-1vjvj-1 vivj+1vj+2 vnv1。,3）令C=C1，轉(zhuǎn)2），直到停止。,該算法得到的Hamilton圈未必是理想圈，但其算法復(fù)雜度低。,示例,從北京(Pe)到倫敦(L)、墨西哥城(MC)、紐約(NY)、巴黎(Pa)、東京(T)各城去環(huán)球講學(xué)，乘飛機(jī)到各城一次再返回首都北京，應(yīng)如何安排行程最省旅費(fèi)？（各城間距離作為邊權(quán)在圖中標(biāo)出）,問題求解,給出初始圈 C=(Pe) (T) (L) (MC) (NY) (Pa) (Pe),L,得到改良圈,C=(Pe) (T) (MC) (NY) (L) (Pa) (Pe),其總長度為13+70+21+35+2+51=192,該結(jié)論未必達(dá)到最小Ham