中國郵遞員問題算法

馮偉森Email：08十一月2023離散數(shù)學計算機學院2023/11/8計算機學院2主要內(nèi)容Euler圖及其應用歐拉道路〔回路〕的定義如何判別歐拉圖一個圖含有歐拉道路的條件連通有向圖G中含有有向歐拉道路和回路的充要條件Fleury算法Euler圖的應用(中國郵遞員問題算法)2023/11/8計算機學院3哥尼斯堡七橋問題哥尼斯堡城市有一條橫貫全城的普雷格爾(Pregel)河，城的各局部用七座橋聯(lián)接，每逢假日，城中居民進展環(huán)城逛游，這樣就產(chǎn)生了一個問題：能不能設計一次“遍游”，使得從某地動身對每座跨河橋只走一次，而在遍歷了七橋之后卻又能回到原地？Ab2BDCb4b1b3b5b7b62023/11/8計算機學院4Euler圖定義13-1.1設G是一個無孤立結(jié)點的圖，包含G的每條邊的簡潔道路〔回路〕稱為該圖的一條歐拉道路〔回路〕。具有歐拉回路的圖稱為歐拉圖。規(guī)定平凡圖為歐拉圖。明顯，每個歐拉圖必定是連通圖。因此，一條歐拉道路〔回路〕是經(jīng)過圖中每邊一次且僅一次的道路〔回路〕。為什么？2023/11/8計算機學院5例13-1.1v5v1v2v3v4a)v5v1v2v3v4b)v4v1v2v3c)

