歐拉圖的應(yīng)用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 中圖分類號(hào)：O157.6本 科 生 畢 業(yè) 論 文（設(shè)計(jì)） （申請(qǐng)學(xué)士學(xué)位）論文題目 歐拉圖的應(yīng)用 作者姓名 黃 敏 專業(yè)名稱 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 指導(dǎo)教師 王龍芹 2011年6月4日學(xué) 號(hào)：論文答辯日期：2011年6月4日指 導(dǎo) 教 師： （簽字） 滁州學(xué)院本科畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明本人鄭重聲明：所呈交的設(shè)計(jì)（論文）是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果。本人完全意識(shí)到本聲明的法律后果由本人承擔(dān)。作者簽名： 年 月 日目 錄2 3 32.2中國郵路問題及其算法43.1

2、3.2 3.3 3.4 專心-專注-專業(yè)歐拉圖的應(yīng)用摘要：歐拉圖起源于哥尼斯堡七橋問題，通過圖中所有邊一次且僅一次行遍圖中所有頂點(diǎn)的通路稱為歐拉通路，通過圖中所有邊一次并且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。歐拉圖在現(xiàn)實(shí)生活中有著較廣泛的應(yīng)用。本文主要介紹了歐拉圖的研究背景、基本概念和常用的判定定理及算法，并利用中國郵路問題算法來解決牛奶配送問題。通過計(jì)算得出數(shù)據(jù)判斷此算法的優(yōu)缺點(diǎn)。關(guān)鍵詞：歐拉圖；判定定理；中國郵路問題算法；牛奶配送問題中圖分類號(hào)：0157.6Applications of Euler GraphsAbstract：Euler Graph ori

3、ginates from Konigsberg bridges problem. The Euler path is the one which passes through all the sides once as well as all the vertexes at one time in the graph, with which the graph is called Euler graph, and it is widely used in real life. This essay mainly introduces the background of research on

4、Euler graph, its basic concept, the common judgment theorem and algorithm, puts forward solution to the milk distribution problem by making use of the algorithm for Chinese postman problem, and determines the merits and demerits of this algorithm with data stemmed from calculation.Key words: Euler g

5、raph; Judgment theorem; Algorithm for Chinese postman problem; Milk distribution problem1 研究背景與基本概念歐拉圖起源于哥尼斯堡的七橋問題。哥尼斯堡城位于雷格爾河畔，河中有兩個(gè)島嶼，河兩岸與兩島之間通過7座橋彼此相連，如圖1所示。當(dāng)時(shí)，人們熱衷于這樣一個(gè)問題：游人從兩岸A，D 或兩個(gè)小島C、B中任一個(gè)地方出發(fā)，能否找到一條路線，對(duì)每座橋恰通過一次而最后返回原地。問題看來似乎很簡單，但經(jīng)很多人的努力，誰也不能解決這個(gè)問題。公元1 736年，歐拉仔細(xì)研究了這個(gè)問題，他將4塊陸地A、B、C、D分別用4個(gè)點(diǎn)來表示

6、，若兩塊陸地之間有一座橋相連，則在這兩點(diǎn)之間連一條線。于是，哥尼斯堡七橋問題就變成由點(diǎn)和邊所組成的圖(見圖2)的如下問題：是否存在從圖中的任一點(diǎn)出發(fā)，經(jīng)過圖中每條邊一次且僅一次的路線，最后返回到出發(fā)點(diǎn)? 歐拉指出：這樣的路線是不存在的。事實(shí)上，對(duì)每一頂點(diǎn)來說，有一進(jìn)就必須有一出，這樣才能保證從任一點(diǎn)出發(fā)，恰好經(jīng)過每條邊一次，最后返回出發(fā)點(diǎn)。于是從每一頂點(diǎn)所引出的邊均應(yīng)為偶數(shù)，但圖中A、B、D引出的邊均為3條，而C引出的邊為5條，故哥尼斯堡七橋問題無解。下面給出本文經(jīng)常用到的概念：定義 1 C圖：圖論中將圖定義為一個(gè)偶對(duì)，其中表示頂點(diǎn)的集合，是無序組集合的一個(gè)子集合，集合中的元素在中出現(xiàn)不止一次

