中國郵路問題及其算法

1、目 錄 TOC o 1-3 h z u HYPERLINK 1引言1 HYPERLINK 2中國郵路問題1 HYPERLINK 2.1圖的概念1 HYPERLINK 2.2道路與回路2 HYPERLINK 2.2.1基本概念2 HYPERLINK 2.2.2歐拉回路3 HYPERLINK 2.3中國郵路問題3 HYPERLINK 2.3.1無向圖的中國郵路問題4 HYPERLINK 2.3.2有向圖的中國郵路問題6 HYPERLINK 3中國郵路問題的算法8 HYPERLINK 3.1無向圖的中國郵路問題的算法8 HYPERLINK 3.1.1奇偶點(diǎn)圖上作業(yè)法8 HYPERLINK 3.1.2

2、最小權(quán)匹配算法10 HYPERLINK 3.1.3破圈法12 HYPERLINK 3.2有向圖的中國郵路問題的算法14 HYPERLINK 4中國郵路問題在實(shí)際生活中的應(yīng)用與推廣15 HYPERLINK 4.1無向圖的中國郵路問題在實(shí)際生活中的應(yīng)用15 HYPERLINK 4.2有向圖的中國郵路問題在實(shí)際生活中的應(yīng)用21 HYPERLINK 5結(jié)束語23 HYPERLINK 參考文獻(xiàn)24 HYPERLINK 致謝25中國郵路問題及其算法Xxxxxx系本xxxxx班 xxxxxx指導(dǎo)教師： xxxxxxx 摘 要：本文利用圖論中的相關(guān)概念闡述并解決中國郵路問題，通過比較不同路徑，歸納總結(jié)，找到其

3、具體算法，再利用上述方法找到的具體算法，求解實(shí)例，加以驗(yàn)證，然后將其推廣到實(shí)際生活中，幫助人們快速找到歐拉回路，即找到省時(shí)，省力，省錢的最佳路線，對于圖論教學(xué)及理論研究均有一定的指導(dǎo)意義。關(guān)鍵詞：中國郵路，歐拉回路，最佳路線。Chinas postal problem and its algorithmXxxxxxxxxClass xxxxx,The Department of mathematicsInstructor: xxxxxx Abstract: in this paper, using the relevant concepts in this paper, the graph t

4、heory and solve the problem of China post road, through comparing the different paths, sum up, find its specific algorithm, using the above to find the specific algorithm, solving the instance, verified, and then to promote it to real life, to help people quickly find eular loop, namely find to save

5、 time, effort, save money, the best way of the graph theory teaching and theoretical research have certain guiding significance. Key words: China post road, eular circuit, the best route. 1引言 中國郵路問題是我國著名圖論學(xué)者管梅谷教授首先提出并解決的。它起初為了幫助郵遞員選擇一條合適道路，使其在完成任務(wù)的同時(shí)所走路程最短，后來其方法在實(shí)際生產(chǎn)生活中有廣泛的應(yīng)用，如郵政部門，掃雪車線路，灑水車路線，警車巡邏路

6、線等，具有很強(qiáng)的實(shí)用價(jià)值，本文緊抓其實(shí)質(zhì)與核心，通過對傳統(tǒng)中國郵路問題研究方法的歸納總結(jié)，幫助人們快速找出歐拉回路，實(shí)現(xiàn)了將數(shù)學(xué)知識應(yīng)用于實(shí)際生活中，服務(wù)于人類。2中國郵路問題2.1圖的概念定義1 二元組稱為圖，其中是非空集合，稱為結(jié)點(diǎn)集，是諸結(jié)點(diǎn)之間邊的集合，常用表示圖。(1) 圖可分為有限圖與無限圖兩類，現(xiàn)只討論,都是有限集，給定某個(gè)圖，如果不加特別說明，認(rèn)為，即結(jié)點(diǎn)數(shù)，邊數(shù)。 (2) 圖的邊可以是有方向的，也可以是無方向的，它們分別稱為有向邊和無向邊，用表示。定義2 的某結(jié)點(diǎn)所關(guān)聯(lián)的邊數(shù)稱為該結(jié)點(diǎn)的度，用表示。定義3 任意兩結(jié)點(diǎn)間最多只有一條邊，且不存在自環(huán)的無向圖稱為簡單圖。性質(zhì)1 設(shè)

