中國郵路問題及其算法-畢業(yè)論文設(shè)計(jì)

PAGEPAGE26目錄1引言 12中國郵路問題 12.1圖的概念 12.2道路與回路 22.2.1基本概念 22.2.2歐拉回路 32.3中國郵路問題 32.3.1無向圖的中國郵路問題 42.3.2有向圖的中國郵路問題 63中國郵路問題的算法 83.1無向圖的中國郵路問題的算法 83.1.1奇偶點(diǎn)圖上作業(yè)法 83.1.2最小權(quán)匹配算法 103.1.3破圈法 123.2有向圖的中國郵路問題的算法 144中國郵路問題在實(shí)際生活中的應(yīng)用與推廣 154.1無向圖的中國郵路問題在實(shí)際生活中的應(yīng)用 154.2有向圖的中國郵路問題在實(shí)際生活中的應(yīng)用 215結(jié)束語 23參考文獻(xiàn) 24致謝 25中國郵路問題及其算法Xxxxxx系本xxxxx班xxxxxx指導(dǎo)教師：xxxxxxx摘要：本文利用圖論中的相關(guān)概念闡述并解決中國郵路問題，通過比較不同路徑，歸納總結(jié)，找到其具體算法，再利用上述方法找到的具體算法，求解實(shí)例，加以驗(yàn)證，然后將其推廣到實(shí)際生活中，幫助人們快速找到歐拉回路，即找到省時，省力，省錢的最佳路線，對于圖論教學(xué)及理論研究均有一定的指導(dǎo)意義。關(guān)鍵詞：中國郵路，歐拉回路，最佳路線。China'spostalproblemanditsalgorithmXxxxxxxxxClassxxxxx,TheDepartmentofmathematicsInstructor:xxxxxxAbstract:inthispaper,usingtherelevantconceptsinthispaper,thegraphtheoryandsolvetheproblemofChinapostroad,throughcomparingthedifferentpaths,sumup,finditsspecificalgorithm,usingtheabovetofindthespecificalgorithm,solvingtheinstance,verified,andthentopromoteittoreallife,tohelppeoplequicklyfindeularloop,namelyfindtosavetime,effort,savemoney,thebestwayofthegraphtheoryteachingandtheoreticalresearchhavecertainguidingsignificance.Keywords:Chinapostroad,eularcircuit,thebestroute.1引言中國郵路問題是我國著名圖論學(xué)者管梅谷教授首先提出并解決的。它起初為了幫助郵遞員選擇一條合適道路，使其在完成任務(wù)的同時所走路程最短，后來其方法在實(shí)際生產(chǎn)生活中有廣泛的應(yīng)用，如郵政部門，掃雪車線路，灑水車路線，警車巡邏路線等，具有很強(qiáng)的實(shí)用價值，本文緊抓其實(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)只討論,都是有限集，給定某個圖，如果不加特別說明，認(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è)有個結(jié)點(diǎn)，條邊，則。性質(zhì)2中度為奇數(shù)的結(jié)點(diǎn)必為偶數(shù)個。定義4若圖的每條邊都賦以一個實(shí)數(shù)作為該邊的權(quán)，則稱是賦權(quán)圖，特別地，如果這些權(quán)都是正實(shí)數(shù)，就稱是正權(quán)圖，權(quán)可以表示該邊的長度，時間，費(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)槌跫売邢虻缆坊虺跫売邢蚧芈?，簡稱為路或回路。顯然，初級有向道路（回路）一定是簡單有向道路（回路）。如下圖2.2.1(a)所示：圖2.2.1(a)邊序列是有向道路；邊序列是有向回路；邊序列是簡單有向道路；邊序列是簡單有向回路；邊序列是初級有向道路；邊序列是初級有向回路。定義2無向圖中，若點(diǎn)邊交替序列滿足,是的兩個端點(diǎn)，則稱是中的一條鏈或道路；如果,則稱是中的一個圈或回路。如下圖2.2.1(b)所示：圖2.2.1(b)邊序列是道路；邊序列是回路；邊序列是簡單道路；邊序列是簡單回路；邊序列是初級道路；邊序列是初級回路。定義3設(shè)是無向圖，若的任意兩結(jié)點(diǎn)之間都存在道路，則稱是連通圖，否則稱為非連通圖。2.2.2歐拉回路定義1對于連通的無向圖，若存在一簡單回路，它通過的所有邊，則這回路稱為的Euler回路。定理1無向連通圖存在歐拉回路的充要條件是中各結(jié)點(diǎn)的度都是偶數(shù)。推論1若無向連通圖中只有2個度為奇數(shù)的結(jié)點(diǎn)，則存在歐拉道路。推論2若有向連通圖中各結(jié)點(diǎn)的正、負(fù)度相等，則存在有向歐拉回路。2.3中國郵路問題中國郵路問題，它是由中國數(shù)學(xué)家管梅谷教授首先提出而得名。設(shè)郵遞員從郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到后返回郵局，要求所走的路徑最短，當(dāng)然如若他所管轄的街道構(gòu)成一歐拉回路，則這歐拉回路便是所求的路徑，如若不然，即存在度數(shù)為奇數(shù)的頂點(diǎn)時，必然有些街道需要走多于1遍，如何尋求最短的路？（基本思路：根據(jù)歐拉圈原理，用奇偶點(diǎn)圖上作業(yè)法，使郵遞路線為最短）現(xiàn)將中國郵路問題用圖論的語言描述如下：設(shè)是連通圖，而且對于所有的,都賦以權(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)投遞路線為：或者可為：這時沒有重復(fù)行走的街道，當(dāng)然郵路最短。(2)圖中只有2個結(jié)點(diǎn),的度是奇數(shù)，則一定存在從到的一條歐拉道路，它經(jīng)過了的各邊一次。在中再找一條從到的最短道路，則中存在歐拉回路。這樣中的歐拉回路，即對應(yīng)于中的邊重復(fù)一次而其余邊只過一次的回路是一條中國郵路，即最佳郵路。如下圖2.3.1(b)所示：圖2.3.1（b）如圖，，是奇次頂點(diǎn)，因此要構(gòu)成一個歐拉回路，線路必須重復(fù)走一次，這樣存在許多重復(fù)走的方案，例如;;;等。我們計(jì)算一下重復(fù)走的長度分別為4，6，5，5；當(dāng)然需要重復(fù)走的線路以為最好，故巧加邊，是使其形成歐拉回路的方法，故此時線路為.總長度為21，且此路線是最短的。(3)圖中度為奇數(shù)的結(jié)點(diǎn)數(shù)多于2個，則需要添加很多條邊，才能形成歐拉回路，且有幾對奇次頂點(diǎn)，就要加幾條邊，此時巧加邊問題更加重要。如下圖2.3.1(c)：圖2.3.1(c)如圖，有8個奇次頂點(diǎn)，它們是,,,,,,,.如何巧妙地把這8個奇次頂點(diǎn)恰當(dāng)?shù)亟M合成4對呢？我們參照上一題的例子，便可將8個奇次頂點(diǎn)配成以下4對：,,,.這是必須重復(fù)走的最短線路，且長度為11，最優(yōu)投遞路線總長為60，其中一條最佳路線為2.3.2有向圖的中國郵路問題(1)圖中含有正度或負(fù)度為0的結(jié)點(diǎn)，此時不存在最佳郵路。如圖2.3.2(a)所示：圖2.3.2(a)(2)圖中各結(jié)點(diǎn)的正，負(fù)度相等，此時中一定存在有向歐拉回路。它過每邊一次且僅一次，因此任意一條歐拉回路都是中國郵路。如下圖2.3.2(b)所示：圖2.3.2(b)(3)圖不對稱，即存在一些結(jié)點(diǎn)，，其中的值是以為始點(diǎn)的邊的數(shù)目，的值是以為終點(diǎn)的邊的數(shù)目。不妨設(shè)，由于郵遞員要經(jīng)過進(jìn)入的每條邊，因此他一定要重復(fù)走以為始點(diǎn)的某條邊。設(shè)表示邊的重復(fù)次數(shù)，表示該邊的權(quán)，那么中國郵路要選擇重復(fù)一些邊后存在有向歐拉回路，并且使為最小的一個解，顯然此時滿足，即.(i)若，表示郵路中要次重復(fù)經(jīng)過所發(fā)出的一些邊，或者說可供應(yīng)個單位量。(ii)若,表示郵路中要次重復(fù)經(jīng)過進(jìn)入的一些邊，或者說可接收個單位量。(iii)若,則稱是中間結(jié)點(diǎn)。由于，所以，這樣可以逐次保證每個可供應(yīng)點(diǎn)經(jīng)過一些邊向某個接收點(diǎn)供應(yīng)一個單位量，最后達(dá)到平衡，或者說這些道路上的邊出現(xiàn)重復(fù)，最后得到的圖是有向歐拉圖，若這些重復(fù)邊的總長最小，它即是最佳郵路。例1求下圖的中國郵路。解此題顯然是有向中國郵路問題中的不對稱型，故(1)各結(jié)點(diǎn)的為，，，。(2)構(gòu)造如下圖2.3.2(c):圖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)之間的一條路上的每邊改為二重邊，得到一個新圖,新圖中沒有奇度數(shù)頂點(diǎn)，即為多重Euler圖。(2)若中某一對頂點(diǎn)之間有多于2條邊連接，則去掉其中的偶數(shù)條邊，留下1條或2條邊連接這兩個頂點(diǎn)，直到每一對相鄰頂點(diǎn)至多由2條邊連接，得到圖。(3)檢查的每一個圈,若某一個圈上重復(fù)邊的權(quán)和超過此圈權(quán)和的一半，則將進(jìn)行調(diào)整。重復(fù)這一過程，直到對的所有圈，其重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，得到圖。(4)求的Euler回路。例2求下圖所示圖的中國郵路。圖G解圖中有6個奇度數(shù)頂點(diǎn),,,,,.把它們配成三對：與,與,與，在圖中，取一條與的路，把邊,,作為重復(fù)邊加入圖中；再取與之間一條路，把邊,,作為重復(fù)邊加入圖中，在和之間加一條重復(fù)邊，如圖(2)，這個圈沒有奇度數(shù)點(diǎn)，是一個Euler圖。(2)(3)在圖(2)中，頂點(diǎn)與之間有三條重邊，去掉其中兩條，得到圖(3)，該圖仍是一個Euler圖。在圖(3)中，圈的總權(quán)為24，而圈上重復(fù)邊的權(quán)和為14，大于該圈總權(quán)的一半，于是去掉邊和上的重復(fù)邊，而在和上加入重復(fù)邊，此時重復(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)匹配，即選出個,保證每個結(jié)點(diǎn)在中只出現(xiàn)一次，同時滿足這些的總和最小。(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)相連的邊）；(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)最大的一條邊，如此下去，最后不能按上述方法刪邊時，得到的圖便是的一棵生成樹，即是的最小生成樹。例4求下面圖中的最優(yōu)郵路。解顯然此題屬于無向圖的中國郵路問題，故(1)先在圖中找到奇點(diǎn)，并記上“o”，如圖(1)：（1）(2)求出該圖最小樹，如圖(2)：（2）(3)在最小樹上添加重復(fù)邊，以消滅奇點(diǎn)，如圖(3)：(3)(4)經(jīng)檢驗(yàn)，此已是最優(yōu)解。此題的一條最優(yōu)路線為3.2有向圖的中國郵路問題的算法對稱有向圖的中國郵路算法較為簡單，下面只研究非對稱有向圖的中國郵路算法，算法如下：(1)計(jì)算各結(jié)點(diǎn)的正，負(fù)度，求出，且。(2)添加一個超發(fā)點(diǎn)，對滿足的結(jié)點(diǎn)，加入條有向邊，權(quán)均為0；添加一個超收點(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)：(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)主干道的簡略圖，其中每條道路上至少有一個垃圾筒，收垃圾大叔每天需將校內(nèi)所有的垃圾倒掉，下圖中各邊上的數(shù)字表示在此條路上完成任務(wù)所需時間（單位為分鐘），問如何設(shè)計(jì)路線才能使大叔在完成任務(wù)的同時，所用時間最短？

