中國郵遞員問題算法

馮偉森Email：fws365@08十月2022離散數(shù)學(xué)計(jì)算機(jī)學(xué)院2023/2/5計(jì)算機(jī)學(xué)院2主要內(nèi)容Euler圖及其應(yīng)用歐拉道路（回路）的定義如何判別歐拉圖一個(gè)圖含有歐拉道路的條件連通有向圖G中含有有向歐拉道路和回路的充要條件

Fleury算法Euler圖的應(yīng)用(中國郵遞員問題算法)

2023/2/5計(jì)算機(jī)學(xué)院3哥尼斯堡七橋問題哥尼斯堡城市有一條橫貫全城的普雷格爾(Pregel)河，城的各部分用七座橋聯(lián)接，每逢假日，城中居民進(jìn)行環(huán)城逛游，這樣就產(chǎn)生了一個(gè)問題：能不能設(shè)計(jì)一次“遍游”，使得從某地動(dòng)身對(duì)每座跨河橋只走一次，而在遍歷了七橋之后卻又能回到原地？Ab2BDCb4b1b3b5b7b62023/2/5計(jì)算機(jī)學(xué)院4Euler圖定義13-1.1設(shè)G是一個(gè)無孤立結(jié)點(diǎn)的圖，包含G的每條邊的簡潔道路（回路）稱為該圖的一條歐拉道路（回路）。具有歐拉回路的圖稱為歐拉圖。規(guī)定平凡圖為歐拉圖。明顯，每個(gè)歐拉圖必定是連通圖。

因此，一條歐拉道路（回路）是經(jīng)過圖中每邊一次且僅一次的道路（回路）。為什么？2023/2/5計(jì)算機(jī)學(xué)院5例13-1.1v5v1v2v3v4a)v5v1v2v3v4b)v4v1v2v3c)

圖a是歐拉圖；圖b不是歐拉圖，但存在歐拉道路；圖c不存在歐拉道路。2023/2/5計(jì)算機(jī)學(xué)院6定理13-1.1無向連通圖G＝<V，E>是歐拉圖當(dāng)且僅當(dāng)G的全部結(jié)點(diǎn)的度數(shù)都為偶數(shù)。證明：“”設(shè)G是Euler圖，則G必定存在一條包含全部邊（也包含全部結(jié)點(diǎn)）的回路C，對(duì)uV，u必定在C中出現(xiàn)一次（可出現(xiàn)多次），每出現(xiàn)u一次，都關(guān)聯(lián)著G中的兩條邊，而當(dāng)u又重復(fù)出現(xiàn)時(shí)，它又關(guān)聯(lián)著G中的另外的兩條邊，（為什么？）因而u每出現(xiàn)一次，都將使得結(jié)點(diǎn)u的度數(shù)增加2度，若u在通路中重復(fù)出現(xiàn)j次，則deg(u)＝2j。即u的度數(shù)必為偶數(shù)。由于在回路C中邊不行能重復(fù)出現(xiàn)2023/2/5計(jì)算機(jī)學(xué)院7“”設(shè)連通圖G的結(jié)點(diǎn)的度數(shù)都是偶數(shù)，則G必含有簡潔回路（可對(duì)結(jié)點(diǎn)個(gè)數(shù)進(jìn)行歸納證明）。設(shè)C是一條包含G中邊最多的簡潔回路：⑴若C已經(jīng)包含G中全部的邊，則C就是Euler回路，結(jié)論成立。⑵若C不能包含G中全部的邊，則刪邊子圖G-E（C）照舊無奇數(shù)度結(jié)點(diǎn)。