7、有個(gè)結(jié)點(diǎn)，條邊，則。性質(zhì)2 中度為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個(gè)。定義4 若圖的每條邊都賦以一個(gè)實(shí)數(shù)作為該邊的權(quán)，則稱是賦權(quán)圖，特別地，如果這些權(quán)都是正實(shí)數(shù)，就稱是正權(quán)圖，權(quán)可以表示該邊的長度，時(shí)間，費(fèi)用或容量等，如下圖2.1所示： 圖2.12.2道路與回路2.2.1 基本概念定義1 有向圖中，若邊序列，其中，滿足是的終點(diǎn),是的始點(diǎn)，就稱是的一條有向道路，如果的終點(diǎn)是的始點(diǎn)，則稱是的一條有向回路。如果中的邊沒有重復(fù)出現(xiàn)，則分別稱為簡單有向道路和簡單有向回路，進(jìn)而，如果中結(jié)點(diǎn)也不重復(fù)出現(xiàn)，又分別稱它們?yōu)槌跫売邢虻缆坊虺跫売邢蚧芈?，簡稱為路或回路。顯然，初級有向道路（回路）一定是簡單有向道路（回路）。如下圖

8、2.2.1(a)所示：圖2.2.1(a)邊序列是有向道路；邊序列是有向回路；邊序列是簡單有向道路；邊序列是簡單有向回路；邊序列是初級有向道路；邊序列是初級有向回路。定義2 無向圖中，若點(diǎn)邊交替序列滿足,是的兩個(gè)端點(diǎn)，則稱是中的一條鏈或道路；如果,則稱是圖2.2.1(b)邊序列是道路；邊序列是回路；邊序列是簡單道路；邊序列是簡單回路；邊序列是初級道路；邊序列是初級回路。定義3 設(shè)是無向圖，若的任意兩結(jié)點(diǎn)之間都存在道路，則稱是連通圖，否則稱為非連通圖。2.2.2歐拉回路定義1 對于連通的無向圖，若存在一簡單回路，它通過的所有邊，則這回路稱為的Euler回路。定理1 無向連通圖存在歐拉回路的充要條件

9、是中各結(jié)點(diǎn)的度都是偶數(shù)。推論1 若無向連通圖中只有2個(gè)度為奇數(shù)的結(jié)點(diǎn)，則存在歐拉道路。推論2 若有向連通圖中各結(jié)點(diǎn)的正、負(fù)度相等，則存在有向歐拉回路。2.3中國郵路問題 中國郵路問題，它是由中國數(shù)學(xué)家管梅谷教授首先提出而得名。設(shè)郵遞員從郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到后返回郵局，要求所走的路徑最短，當(dāng)然如若他所管轄的街道構(gòu)成一歐拉回路，則這歐拉回路便是所求的路徑，如若不然，即存在度數(shù)為奇數(shù)的頂點(diǎn)時(shí)，必然有些街道需要走多于1遍，如何尋求最短的路？（基本思路：根據(jù)歐拉圈原理，用奇偶點(diǎn)圖上作業(yè)法，使郵遞路線為最短）現(xiàn)將中國郵路問題用圖論的語言描述如下：設(shè)是連通圖，而且對于所有的,都賦以

10、權(quán)，求以點(diǎn)出發(fā)，通過所有邊至少一次，最后返回點(diǎn)的回路，使得達(dá)到最小。2.3.1無向圖的中國郵路問題郵遞員從郵局出發(fā)，走完投遞線路后又回到郵局，這就要求郵遞員的行走路徑必須是歐拉圈，但是由于城市街道及郵遞點(diǎn)組成的圖有三種基本類型，相應(yīng)的就有三種類型線路，不管何種類型，歸根到底，都要設(shè)法使之形成歐拉圈。(1)圖里沒有奇次定點(diǎn)。即中各結(jié)點(diǎn)的度都是偶數(shù)，那么一定有歐拉回路，顯然任何一條歐拉回路都是該問題的解。如下圖2.3.1(a)所示：圖2.3.1(a)投遞路線為：或者可為：這時(shí)沒有重復(fù)行走的街道，當(dāng)然郵路最短。(2)圖中只有2個(gè)結(jié)點(diǎn),的度是奇數(shù)，則一定存在從到的一條歐拉道路，它經(jīng)過了的各邊一次。在中