(1)(2)分析我們把這個問題抽象成上圖(2)所示，其中的結(jié)點(diǎn)表示幾條相交道路的交點(diǎn)，各道路可用交點(diǎn)間的邊表示，于是此問題就等價于圖中是否存在經(jīng)過圖的每邊一次且僅一次的閉跡問題。方法一用奇偶點(diǎn)圖上作業(yè)法解在中有6個奇度數(shù)頂點(diǎn),,,,,.把它們配成三對:與,與,與.在中，取一條連接與的路，并把邊，作為重復(fù)邊加入圖中；再將與間一條路，把邊，作為重復(fù)邊加入圖中，在與之間加一條重復(fù)邊，如下圖(a)中，這個圖中沒有奇度數(shù)點(diǎn)，是一個Euler圖。(a)(b)在圖(a)中，頂點(diǎn)，間有三條重邊，去掉其中兩條，得到圖(b)，該圖仍是一個Euler圖。在圖(b)中，圈的總權(quán)為6，而重復(fù)邊的權(quán)和為2，小于該圈總權(quán)的一半；圈的總權(quán)為11，而重復(fù)邊的權(quán)和為4，小于該圈總權(quán)的一半；圈的總權(quán)為8，而重復(fù)邊的權(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)的一半。由此看來，在每個圈上，都滿足重復(fù)邊的權(quán)和不超過此圈權(quán)和的一半，故圖(b)為最優(yōu)方案，其中一條歐拉回路即為最佳郵路，如即為一條最優(yōu)郵路，且最短時間為49。方法二最小權(quán)匹配算法解顯然此題屬于無向圖的中國郵路問題，故(1)先找出奇數(shù)結(jié)點(diǎn)；(2)再求各結(jié)點(diǎn)在中的最短路徑及長度，，；，；，；，；，；，；，；，；，；，；，；，；，；，；，。對的結(jié)點(diǎn)進(jìn)行最小權(quán)匹配，得最佳匹配為與,與,與,在最小權(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)解，如即為解，且最短時間為49。例7下圖是忻州師院校內(nèi)某超市的內(nèi)部過道，剛剛開學(xué)時，某同學(xué)需要購買的物品比較多，下圖中的數(shù)字表示在此貨架上尋找自己所需物品的時間（單位為分鐘），問若他能一次性購齊所有物品，如何規(guī)劃路線能使其所用時間最短？分析本題用上述的三種方法均可求解，下面用破圈法為例解決此題。解(1)先找到圖中的奇點(diǎn)，并記上“o”，如圖(a)所示：(a)(2)求出該圖的最小樹，如圖(b)所示：（方法用破圈法）(b)(3)在最小樹上添加重復(fù)邊，以消滅奇點(diǎn),如圖(c)：(c)(4)經(jīng)檢驗(yàn)，此解已是最優(yōu)解，如就是一條最優(yōu)中國郵路，且最短用時為41。4.2有向圖的中國郵路問題在實(shí)際生活中的應(yīng)用例8實(shí)例圖仍為忻州師范學(xué)院，校內(nèi)由于道路較窄，每到開學(xué)季，進(jìn)入校內(nèi)的車輛較多，故每條道路都為單行線，其方向如圖所示，某家長想開車環(huán)游整個校園，問如何規(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í)生活中，尤其以我的大學(xué)校園忻州師范學(xué)院為素材，全面運(yùn)用中國郵路知識進(jìn)行分析，并解決了實(shí)際生活中的最短路問題，為后人學(xué)習(xí)和生活提供幫助。