由于G是連通的，C中應(yīng)至少存在一點(diǎn)v，使G-E（C）中有一條包含v的回路C′。（見示意圖）Why?2023/2/5計(jì)算機(jī)學(xué)院8這樣，就可以構(gòu)造出一條由C和C′組成的G的回路，其包含的邊數(shù)比C多，與假設(shè)沖突。因此，C必是Euler回路，結(jié)論成立。2023/2/5計(jì)算機(jī)學(xué)院9證明：“”設(shè)G具有一條Euler道路L，則在L中除起點(diǎn)和終點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都與偶數(shù)條邊相關(guān)聯(lián)，所以，G中僅有零個(gè)（Euler回路）或者兩個(gè)奇數(shù)度結(jié)點(diǎn)?！啊雹湃鬐沒有奇度數(shù)結(jié)點(diǎn)，則結(jié)論明顯成立；⑵若G有兩個(gè)奇度數(shù)結(jié)點(diǎn)u和v，則G+uv是Euler圖，從而存在Euler回路C。從C中去掉邊uv，則得到一條簡潔道路L（起點(diǎn)u和終點(diǎn)v），且包含了G的全部邊，即L是一條Euler道路。推論13-1.1.1非平凡連通圖G＝<V，E>含有歐拉道路當(dāng)且僅當(dāng)G僅有零個(gè)或者兩個(gè)奇數(shù)度結(jié)點(diǎn)。留意：若有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通路的端點(diǎn)。2023/2/5計(jì)算機(jī)學(xué)院10例13-1.2由定理13-1.1及推論13-1.1.1簡潔看出：是歐拉圖；不是歐拉圖，但存在歐拉道路；既不是歐拉圖，也不存在歐拉道路。V2V1V5V3V4(a)V2V1V5V3V4(b)V1V4V2V3(c)現(xiàn)在，我們是不是已經(jīng)解決了哥尼斯堡七橋問題？2023/2/5計(jì)算機(jī)學(xué)院11有向圖的歐拉道路、歐拉圖定理13-1.2?。┯邢蜻B通圖G含有有向歐拉道路，當(dāng)且僅當(dāng)除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的出度比入度大1。ⅱ）有向連通圖G含有有向歐拉回路，當(dāng)且僅當(dāng)G中的全部結(jié)點(diǎn)的入度等于出度。類似于無向圖的探討，對(duì)有向圖我們有以下結(jié)論：同樣，有向Euler圖的結(jié)點(diǎn)度數(shù)都為偶數(shù)；含有有向Euler道路的圖僅有零個(gè)或者兩個(gè)奇度數(shù)結(jié)點(diǎn)。2023/2/5計(jì)算機(jī)學(xué)院12例13-1.3V1V2V3V4V1V2V3V4V8V2V4V6V1V3V5V7圖a)存在一條的歐拉道路：v3v1v2v3v4v1；(a)(b)(c)圖(b)中存在歐拉回路v1v2v3v4v1v3v1，因而(b)是歐拉圖；圖(c)中有歐拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是歐拉圖。2023/2/5計(jì)算機(jī)學(xué)院13例13-1.4解在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c的歐拉通路，螞蟻乙走到c只要走一條歐拉通路，邊數(shù)為9條。而螞蟻甲要想走完全部的邊到達(dá)c，至少要先走一條邊到達(dá)b，再走一條歐拉通路，因而它至少要走10條邊才能到達(dá)c，所以乙必勝。甲、乙兩只螞蟻分別位于右圖中的結(jié)點(diǎn)a，b處，并設(shè)圖中的邊長度是相等的。甲、乙進(jìn)行競賽：從它們所在的結(jié)點(diǎn)動(dòng)身，走過圖中的全部邊最終到達(dá)結(jié)點(diǎn)c處。假如它們的速度相同，問誰先到達(dá)目的地？cb(乙)a(甲)2023/2/5計(jì)算機(jī)學(xué)院14Fleury算法（構(gòu)造Euler回路）任取v0∈V，令P0＝v0；設(shè)P0＝v0e1v1e2…eivi，按下面的方法從GK=E-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無別的邊可選取，否則ei+1不應(yīng)當(dāng)為Gk＝G-{e1,e2,…,ei}中的橋；當(dāng)Gk為零圖時(shí)，算法結(jié)束；否則，返回2。設(shè)G＝<V，E>是一個(gè)歐拉圖即假如ei+1是割邊，同時(shí)還有其它邊與vi相關(guān)聯(lián)，則不能選ei+12023/2/5計(jì)算機(jī)學(xué)院15例13-1.5v4v5v6e4e5e6e10e9e8e3在右圖所示的歐拉圖中，某人用算法求Ｇ中的歐拉回路時(shí)，走了簡潔的回路：v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后，無法行遍了，試分析在哪步他犯了錯(cuò)誤？v1v3v7e1e2e7v８e1３e1２e1４e1１v2v4v5v6e4e5e6e10e9e8e3v1v3v7e1e2e7v８e1３e1２e1４e1１v2此人行遍v8時(shí)犯了能不走橋就不走橋的錯(cuò)誤，因而未能行遍出歐拉回路。當(dāng)他走到v8時(shí)，Ｇ－｛e2，e3，e14，e10，e1，e8｝,見右圖，此時(shí)，e9為該圖中的橋，而e7、e11均不是橋。因此，他不該走e9，而應(yīng)當(dāng)走e7或e11。但在行遍v3和v1時(shí)，也遇到橋，為什么沒有問題呢？v9v92023/2/5計(jì)算機(jī)學(xué)院16中國郵遞員問題山東師范高校，管梅谷先生1962提出并解決。（參考文獻(xiàn)：①1962（數(shù)學(xué)通報(bào)）81.10,P32,②<電子技術(shù)應(yīng)用>,81.5）一個(gè)郵遞員從郵局動(dòng)身，在其分管的投遞區(qū)域內(nèi)走遍全部的街道把郵件送到每個(gè)收件人手中，最終又回到郵局，要走怎樣的線路使全程最短。這個(gè)問題用圖來表示：街道為圖的邊，街道交叉口為圖的結(jié)點(diǎn)，問題就是要從這樣一個(gè)圖中找出一條至少包含每條邊一次的總長最短的回路。2023/2/5計(jì)算機(jī)學(xué)院17