11、再找一條從到的最短道路，則中存在歐拉回路。這樣中的歐拉回路，即對應(yīng)于中的邊重復(fù)一次而其余邊只過一次的回路是一條中國郵路，即最佳郵路。如下圖2.3.1(b)所示：圖2.3.1（b）如圖，是奇次頂點(diǎn)，因此要構(gòu)成一個(gè)歐拉回路，線路必須重復(fù)走一次，這樣存在許多重復(fù)走的方案，例如;等。我們計(jì)算一下重復(fù)走的長度分別為4，6，5，5；當(dāng)然需要重復(fù)走的線路以為最好，故巧加邊，是使其形成歐拉回路的方法，故此時(shí)線路為.總長度為21，且此路線是最短的。(3)圖中度為奇數(shù)的結(jié)點(diǎn)數(shù)多于2個(gè)，則需要添加很多條邊，才能形成歐拉回路，且有幾對奇次頂點(diǎn)，就要加幾條邊，此時(shí)巧加邊問題更加重要。如下圖2.3.1(c)：如圖，有8個(gè)

12、奇次頂點(diǎn)，它們是,.如何巧妙地把這8個(gè)奇次頂點(diǎn)恰當(dāng)?shù)亟M合成4對呢？我們參照上一題的例子，便可將8個(gè)奇次頂點(diǎn)配成以下4對：,.這是必須重復(fù)走的最短線路，且長度為11，最優(yōu)投遞路線總長為60，其中一條最佳路線為2.3.2有向圖的中國郵路問題(1) 圖中含有正度或負(fù)度為0的結(jié)點(diǎn)，此時(shí)不存在最佳郵路。如圖2.3.2(a)所示：圖2.3.2(a)(2) 圖中各結(jié)點(diǎn)的正，負(fù)度相等，此時(shí)中一定存在有向歐拉回路。它過每邊一次且僅一次，因此任意一條歐拉回路都是中國郵路。如下圖2.3.2(b)所示：圖2.3.2(b)(3) 圖不對稱，即存在一些結(jié)點(diǎn)，其中 的值是以為始點(diǎn)的邊的數(shù)目，的值是以為終點(diǎn)的邊的數(shù)目。不妨設(shè)

13、，由于郵遞員要經(jīng)過進(jìn)入的每條邊，因此他一定要重復(fù)走以為始點(diǎn)的某條邊。設(shè)表示邊的重復(fù)次數(shù)，表示該邊的權(quán)，那么中國郵路要選擇重復(fù)一些邊后存在有向歐拉回路，并且使為最小的一個(gè)解，顯然此時(shí)滿足，即.(i)若，表示郵路中要次重復(fù)經(jīng)過所發(fā)出的一些邊，或者說可供應(yīng)個(gè)單位量。(ii)若,表示郵路中要次重復(fù)經(jīng)過進(jìn)入的一些邊，或者說可接收個(gè)單位量。 (iii)若,則稱是中間結(jié)點(diǎn)。由于，所以，這樣可以逐次保證每個(gè)可供應(yīng)點(diǎn)經(jīng)過一些邊向某個(gè)接收點(diǎn)供應(yīng)一個(gè)單位量，最后達(dá)到平衡，或者說這些道路上的邊出現(xiàn)重復(fù)，最后得到的圖是有向歐拉圖，若這些重復(fù)邊的總長最小，它即是最佳郵路。例1 求下圖的中國郵路。解 此題顯然是有向中國郵路

14、問題中的不對稱型，故(1)各結(jié)點(diǎn)的為，。(2)構(gòu)造 圖2.3.2(c) 圖2.3.2(d)(3)得到2條總和最小的道路,；，;故.這樣邊重復(fù)2次，邊重復(fù)1次，得圖2.3.2(d)，其中虛線邊表示重復(fù)1次。(4)圖2.3.2(d)是歐拉圖，其中一條歐拉回路，如就是最佳郵路。3中國郵路問題的算法3.1無向圖的中國郵路問題的算法3.1.1奇偶點(diǎn)圖上作業(yè)法(1)把中所有奇度數(shù)頂點(diǎn)配成對，將每對奇度數(shù)頂點(diǎn)之間的一條路上的每邊改為二重邊，得到一個(gè)新圖,新圖中沒有奇度數(shù)頂點(diǎn)，即為多重Euler圖。 (2)若中某一對頂點(diǎn)之間有多于2條邊連接，則去掉其中的偶數(shù)條邊，留下1條或2條邊連接這兩個(gè)頂點(diǎn)，直到每一對相鄰

