歐拉圖在生活中的應(yīng)用本科畢業(yè)論文-wenkub.com
2025-06-25 15:17 本頁(yè)面
【正文】 同樣也得到了許多同學(xué)的寶貴建議，在此一并致以誠(chéng)摯的謝意。在此向張楠老師表示深深的感謝和崇高的敬意！感謝我的爸爸媽媽，焉的諼草，言樹(shù)之背，養(yǎng)育之恩，無(wú)以回報(bào)，你們永遠(yuǎn)健康快樂(lè)是我最大的心愿。我不是您最出色的學(xué)生，而您卻是我最尊敬的老師。實(shí)用的中國(guó)郵遞員問(wèn)題就是要確定一條包含每條邊最少一次且總權(quán)數(shù)最小的途徑，該問(wèn)題從算法的角度而言也已經(jīng)得到了圓滿的解決。顯然，求出的最短配送路徑遠(yuǎn)遠(yuǎn)小于目前該牛奶公司的配送路徑長(zhǎng)度。也滿足定理。得圖31212511343632431122551圖312考察圖312中回路，。案例應(yīng)用某市一牛奶企業(yè)的物流配送具有客戶多、批量小、品種多、時(shí)間要求高的特點(diǎn)，該企業(yè)按照單車車載量將本市劃分為多個(gè)區(qū)域，每個(gè)區(qū)域分別由該地區(qū)的配送中心來(lái)進(jìn)行分配，如圖1是該牛奶企業(yè)的某個(gè)配送區(qū)域，在該區(qū)域有12個(gè)零售戶，則該配送區(qū)域構(gòu)成如下的邊權(quán)連通無(wú)向圖，目前該牛奶企業(yè)在該地區(qū)的配送路線為：配送路徑的長(zhǎng)12511343632431122551度。牛奶配送路徑優(yōu)化模型本文結(jié)合我國(guó)牛奶配送的特點(diǎn)，建立了市區(qū)間的牛奶配送路徑優(yōu)化模型，其前提條件如下：(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)所在道路的長(zhǎng)度可知；(4)配送車輛有某一區(qū)域的配送中心出發(fā)，經(jīng)過(guò)該區(qū)域內(nèi)各零售網(wǎng)點(diǎn)，配送完成后車輛返回該物流中心。為了在中求出一條起點(diǎn)為，終點(diǎn)為的歐拉跡，在和間添加一條平行邊圖39用算法求出歐拉環(huán)游為：所以：解為：3﹒2牛奶配送問(wèn)題目前我國(guó)絕大數(shù)牛奶生產(chǎn)企業(yè)以人工、憑主觀、靠經(jīng)驗(yàn)對(duì)配送線路進(jìn)行優(yōu)化，也有少部分企業(yè)開(kāi)始借助于信息技術(shù)實(shí)現(xiàn)配送路線的優(yōu)化工作，但能夠提出完整的物流配送線路優(yōu)化系統(tǒng)的企業(yè)還非常少。例8 在下面歐拉圖中求一條歐拉回路。55433332221圖3155345433332221 圖32 考察回路，由于，，不滿足定理的要求，作。例題：給出中國(guó)郵路問(wèn)題求解的過(guò)程。若添加的重復(fù)邊數(shù)超過(guò)1，則出去其中偶數(shù)條，使得每條邊之多有一條添加的邊，且每一個(gè)頂點(diǎn)的度為偶數(shù)，從而得圖。從上定理的證明過(guò)程提供了構(gòu)造中國(guó)郵路問(wèn)題的算法。但，故。注意：這里分解為與共同部分，還有其余部分，后者出現(xiàn)在中。這里是對(duì)稱差。定理7 設(shè)是使達(dá)到最小的重復(fù)邊集合，當(dāng)且僅當(dāng)對(duì)于圖的任一回路，恒有。我們可以設(shè)想，有些邊添加若干次使得到的圖的所有頂點(diǎn)的度數(shù)均為偶數(shù)，即為歐拉圖，問(wèn)題導(dǎo)致求圖的歐拉回路，但圖不再是簡(jiǎn)單圖，它具有平行邊，設(shè)邊重復(fù)了次，去掉偶數(shù)條后，仍保持各頂點(diǎn)的度數(shù)為偶數(shù)，即所得到的圖仍是歐拉圖。當(dāng)然如若他所管轄的街道構(gòu)成一歐拉回路，則這歐拉回路便是所求路徑。設(shè)最短的路最短的路分別為： 那么，由乘積圖的定義：在乘積圖中有路：這樣，我們證明了是連通的且每個(gè)頂點(diǎn)度數(shù)為偶數(shù)。即：在乘積圖中鄰點(diǎn)個(gè)數(shù)等于在中鄰點(diǎn)個(gè)數(shù)與在中鄰點(diǎn)個(gè)數(shù)之和。圖24例6下面圖中誰(shuí)是歐拉圖？誰(shuí)是非歐拉圖但存在歐拉跡？誰(shuí)是非歐拉圖且不存在歐拉跡？圖25 圖26 圖27解：圖25是歐拉圖；圖26是非歐拉圖，但存在歐拉跡；圖27中不存在歐拉跡。例3 設(shè)是歐拉圖，但不是平凡圖，也不是一個(gè)環(huán)則證明：只需證明中不肯能有橋（如何證明？） 圖22 圖23上圖中，圖22，圖23兩圖都是歐拉圖，均從點(diǎn)出發(fā)，如何一次成功地走出一條歐拉回路來(lái)？例4 多米諾骨牌 28塊，能否排成一圈使兩兩相鄰的半邊的點(diǎn)數(shù)相同，問(wèn)是否可能？解答：種例5 “兩只螞蟻比賽問(wèn)題”。解答：在計(jì)算機(jī)領(lǐng)域中，網(wǎng)絡(luò)就是用物理鏈路將各個(gè)孤立的工作站或主機(jī)連在一起，組成數(shù)據(jù)鏈路，從而達(dá)到資源共享和通信的目的。因?yàn)槿χ忻總€(gè)點(diǎn)的度數(shù)是2，已經(jīng)符合歐拉圖的條件，如果再添加邊必須在一個(gè)頂點(diǎn)上再加兩條邊與其相鄰的頂點(diǎn)連接（如圖3所示），這樣才能使之符合歐拉圖的每個(gè)頂點(diǎn)的度均為偶數(shù)的條件。定理4 有向圖是歐拉圖當(dāng)且僅當(dāng)是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度都等于出度?，F(xiàn)在假設(shè)是連通的，且恰好有兩個(gè)奇度頂點(diǎn)和，令是通過(guò)對(duì)增加一條連接和的新邊而得到的一般圖，則是連通的，且此時(shí)的所有頂點(diǎn)都是偶度次的，因此，由定理1，中存在一條歐拉跡。此外，中任均連接意一條開(kāi)歐拉跡和。令是中去掉的邊后得到的一般圖，如果中至少含有一條邊，則它必有一條邊與閉跡中的某個(gè)頂點(diǎn)鄰接，再對(duì)和邊應(yīng)用算法，求得一條包含邊與閉跡，又將和在頂點(diǎn)出拼接，得到一條包含，和的所有邊的閉跡?，F(xiàn)在設(shè)是一個(gè)連通一般圖，且它的每個(gè)頂點(diǎn)都具有偶度次，我們選定的任意一條邊，并應(yīng)用引理
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1