圖a是歐拉圖；圖b不是歐拉圖，但存在歐拉道路；圖c不存在歐拉道路。2023/11/8計算機學院6定理13-1.1無向連通圖G＝<V，E>是歐拉圖當且僅當G的全部結(jié)點的度數(shù)都為偶數(shù)。證明：“”設G是Euler圖，則G必定存在一條包含全部邊〔也包含全部結(jié)點〕的回路C，對uV，u必定在C中消失一次〔可消失屢次〕，每消失u一次，都關(guān)聯(lián)著G中的兩條邊，而當u又重復消失時，它又關(guān)聯(lián)著G中的另外的兩條邊，〔為什么？〕因而u每消失一次，都將使得結(jié)點u的度數(shù)增加2度，假設u在通路中重復消失j次，則deg(u)＝2j。即u的度數(shù)必為偶數(shù)。由于在回路C中邊不行能重復消失2023/11/8計算機學院7“”設連通圖G的結(jié)點的度數(shù)都是偶數(shù)，則G必含有簡潔回路〔可對結(jié)點個數(shù)進展歸納證明〕。設C是一條包含G中邊最多的簡潔回路：⑴假設C已經(jīng)包含G中全部的邊，則C就是Euler回路，結(jié)論成立。⑵假設C不能包含G中全部的邊，則刪邊子圖G-E〔C〕仍舊無奇數(shù)度結(jié)點。由于G是連通的，C中應至少存在一點v，使G-E〔C〕中有一條包含v的回路C′?！惨娛疽鈭D〕Why?2023/11/8計算機學院8這樣，就可以構(gòu)造出一條由C和C′組成的G的回路，其包含的邊數(shù)比C多，與假設沖突。因此，C必是Euler回路，結(jié)論成立。2023/11/8計算機學院9證明：“”設G具有一條Euler道路L，則在L中除起點和終點外，其余每個結(jié)點都與偶數(shù)條邊相關(guān)聯(lián)，所以，G中僅有零個〔Euler回路〕或者兩個奇數(shù)度結(jié)點?！啊雹偶僭OG沒有奇度數(shù)結(jié)點，則結(jié)論明顯成立；⑵假設G有兩個奇度數(shù)結(jié)點u和v，則G+uv是Euler圖，從而存在Euler回路C。從C中去掉邊uv，則得到一條簡潔道路L〔起點u和終點v〕，且包含了G的全部邊，即L是一條Euler道路。推論非平凡連通圖G＝<V，E>含有歐拉道路當且僅當G僅有零個或者兩個奇數(shù)度結(jié)點。留意：假設有兩個奇度數(shù)結(jié)點，則它們是G中每條歐拉通路的端點。2023/11/8計算機學院10例13-1.2由定理13-1.1及推論簡潔看出：是歐拉圖；不是歐拉圖，但存在歐拉道路；既不是歐拉圖，也不存在歐拉道路。V2V1V5V3V4(a)V2V1V5V3V4(b)V1V4V2V3(c)現(xiàn)在，我們是不是已經(jīng)解決了哥尼斯堡七橋問題？2023/11/8計算機學院11有向圖的歐拉道路、歐拉圖定理13-1.2ⅰ〕有向連通圖G含有有向歐拉道路，當且僅當除了兩個結(jié)點以外，其余結(jié)點的入度等于出度，而這兩個例外的結(jié)點中，一個結(jié)點的入度比出度大1，另一個結(jié)點的出度比入度大1。ⅱ〕有向連通圖G含有有向歐拉回路，當且僅當G中的全部結(jié)點的入度等于出度。類似于無向圖的爭論，對有向圖我們有以下結(jié)論：同樣，有向Euler圖的結(jié)點度數(shù)都為偶數(shù)；含有有向Euler道路的圖僅有零個或者兩個奇度數(shù)結(jié)點。2023/11/8計算機學院12例13-1.3V1V2V3V4V1V2V3V4V8V2V4V6V1V3V5V7圖a)存在一條的歐拉道路：v3v1v2v3v4v1；(a)(b)(c)圖(b)中存在歐拉回路v1v2v3v4v1v3v1，因而(b)是歐拉圖；圖(c)中有歐拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是歐拉圖。2023/11/8計算機學院13例13-1.4解在圖中，僅有兩個度數(shù)為奇數(shù)的結(jié)點b，c，因而存在從b到c的歐拉通路，螞蟻乙走到c只要走一條歐拉通路，邊數(shù)為9條。而螞蟻甲要想走完全部的邊到達c，至少要先走一條邊到達b，再走一條歐拉通路，因而它至少要走10條邊才能到達c，所以乙必勝。甲、乙兩只螞蟻分別位于右圖中的結(jié)點a，b處，并設圖中的邊長度是相等的。甲、乙進展競賽：從它們所在的結(jié)點動身，走過圖中的全部邊最終到達結(jié)點c處。假設它們的速度一樣，問誰先到達目的地？cb(乙)a(甲)2023/11/8計算機學院14Fleury算法〔構(gòu)造Euler回路〕任取v0∈V，令P0＝v0；設P0＝v0e1v1e2…eivi，按下面的方法從GK=E-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無別的邊可選取，否則ei+1不應當為Gk＝G-{e1,e2,…,ei}中的橋；當Gk為零圖時，算法完畢；否則，返回2。設G＝<V，E>是一個歐拉圖即假設ei+1是割邊，同時還有其它邊與vi相關(guān)聯(lián)，則不能選ei+12023/11/8計算機學院15例13-1.5v4v5v6e4e5e6e10e9e8e3在右圖所示的歐拉圖中，某人用算法求Ｇ中的歐拉回路時，走了簡潔的回路：v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后，無法行遍了，試分析在哪步他犯了錯誤？v1v3v7e1e2e7v８e1３e1２e1４e1１v2v4v5v6e4e5e6e10e9e8e3v1v3v7e1e2e7v８e1３e1２e1４e1１v2此人行遍v8時犯了能不走橋就不走橋的錯誤，因而未能行遍出歐拉回路。當他走到v8時，Ｇ－｛e2，e3，e14，e10，e1，e8｝,見右圖，此時，e9為該圖中的橋，而e7、e11均不是橋。因此，他不該走e9，而應當走e7或e11。但在行遍v3和v1時，也遇到橋，為什么沒有問題呢？v9v92023/11/8計算機學院16中國郵遞員問題山東師范大學，管梅谷先生1962提出并解決?！矃⒖嘉墨I：①1962〔數(shù)學通報〕81.10,P32,②<電子技術(shù)應用>,81.5〕一個郵遞員從郵局動身，在其分管的投遞區(qū)域內(nèi)走遍全部的街道把郵件送到每個收件人手中，最終又回到郵局，要走怎樣的線路使全程最短。這個問題用圖來表示：街道為圖的邊，街道穿插口為圖的結(jié)點，問題就是要從這樣一個圖中找出一條至少包含每條邊一次的總長最短的回路。2023/11/8計算機學院17對此，管梅谷曾證明，假設圖的邊數(shù)為m，則所求回路的長度最小是m，最多不超過2m，并且每條邊在其中最多消失兩次。中國郵遞員問題，一般為在帶權(quán)連通圖中找一條包括全部邊的且權(quán)最小的回路。這個問題有著有效的解決方法，其中最直觀的方法之一是:把圖中的某些邊復制成兩條邊，然后在所求圖中找一條歐拉回路。中國郵遞員問題是運籌學中一個典型的優(yōu)化問題。明顯，當這個圖是歐拉圖時，任何一條歐拉回路都符合要求；當這個圖不是歐拉圖時，所求回路必定要重復通過某些邊。關(guān)鍵是：復制哪些邊？2023/11/8計算機學院18算法〔1〕假設G不含奇數(shù)度結(jié)點，則任一歐拉回路就是問題的解決。〔2〕假設G含有2K(K>0)個奇數(shù)度結(jié)點，則先求出其中任何兩點間的最短路徑，然后再在這些路徑之中找出K條路徑P1，P2，…，PK，使得滿足以下條件：①任何Pi和Pj〔i≠j〕沒有一樣的起點和終點。②在所滿足①的K條最短路徑的集合中，P1，P2，…PK的長度總和最短?！?〕依據(jù)〔2〕中求出的K條最短道路P1，P2，…，PK，在原圖G中復制全部消失的在這條道路上的邊，設所得之圖為G′。〔4〕構(gòu)造G′的歐拉回路，即得中國郵遞員問題的解。找出需復制的邊連通圖中，奇數(shù)度結(jié)點的個數(shù)必為偶數(shù)個。2023/11/8計算機學院19例13-1.61．由于G含有奇數(shù)度結(jié)點，所以2．G中有2K=4(K=2)個奇結(jié)點V1，V2，V3，V5。這4點間的距離d(V1,V2)=3，d(V1,V3)=5，d(V1,V5)=4，d(V2,V3)=2，d(V2,V5)=3，d(V3,V5)=4各路徑:V1V2(3),V3V5(4)—7V1V3(5),V2V5(3)—8