7、邊的集合。分別用和表示圖的頂點(diǎn)集合與邊的集合。如果和都是有限集合，則稱為有限圖，否則稱為無限圖。若，則稱為階圖。定義 2 平凡圖：只有一個(gè)頂點(diǎn)的圖叫做平凡圖。定義 3 關(guān)聯(lián)：一條邊的端點(diǎn)稱為與這條邊關(guān)聯(lián)。定義 4 連通：設(shè)是圖中的兩個(gè)頂點(diǎn)，若中存在一條道路，則稱頂點(diǎn)和是連通的。定義 5 度:設(shè)中與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目，稱為（在中）的度，記作。定義 6 回路：設(shè)為圖，中頂點(diǎn)與邊的交替序列稱為到的通路，若，則稱通路為回路。(若的所有邊各異，則稱為簡單回路。)定義7 通過圖中所有邊一次且僅一次行遍圖中所有頂點(diǎn)的通路稱為歐拉通路，通過圖中所有邊一次并且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的

8、圖稱為歐拉圖。2 預(yù)備知識(shí)2.1歐拉圖的判定定理下面介紹歐拉圖的一些判定定理：定理1(1) 圖是歐拉圖當(dāng)且僅當(dāng)是連通圖，且中沒有奇度頂點(diǎn)。證明：若為平凡圖，結(jié)論顯然成立，下面設(shè)為非平凡圖，設(shè)是條邊的階無向圖。并設(shè)的頂點(diǎn)集。必要性 因?yàn)闉闅W拉圖，所有中存在歐拉回路，設(shè)為中任意一條歐拉回路，都在上，因而連通，所以為連通圖。又，在上每出現(xiàn)一次獲得2度，若出現(xiàn)次就獲得度，即，所以中無奇度頂點(diǎn)。充分性 由于為非平凡的連通圖可知，中邊數(shù)。對(duì)作歸納法。 (1) 時(shí)，由的連通性及無奇度頂點(diǎn)可知，只能是一個(gè)環(huán)，因而為歐拉圖。 (2) 設(shè)時(shí)結(jié)論成立，要證明是結(jié)論也成立。由的連通性及無奇度頂點(diǎn)可知，。無論是否為簡單

9、圖，都可以證明中必含圈，設(shè)為中一個(gè)圈，刪除上的全部邊，得生成子圖,設(shè)有個(gè)連通分支，每個(gè)連通分支至多有條邊，且無奇度頂點(diǎn)，并且設(shè)與的公共頂點(diǎn)。由歸納假設(shè)可知都是歐拉圖，因而都存在歐拉回路。最后將還原（即將刪除的邊重新加上），并從上的某頂點(diǎn)開始行遍，每遇到，就行遍中的歐拉回路，最后回到，得回路，此回路經(jīng)過中每條邊一次且僅一次并行遍中所有頂點(diǎn)，因而它是中的歐拉回路，故為歐拉圖。2.2中國郵路問題及其算法2.2.1 中國郵路問題中國郵遞員問題3,5,6，是我國管梅谷教授于1960年首先提出而得名。設(shè)郵遞員從郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到目的地后返回郵局，要求所走的路徑最短。當(dāng)然如若他所