15、頂點(diǎn)至多由2條邊連接，得到圖。 (3)檢查的每一個(gè)圈,若某一個(gè)圈上重復(fù)邊的權(quán)和超過此圈權(quán)和的一半，則將進(jìn)行調(diào)整。重復(fù)這一過程，直到對的所有圈，其重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，得到圖。 (4)求的Euler回路。例2 求下圖所示圖的中國郵路。圖G解 圖中有6個(gè)奇度數(shù)頂點(diǎn),.把它們配成三對：與,與,與，在圖中，取一條與的路，把邊,作為重復(fù)邊加入圖中；再取與之間一條路，把邊,作為重復(fù)邊加入圖中，在和之間加一條重復(fù)邊，如圖(2)，這個(gè)圈沒有奇度數(shù)點(diǎn)，是一個(gè)Euler圖。(2) (3)在圖(2)中，頂點(diǎn)與之間有三條重邊，去掉其中兩條，得到圖(3)，該圖仍是一個(gè)Euler圖。在圖(3)中，圈的總權(quán)為2

16、4，而圈上重復(fù)邊的權(quán)和為14，大于該圈總權(quán)的一半，于是去掉邊和上的重復(fù)邊，而在和上加入重復(fù)邊，此時(shí)重復(fù)邊的權(quán)和為10，小于該圈總權(quán)的一半。同理，圈的總權(quán)和為15，去掉邊和上的重復(fù)邊，在邊和上加重復(fù)邊，如下圖(4)：(4) (5)圖(4)中，圈的總權(quán)為15，而重復(fù)邊的權(quán)和為8，從而調(diào)整為圖(5)。圖(5)中,圈的總權(quán)為36,而重復(fù)邊的總權(quán)為20,繼續(xù)調(diào)整為圖(6)：（6）經(jīng)檢驗(yàn)，圖(6)為最優(yōu)方案，其中一條歐拉回路就是最佳郵路。3.1.2最小權(quán)匹配算法(1)確定中度為奇數(shù)的結(jié)點(diǎn)，構(gòu)成。(2)求各結(jié)點(diǎn)在中的最短路徑及其長度。(3)對的結(jié)點(diǎn)進(jìn)行最小權(quán)匹配，即選出個(gè),保證每個(gè)結(jié)點(diǎn)在中只出現(xiàn)一次，同時(shí)滿

17、足這些的總和最小。(4)在最小權(quán)匹配里各所對應(yīng)的路徑中的諸邊在中重復(fù)一次，得到。(5)是歐拉圖，它的一條歐拉回路即為最優(yōu)解。例3 求下圖所示圖的中國郵路。解 顯然此題屬于無向圖的中國郵路問題，故(1)首先找到奇數(shù)結(jié)點(diǎn)，。 (2)求各結(jié)點(diǎn)在中的最短路徑及長度，； ，；，； ，；，； ，；，； ，；，； ，；，； ，；，； ，；，.(3)對的結(jié)點(diǎn)進(jìn)行最小權(quán)匹配，得最佳匹配,。(4)在最小權(quán)匹配里各所對應(yīng)的路徑中的諸邊在中重復(fù)一次，得到下圖。(5)是歐拉圖，故它的一條歐拉回路即為最優(yōu)解。3.1.3破圈法(1)奇點(diǎn)處作出標(biāo)記如加“*”或“o”;(2)求該圖的最小樹（用破圈法，盡可能多的保留與奇點(diǎn)相連的