對(duì)此，管梅谷曾證明，若圖的邊數(shù)為m，則所求回路的長度最小是m，最多不超過2m，并且每條邊在其中最多出現(xiàn)兩次。中國郵遞員問題，一般為在帶權(quán)連通圖中找一條包括全部邊的且權(quán)最小的回路。這個(gè)問題有著有效的解決方法，其中最直觀的方法之一是:把圖中的某些邊復(fù)制成兩條邊，然后在所求圖中找一條歐拉回路。中國郵遞員問題是運(yùn)籌學(xué)中一個(gè)典型的優(yōu)化問題。明顯，當(dāng)這個(gè)圖是歐拉圖時(shí)，任何一條歐拉回路都符合要求；當(dāng)這個(gè)圖不是歐拉圖時(shí)，所求回路必定要重復(fù)通過某些邊。關(guān)鍵是：復(fù)制哪些邊？2023/2/5計(jì)算機(jī)學(xué)院18算法（1）若G不含奇數(shù)度結(jié)點(diǎn)，則任一歐拉回路就是問題的解決。（2）若G含有2K(K>0)個(gè)奇數(shù)度結(jié)點(diǎn)，則先求出其中任何兩點(diǎn)間的最短路徑，然后再在這些路徑之中找出K條路徑P1，P2，…，PK，使得滿足以下條件：①任何Pi和Pj（i≠j）沒有相同的起點(diǎn)和終點(diǎn)。②在所滿足①的K條最短路徑的集合中，P1，P2，…PK的長度總和最短。（3）依據(jù)（2）中求出的K條最短道路P1，P2，…，PK，在原圖G中復(fù)制全部出現(xiàn)的在這條道路上的邊，設(shè)所得之圖為G′。（4）構(gòu)造G′的歐拉回路，即得中國郵遞員問題的解。找出需復(fù)制的邊連通圖中，奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)必為偶數(shù)個(gè)。2023/2/5計(jì)算機(jī)學(xué)院19例13-1.61．因?yàn)镚含有奇數(shù)度結(jié)點(diǎn)，所以2．G中有2K=4(K=2)個(gè)奇結(jié)點(diǎn)V1，V2，V3，V5。這4點(diǎn)間的距離

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)—8V1V5(4),V2V3