10、管轄的街道構(gòu)成一歐拉回路，則這歐拉回路便是所求路徑。如若不然，即存在度數(shù)為奇數(shù)的頂點(diǎn)，必然有些街道需要多走至少1遍，這時(shí)用中國郵路問題算法可求出最短路徑?，F(xiàn)將中國郵路問題用圖論的語言描述如下：設(shè)是連通圖，而且對(duì)于所有的，都賦以權(quán)，求從點(diǎn)出發(fā)，通過所有邊至少一次最后返回點(diǎn)的回路，使得達(dá)到最小。不失一般性，假定圖存在度數(shù)為奇數(shù)的頂點(diǎn)，如若不然，存在一條歐拉回路，它就是所求的郵路。我們可以設(shè)想，有些邊添加若干次使得到得圖的所有頂點(diǎn)的度數(shù)均為偶數(shù)，即為歐拉圖，問題導(dǎo)致求圖的歐拉回路，但圖不再是簡單圖，它具有平行邊，設(shè)邊重復(fù)了次，去掉偶數(shù)條后，仍保持各頂點(diǎn)的度數(shù)為偶數(shù)，即所得到的圖仍是歐拉圖。為使總數(shù)達(dá)

11、到最小，我們不妨假定每條邊重復(fù)數(shù)目不超過1。仍使郵路達(dá)到最短，也就是要求重復(fù)邊的長度達(dá)到最短。設(shè)是所求的重復(fù)邊的集合，使達(dá)到最小，對(duì)于任一簡單回路，可分解為與相交的部分，及其余。2.2.2 引理定理6 (2) 設(shè)是使達(dá)到最小的重復(fù)邊集合，當(dāng)且僅當(dāng)對(duì)于圖的任一回路，恒有。證明：必要性.如若不然，假定存在使，這意味部分的權(quán)超過其余部分的權(quán)，令即。也可作為重復(fù)邊使圖成為歐拉圖。這里是對(duì)稱差。顯然，可使圖的所有頂點(diǎn)保持其度數(shù)為偶數(shù)，由于假定 ，故。跟的假設(shè)相矛盾.必要性得到了證明。 注意這里分解為與共同部分，還有其余部分，后者出現(xiàn)在中。 充分性證明。假定存在由的邊作為重復(fù)的邊，滿足定理的條件：對(duì)于任一

12、回路有，可以證明等式 。令 ，則圖沒有度數(shù)為奇數(shù)的頂點(diǎn)，可分解成若干簡單回路 ，或記以 ，則有 。但 ，故 。同理。即，所以。充分得證。2.2.3 算法從上定理的證明過程提供了構(gòu)造中國郵路問題的算法。設(shè)已知圖中頂點(diǎn)的度數(shù)為奇數(shù)的點(diǎn)為。第一步：從1到，引從到得鏈，并對(duì)的每條邊附加一條使成為重復(fù)邊。第二步：檢查圖的每條邊.若添加的重復(fù)邊數(shù)超過1，則除去其中偶數(shù)條，使得每條邊之多有一條添加的邊，且每一個(gè)頂點(diǎn)的度為偶數(shù)，從而得圖。圖中重復(fù)邊的集合記為。第三步：，(a) 若對(duì)于回路有，則作【，轉(zhuǎn)(a)】否則轉(zhuǎn) (b)。(b) 輸出，便是最優(yōu)集。例題：給出中國郵路問題求解的過程。解：圖(a)到圖(e)給出

13、了中國郵路問題的求解過程。(a)便是圖，其中點(diǎn)是度數(shù)為奇數(shù)的點(diǎn)，引重復(fù)邊便得(b)。(b)中不存在重復(fù)邊數(shù)超過1的邊。55433332221V7V6V5V4V3V2V1(a)5534v4v3v25433332221V7V6V5V1 (b) 考察回路 ，由于，不滿足定理的要求，作。得圖(c)，考察(c)中的回路 V5 V65 V3 V25433332221V7V4V1(c)，顯然不滿足定理的要求，作 。修改(c)得圖(d)V5V63V45V3V2543332221V7V1 (d)考察回路 ，。不滿足定理，修改得圖(e)。V4 5V6V5V2V35433332221V7V1 (e)易知，圖(e)滿