18、邊）；(3)在最小樹上的奇點(diǎn)處添加重復(fù)邊，以消滅奇點(diǎn)； (4)回到原問題，且按判優(yōu)準(zhǔn)則檢驗(yàn)與調(diào)整，直至最優(yōu)。注1 最小生成樹的求法：設(shè)是連通加權(quán)簡單圖，若不是樹，則中必有回路，我們刪去中含于某回路內(nèi)權(quán)最大的一條邊，所得圖記為，是的連通生成子圖，下一步，若不是樹，又從的某回路內(nèi)刪去權(quán)最大的一條邊，如此下去，最后不能按上述方法刪邊時(shí)，得到的圖便是的一棵生成樹，即是的最小生成樹。例4 求下面圖中的最優(yōu)郵路。解 顯然此題屬于無向圖的中國郵路問題，故(1)先在圖中找到奇點(diǎn)，并記上“o”，如圖(1)：（1）(2)求出該圖最小樹，如圖(2)：（2）(3)在最小樹上添加重復(fù)邊，以消滅奇點(diǎn)，如圖(3)：(3)(

19、4)經(jīng)檢驗(yàn)，此已是最優(yōu)解。此題的一條最優(yōu)路線為3.2有向圖的中國郵路問題的算法對稱有向圖的中國郵路算法較為簡單，下面只研究非對稱有向圖的中國郵路算法，算法如下：(1)計(jì)算各結(jié)點(diǎn)的正，負(fù)度，求出，且。(2)添加一個(gè)超發(fā)點(diǎn)，對滿足的結(jié)點(diǎn)，加入條有向邊，權(quán)均為0；添加一個(gè)超收點(diǎn)，對滿足的結(jié)點(diǎn)，加入條有向邊，權(quán)均為0，得到圖。(3)在中求條過以，為兩端點(diǎn)的形如，每邊一次且僅一次的總和最小的道路，記下中各邊在這些道路中的重復(fù)次數(shù)。(4)計(jì)入各邊的重復(fù)次數(shù)，中存在有向歐拉回路，其中一條即為解。例5 求下圖的中國郵路。解 顯然此題屬于非對稱有向圖的中國郵路問題，故(1)先求各結(jié)點(diǎn)的為，(2)構(gòu)造如下圖(a)

20、：(a)(3)得到2條總和最小的道路,；,;.這樣邊重復(fù)2次，邊重復(fù)1次，得下圖，其中虛線邊表示重復(fù)1次。(4)上圖即為歐拉圖，其中一條歐拉回路如 就是最佳郵路。4中國郵路問題在實(shí)際生活中的應(yīng)用與推廣4.1無向圖的中國郵路問題在實(shí)際生活中的應(yīng)用例6 如下圖(1)所示是忻州師范學(xué)院主區(qū)俯視圖，圖(2)是校內(nèi)主干道的簡略圖，其中每條道路上至少有一個(gè)垃圾筒，收垃圾大叔每天需將校內(nèi)所有的垃圾倒掉，下圖中各邊上的數(shù)字表示在此條路上完成任務(wù)所需時(shí)間（單位為分鐘），問如何設(shè)計(jì)路線才能使大叔在完成任務(wù)的同時(shí)，所用時(shí)間最短？ (1) (2)分析 我們把這個(gè)問題抽象成上圖(2)所示，其中的結(jié)點(diǎn)表示幾條相交道路的交

21、點(diǎn)，各道路可用交點(diǎn)間的邊表示，于是此問題就等價(jià)于圖中是否存在經(jīng)過圖的每邊一次且僅一次的閉跡問題。方法一 用奇偶點(diǎn)圖上作業(yè)法解 在中有6個(gè)奇度數(shù)頂點(diǎn),.把它們配成三對:與,與,與.在中，取一條連接與的路，并把邊，作為重復(fù)邊加入圖中；再將與間一條路，把邊，作為重復(fù)邊加入圖中，在與之間加一條重復(fù)邊，如下圖(a)中，這個(gè)圖中沒有奇度數(shù)點(diǎn)，是一個(gè)Euler圖。 (a) (b)在圖(a)中，頂點(diǎn)，間有三條重邊，去掉其中兩條，得到圖(b)，該圖仍是一個(gè)Euler圖。在圖(b)中，圈的總權(quán)為6，而重復(fù)邊的權(quán)和為2，小于該圈總權(quán)的一半；圈的總權(quán)為11，而重復(fù)邊的權(quán)和為4，小于該圈總權(quán)的一半；圈的總權(quán)為8，而重復(fù)