參考文獻(xiàn)[1]顧守淮.中國郵路問題的一個算法[J].蘭州交通大學(xué)學(xué)報(bào),1992,8(1):10-13.[2]吳杰.求解中國郵遞員問題的一種思路[J].科技資訊,2007,4(5):1-5.[3]吳正奎,王全文,劉振航.中國郵路問題的一個解法[J].運(yùn)籌與管理,2004,3(3):5-9.[4]管梅谷.中國投遞員問題綜述[J].數(shù)學(xué)研究與評論,1984,5(1):18-21.[5]孟亞坤.時間依賴網(wǎng)絡(luò)中國郵路問題的列生成算法[J].大連理工大學(xué),2010,8(11):6-10.[6]孫景昊.時變中國郵路問題的整數(shù)規(guī)劃模型及算法研究[J].大連理工大學(xué),2012,6(3):6-9.[7]耿素云,屈婉玲,王捍平.離散數(shù)學(xué)教程[M].北京:北京大學(xué)出版社,2002.[8]汪海森,林耿,卓彩娥.中國郵遞員問題的匹配算法[J].長江大學(xué)學(xué)院，2013,8(9):12-15.[9]殷劍宏,吳開亞.圖論及其算法[M].北京:中國科學(xué)技術(shù)大學(xué)出版社,2003.[10]戴一奇,胡冠章,陳衛(wèi).圖論與代數(shù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,1995.致謝歲月如梭，短暫而有意義的大學(xué)生活即將結(jié)束，此時看著畢業(yè)設(shè)計(jì)擺在面前，我感慨萬分。它不僅承載了我四年來的學(xué)習(xí)收獲，更讓我學(xué)會了如何求學(xué)、如何進(jìn)行科學(xué)研究甚至如何做人?；叵肫鹚哪甑膶W(xué)習(xí)生活，有太多的人給我以幫助與支持，指導(dǎo)與鼓勵。在此我對我所有的恩師以及所有的同學(xué)們表示我最真誠的謝意！首先衷心感謝我的恩師曹教授對我的悉心教誨與指導(dǎo)！在跟隨曹老師的這段日子里，我不僅跟曹老師學(xué)到了許多專業(yè)知識，同時也學(xué)習(xí)到了她嚴(yán)謹(jǐn)求實(shí)、一絲不茍的治學(xué)態(tài)度和孜孜不倦的偉大精神，它會使我受益終身。在此，我對曹老師的教育與培養(yǎng)表示衷心的感謝！同時我還要感謝學(xué)校領(lǐng)導(dǎo)和數(shù)學(xué)系的師生對我日常生活的關(guān)心和照顧，思想上的啟發(fā)，以及為我提供了如此良好的學(xué)習(xí)環(huán)境。謝謝你們！基于C8051F單片機(jī)直流電動機(jī)反饋控制系統(tǒng)的設(shè)計(jì)與研究基于單片機(jī)的嵌入式Web服務(wù)器的研究MOTOROLA單片機(jī)MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對良率的影響研究基于模糊控制的電阻釬焊單片機(jī)溫度控制系統(tǒng)的研制基于MCS-51系列單片機(jī)的通用控制模塊的研究基于單片機(jī)實(shí)現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調(diào)節(jié)器單片機(jī)控制的二級倒立擺系統(tǒng)的研究基于增強(qiáng)型51系列單片機(jī)的TCP/IP協(xié)議棧的實(shí)現(xiàn)基于單片機(jī)的蓄電池自動監(jiān)測系統(tǒng)基于32位嵌入式單片機(jī)系統(tǒng)的圖像采集與處理技術(shù)的研究基于單片機(jī)的作物營養(yǎng)診斷專家系統(tǒng)的研究基于單片機(jī)的交流伺服電機(jī)運(yùn)動控制系統(tǒng)研究與開發(fā)基于單片機(jī)的泵管內(nèi)壁硬度測試儀的研制基于單片機(jī)的自動找平控制系統(tǒng)研究基于C8051F040單片機(jī)的嵌入式系統(tǒng)開發(fā)基于單片機(jī)的液壓動力系統(tǒng)狀態(tài)監(jiān)測儀開發(fā)模糊Smith智能控制方法的研究及其單片機(jī)實(shí)現(xiàn)一種基于單片機(jī)的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機(jī)的在線間歇式濁度儀的研制基于單片機(jī)的噴油泵試驗(yàn)臺控制器的研制基于單片機(jī)的軟起動器的研究和設(shè)計(jì)基于單片機(jī)控制的高速快走絲電火花線切割機(jī)床短循環(huán)走絲方式研究基于單片機(jī)的機(jī)電產(chǎn)品控制系統(tǒng)開發(fā)基于PIC單片機(jī)的智能手機(jī)充電器基于單片機(jī)的實(shí)時內(nèi)核設(shè)計(jì)及其應(yīng)用研究基于單片機(jī)的遠(yuǎn)程抄表系統(tǒng)的設(shè)計(jì)與研究基于單片機(jī)的煙氣二氧化硫濃度檢測儀的研制基于微型光譜儀的單片機(jī)系統(tǒng)單片機(jī)系統(tǒng)軟件構(gòu)件開發(fā)的技術(shù)研究基于單片機(jī)的液體點(diǎn)滴速度自動檢測儀的研制基于單片機(jī)系統(tǒng)的多功能溫度測量儀的研制基于PIC單片機(jī)的電能采集終端的設(shè)計(jì)和應(yīng)用基于單片機(jī)的光纖光柵解調(diào)儀的研制氣壓式線性摩擦焊機(jī)單片機(jī)控制系統(tǒng)的研制基于單片機(jī)的數(shù)字磁通門傳感器基于單片機(jī)的旋轉(zhuǎn)變壓器-數(shù)字轉(zhuǎn)換器的研究基于單片機(jī)的光纖Bragg光柵解調(diào)系統(tǒng)的研究單片機(jī)控制的便攜式多功能乳腺治療儀的研制基于C8051F020單片機(jī)的多生理信號檢測儀基于單片機(jī)的電機(jī)運(yùn)動控制系統(tǒng)設(shè)計(jì)Pico專用單片機(jī)核的可測性設(shè)計(jì)研究基于MCS-51單片機(jī)的熱量計(jì)基于雙單片機(jī)的智能遙測微型氣象站MCS-51單片機(jī)構(gòu)建機(jī)器人的實(shí)踐研究基于單片機(jī)的輪軌力檢測基于單片機(jī)的GPS定位儀的研究與實(shí)現(xiàn)基于單片機(jī)的電液伺服控制系統(tǒng)用于單片機(jī)系統(tǒng)的MMC卡文件系統(tǒng)研制基于單片機(jī)的時控和計(jì)數(shù)系統(tǒng)性能優(yōu)化的研究基于單片機(jī)和CPLD的粗光柵位移測量系統(tǒng)研究單片機(jī)控制的后備式方波UPS提升高職學(xué)生單片機(jī)應(yīng)用能力的探究基于單片機(jī)控制的自動低頻減載裝置研究基于單片機(jī)控制的水下焊接電源的研究基于單片機(jī)的多通道數(shù)據(jù)采集系統(tǒng)基于uPSD3234單片機(jī)的氚表面污染測量儀的研制基于單片機(jī)的紅外測油儀的研究96系列單片機(jī)仿真器研究與設(shè)計(jì)基于單片機(jī)的單晶金剛石刀具刃磨設(shè)備的數(shù)控改造基于單片機(jī)的溫度智能控制系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)基于MSP430單片機(jī)的電梯門機(jī)控制器的研制基于單片機(jī)的氣體測漏儀的研究基于三菱M16C/6N系列單片機(jī)的CAN/USB協(xié)議轉(zhuǎn)換器基于單片機(jī)和DSP的變壓器油色譜在線監(jiān)測技術(shù)研究基于單片機(jī)的膛壁溫度報(bào)警系統(tǒng)設(shè)計(jì)基于AVR單片機(jī)的低壓無功補(bǔ)償控制器的設(shè)計(jì)基于單片機(jī)船舶電力推進(jìn)電機(jī)監(jiān)測系統(tǒng)基于單片機(jī)網(wǎng)絡(luò)的振動信號的采集系統(tǒng)基于單片機(jī)的大容量數(shù)據(jù)存儲技術(shù)的應(yīng)用研究基于單片機(jī)的疊圖機(jī)研究與教學(xué)方法實(shí)踐基于單片機(jī)嵌入式Web服務(wù)器技術(shù)的研究及實(shí)現(xiàn)基于AT89S52單片機(jī)的通用數(shù)據(jù)采集系統(tǒng)基于單片機(jī)的多道脈沖幅度分析儀研究機(jī)器人旋轉(zhuǎn)電弧傳感角焊縫跟蹤單片機(jī)控制系統(tǒng)基于單片機(jī)的控制系統(tǒng)在PLC虛擬教學(xué)實(shí)驗(yàn)中的應(yīng)用研究基于單片機(jī)系統(tǒng)的網(wǎng)絡(luò)通信研究與應(yīng)用基于PIC16F877單片機(jī)的莫爾斯碼自動譯碼系統(tǒng)設(shè)計(jì)與研究基于單片機(jī)的模糊控制器在工業(yè)電阻爐上的應(yīng)用研究基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究與開發(fā)基于Cygnal單片機(jī)的μC/OS-Ⅱ的研究基于單片機(jī)的一體化智能差示掃描量熱儀系統(tǒng)研究基于TCP/IP協(xié)議的單片機(jī)與Internet互聯(lián)的研究與實(shí)現(xiàn)變頻調(diào)速液壓電梯單片機(jī)控制器的研究基于單片機(jī)γ-免疫計(jì)數(shù)器自動換樣功能的研究與實(shí)現(xiàn)基于單片機(jī)的倒立擺控制系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)單片機(jī)嵌入式以太網(wǎng)防盜報(bào)警系統(tǒng)基于51單片機(jī)的嵌入式Internet系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)單片機(jī)監(jiān)測系統(tǒng)在擠壓機(jī)上的應(yīng)用MSP430單片機(jī)在智能水表系統(tǒng)上的研究與應(yīng)用基于單片機(jī)的嵌入式系統(tǒng)中TCP/IP協(xié)議棧的實(shí)現(xiàn)與應(yīng)用HYP