14、足定理6，故圖(e)是歐拉回路。3. 牛奶配送問題目前我國絕大數(shù)牛奶生產(chǎn)企業(yè)以人工、憑主觀、靠經(jīng)驗(yàn)對(duì)配送線路進(jìn)行優(yōu)化，也有少部分企業(yè)開始借助于信息技術(shù)實(shí)現(xiàn)配送路線的優(yōu)化工作，但能夠提出完整的物流配送線路優(yōu)化系統(tǒng)9,10,11,12的企業(yè)還非常少。而國外的一些路徑優(yōu)化軟件由于交通規(guī)則、道路規(guī)劃等各方面不符合我國國情，很難符合改革中的中國牛奶的管理流程11，因此牛奶配送路徑優(yōu)化問題已成為制約我國牛奶物流發(fā)展的主要因素之一。目前，國內(nèi)外大多數(shù)研究很難一次形成合適的配送線路，往往需要輔助很多人工干預(yù)和調(diào)整，增加了工作的復(fù)雜性。本文將中國郵路問題引入配送路徑的優(yōu)化中，在郵路問題中引用指派問題來處理奇點(diǎn)對(duì)

15、之間增加重復(fù)邊12的問題，大大簡化了多奇點(diǎn)對(duì)之間增加重復(fù)邊的繁瑣性，試圖尋求一種新的適合我國牛奶配送系統(tǒng)的路徑優(yōu)化方法，并力求有所突破。3.1 牛奶配送路徑優(yōu)化模型本文結(jié)合我國牛奶配送的特點(diǎn)，建立了市區(qū)間的牛奶配送路徑優(yōu)化模型13，其前提條件如下：(1)某市牛奶零售網(wǎng)點(diǎn)分布在全市各地，其總體數(shù)量大致穩(wěn)定；(2)該市根據(jù)配送輻射半徑，將全市劃分多個(gè)配送區(qū)域，并確定每一區(qū)域的配送中心及每個(gè)配送中心所覆蓋的零售網(wǎng)點(diǎn)；(3)零售網(wǎng)點(diǎn)的配送任務(wù)由所在區(qū)域的牛奶需求量都必須在單車車載量以內(nèi)，區(qū)域內(nèi)各零售網(wǎng)點(diǎn)所在道路的長度可知；(4)配送車輛有某一區(qū)域的配送中心出發(fā)，經(jīng)過該區(qū)域內(nèi)各零售網(wǎng)點(diǎn)，配送完成后車輛返

16、回該物流中心。 符號(hào)規(guī)定如下：為某牛奶配送區(qū)域內(nèi)零售網(wǎng)點(diǎn)的個(gè)數(shù) ； 表示配送路徑是否經(jīng)過個(gè)零售網(wǎng)點(diǎn)；為該區(qū)域零售網(wǎng)點(diǎn)所在道路形成的邊權(quán)連通無向圖；為道路交叉點(diǎn)的集合，點(diǎn)數(shù)，其中表示該區(qū)域的牛奶配送中心；表示中所有道路的集合，道路個(gè)數(shù)，；的長度；、表示中的某兩個(gè)奇點(diǎn)，（）；為從牛奶配送中心出發(fā)經(jīng)過每個(gè)零售網(wǎng)點(diǎn)后重新回到配送中心的一個(gè)配送路徑；表示配送路徑的總長度。3.2 模型描述與建立對(duì)于某一個(gè)牛奶配送區(qū)域，零售網(wǎng)點(diǎn)是固定分布在道路上的，可將配送路徑必須經(jīng)過零售網(wǎng)點(diǎn)的問題轉(zhuǎn)化為必須經(jīng)過零售網(wǎng)點(diǎn)所在道路的問題，這樣如果配送車輛能以最短路線遍行零售網(wǎng)點(diǎn)所在的道路，即能完成送貨任務(wù)。所以在道路可知的邊