22、邊的權(quán)和為2，小于該圈總權(quán)的一半；圈的總權(quán)為12，而重復(fù)邊的權(quán)和為6，等于該圈總權(quán)的一半；圈的總權(quán)為16，而重復(fù)邊的權(quán)和為8，等于該圈總權(quán)的一半；圈的總權(quán)為20，而重復(fù)邊的權(quán)和為6，小于該圈總權(quán)的一半。由此看來，在每個(gè)圈上，都滿足重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，故圖(b)為最優(yōu)方案，其中一條歐拉回路即為最佳郵路，如即為一條最優(yōu)郵路，且最短時(shí)間為49。方法二 最小權(quán)匹配算法解 顯然此題屬于無向圖的中國郵路問題，故(1)先找出奇數(shù)結(jié)點(diǎn)； (2)再求各結(jié)點(diǎn)在中的最短路徑及長度， ， ； ，； ，； ，； ，； ，； ，； ，； ，；，； ，；，；，； ，；，。對的結(jié)點(diǎn)進(jìn)行最小權(quán)匹配，得最佳匹配為與

23、,與,與,在最小權(quán)匹配里各所對應(yīng)的路徑中的諸邊在中重復(fù)一次，得到上圖(b)，且其為歐拉圖，故它的一條歐拉回路即為最優(yōu)郵路。方法三 用破圈法來求解此題解 顯然此題屬于無向圖的中國郵路問題，故(1)先在圖中找出奇點(diǎn)，并記上“o”,如下圖(a)：(2)求出該圖最小樹，如下圖(b)： (a) (b) (3)在最小樹上添加重復(fù)邊，以消滅奇點(diǎn),如圖(c)： (c)(4)經(jīng)檢驗(yàn)，此解已是最優(yōu)解，其中任意一條歐拉回路即為最優(yōu)解，如 即為解，且最短時(shí)間為49。例7 下圖是忻州師院校內(nèi)某超市的內(nèi)部過道，剛剛開學(xué)時(shí)，某同學(xué)需要購買的物品比較多，下圖中的數(shù)字表示在此貨架上尋找自己所需物品的時(shí)間（單位為分鐘），問若他能

24、一次性購齊所有物品，如何規(guī)劃路線能使其所用時(shí)間最短？分析 本題用上述的三種方法均可求解，下面用破圈法為例解決此題。解 (1)先找到圖中的奇點(diǎn)，并記上“o”，如圖(a)所示：(a)(2)求出該圖的最小樹，如圖(b)所示：（方法用破圈法）(b)(3)在最小樹上添加重復(fù)邊，以消滅奇點(diǎn),如圖(c)：(c)(4)經(jīng)檢驗(yàn)，此解已是最優(yōu)解，如 就是一條最優(yōu)中國郵路，且最短用時(shí)為41。4.2有向圖的中國郵路問題在實(shí)際生活中的應(yīng)用 例8 實(shí)例圖仍為忻州師范學(xué)院，校內(nèi)由于道路較窄，每到開學(xué)季，進(jìn)入校內(nèi)的車輛較多，故每條道路都為單行線，其方向如圖所示，某家長想開車環(huán)游整個(gè)校園，問如何規(guī)劃路線才能使其在不違反規(guī)定的條件下，將校內(nèi)每條道的風(fēng)景都領(lǐng)略到呢？解 顯然此題屬于非對稱有向圖的中國郵路問題，故(1)求得各結(jié)點(diǎn)的為， ，。(2)構(gòu)造如圖(b)：(b)(3)得到4條總和最小的道路,;,;,;,;.這樣邊,各重復(fù)4次，邊,各重復(fù)3次，邊,各重復(fù)2次，邊,各重復(fù)1次，得到下圖(c)，其中虛線邊數(shù)表示重復(fù)次數(shù)。(c)(4)圖(c)是歐拉圖，其中一條歐拉回路即為最佳郵路。5結(jié)束語中國郵路問題是我國著名圖論學(xué)者管梅谷教授首先提出并解決的，后人在其已有的基礎(chǔ)上進(jìn)行了深入研究，取得了矚目的成果，本文通過對不同種情況的詳細(xì)研究與總結(jié)，找到了幾種不同的中國郵路問題的算法，并將其再次應(yīng)用于現(xiàn)實(shí)生