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奇偶點圖上作業法8 HYPERLINK 3.1.2

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

3、具體算法，再利用上述方法找到的具體算法，求解實例，加以驗證，然后將其推廣到實際生活中，幫助人們快速找到歐拉回路，即找到省時，省力，省錢的最佳路線，對于圖論教學及理論研究均有一定的指導意義。關鍵詞：中國郵路，歐拉回路，最佳路線。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引言 中國郵路問題是我國著名圖論學者管梅谷教授首先提出并解決的。它起初為了幫助郵遞員選擇一條合適道路，使其在完成任務的同時所走路程最短，后來其方法在實際生產生活中有廣泛的應用，如郵政部門，掃雪車線路，灑水車路線，警車巡邏路

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

7、有個結點，條邊，則。性質2 中度為奇數的結點必為偶數個。定義4 若圖的每條邊都賦以一個實數作為該邊的權，則稱是賦權圖，特別地，如果這些權都是正實數，就稱是正權圖，權可以表示該邊的長度，時間，費用或容量等，如下圖2.1所示： 圖2.12.2道路與回路2.2.1 基本概念定義1 有向圖中，若邊序列，其中，滿足是的終點,是的始點，就稱是的一條有向道路，如果的終點是的始點，則稱是的一條有向回路。如果中的邊沒有重復出現，則分別稱為簡單有向道路和簡單有向回路，進而，如果中結點也不重復出現，又分別稱它們為初級有向道路或初級有向回路，簡稱為路或回路。顯然，初級有向道路（回路）一定是簡單有向道路（回路）。如下圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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