17、權(quán)連通無向圖中 目標(biāo)函數(shù)為: 約束條件為： 該問題在本質(zhì)上與中國郵遞員問題是一致的，故我們把該牛奶配送最短路徑問題，轉(zhuǎn)化為求解網(wǎng)絡(luò)圖的中國郵遞員問題。3.3 案例應(yīng)用某市一牛奶企業(yè)的物流配送具有客戶多、批量小、品種多、時(shí)間要求高的特點(diǎn)，該企業(yè)按照單車車載量將本市劃分為多個(gè)區(qū)域，每個(gè)區(qū)域分別由該地區(qū)的配送中心來進(jìn)行分配，如圖1是該牛奶企業(yè)的某個(gè)配送區(qū)域，在該區(qū)域有12個(gè)零售戶，則該配送區(qū)域構(gòu)成如下的邊權(quán)連通無向圖，目前該牛奶企業(yè)在該地區(qū)的配送路線為：配送路徑的長度=70。圖 (a) 構(gòu)成的邊權(quán)連通無向圖(1) 找出奇點(diǎn)及奇點(diǎn)數(shù)表1 各點(diǎn)對(duì)應(yīng)的度數(shù)值奇點(diǎn)度數(shù)3233232334332共有8個(gè)奇點(diǎn)，

18、分別為，引重復(fù)邊 便得圖(f)。(f)中不存在重復(fù)邊數(shù)超過1的邊。(2)考察回路 圖 (f)利用中國郵路算法，考察圖(f)中回路，不滿足定理的要求，作，。得圖(m)圖 (g)考察圖(m)中回路，。滿足定理， 。滿足定理，。滿足定理，。也滿足定理。在郵路圖中對(duì)每個(gè)配對(duì)奇點(diǎn)之間按照最短路徑添加重復(fù)邊,此圖中已沒有奇點(diǎn),并且滿足定理6。如圖(g)所示。在圖(k)中,此時(shí)配送路徑的長度, 即為該配送區(qū)域的最短路徑，從配送中心出發(fā)找出歐拉回路：此回路即該配送區(qū)域內(nèi)送貨車輛的最短行駛路線。顯然，求出的最短配送路徑遠(yuǎn)遠(yuǎn)小于目前該牛奶公司的配送路徑長度?？紤]到現(xiàn)實(shí)配送過程所耗費(fèi)的人員和車輛等費(fèi)用后，該牛奶公司

19、改用最短配送路徑后可大大提高配送的效率，并將節(jié)省大量物流成本。3.4 結(jié)論利用中國郵路問題的最短路徑算法，能快速求出每個(gè)牛奶配送區(qū)域內(nèi)的最短路徑和最優(yōu)路線，使得牛奶配送路徑的實(shí)時(shí)計(jì)算成為現(xiàn)實(shí)，其成果在牛奶的區(qū)域配送系統(tǒng)中具有普遍適用性和廣闊的應(yīng)用前景.但是該方法的主要困難在于檢查回路，當(dāng)圖中點(diǎn)、邊數(shù)較多時(shí)，回路的個(gè)數(shù)將會(huì)很多。給算法增加復(fù)雜度和計(jì)算量。參考文獻(xiàn)1，耿素云，張立昂，離散數(shù)學(xué)M. 北京：高等教育出版社， 2008: 128-170.2盧開澄，盧華明，圖論及其應(yīng)用M.北京：清華大學(xué)出版社，1998: 26-2.3王朝瑞，圖論M，北京：北京理工大學(xué)出版社，2004：41-51.4周炳生， 高向陽， 哈密頓圖和歐拉圖的一種判別方法J. 廣西科學(xué)院學(xué)報(bào)， 2006（01）: 1-5.5王淑棟， 鄭惠琴， 關(guān)于歐拉圖的一個(gè)猜想的新結(jié)果J. 山東礦業(yè)學(xué)院學(xué)報(bào)， 1999(1): 90-95.6陳顯強(qiáng)，吳集林，論哈密爾頓圖的判定問題J. 廣東廣播電視大學(xué)學(xué)報(bào)， 2005(1): 106-109.7黃永華， 歐拉圖與哈密頓圖J. 唐山師專學(xué)報(bào)