基于圖論的數(shù)學(xué)建模_第1頁
基于圖論的數(shù)學(xué)建模_第2頁
基于圖論的數(shù)學(xué)建模_第3頁
基于圖論的數(shù)學(xué)建模_第4頁
基于圖論的數(shù)學(xué)建模_第5頁
已閱讀5頁,還剩30頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、1,數(shù)學(xué)建模理論與實(shí)踐, 基于圖論的數(shù)學(xué)建模,2,基于圖論的數(shù)學(xué)建模,一、歐拉環(huán)游問題與中國郵遞員問題 二、最小生成樹模型 三、最短路模型,3,一、歐拉環(huán)游問題與中國郵遞員問題,(一)圖的概念 (二)歐拉環(huán)游及弗萊里算法 (三)中國郵遞員問題,4,(一)圖的概念,問題的提出:,現(xiàn)實(shí)生活中,我們經(jīng)常碰到一些現(xiàn)象,如:在一群人中有些人互相認(rèn)識,有些人互相不認(rèn)識。又如:某航空公司在100個城市之間建立若干航線,某些城市間有直達(dá)航班,而另一些城市間沒有直達(dá)航班等等。以上現(xiàn)象都有共同內(nèi)容:一是有研究的“對象”,如人,城市等;二是這些對象之間存在著某種關(guān)系:如互相認(rèn)識,有直達(dá)航班等。為了表示這些對象以及對

2、象之間的關(guān)系,我們將“點(diǎn)”代表“對象”,“邊”表示“對象之間的關(guān)系”,引出了“圖”這個概念。,5,幾個基本概念:,圖:由若干個不同的點(diǎn)與連接其中某些頂點(diǎn)的邊所組成的圖形,稱為圖,圖有二要素:“點(diǎn)”和“邊”: “點(diǎn)”表示對象,“邊”反映對象之間的關(guān)系。,(一)圖的概念,6,進(jìn)一步的概念:,(一)圖的概念,7,環(huán)游與歐拉環(huán)游:,(一)圖的概念,8,七橋問題:,(二)歐拉環(huán)游及弗萊里算法,流經(jīng)哥尼斯堡的普雷格河的河灣有兩個小島,七座橋連接了兩岸和小島(如圖1),當(dāng)?shù)亓鱾饕粋€游戲:要求在一次散步中恰好通過每座橋一次。,9,七橋問題:,(二)歐拉環(huán)游及弗萊里算法,在這個問題中,我們可以將“兩個小島和兩岸

3、”看成“點(diǎn)”。連接他們之間的“七座橋”看成“邊”,得到圖2。,“七橋問題”可以歸結(jié)為“一筆畫”問題:即能否用一支筆不離開紙面地畫出經(jīng)過所有橋一次的路線。用圖論的術(shù)語,就是一個圖是否存在歐拉環(huán)游?如果有,如何找出來?,10,存在歐拉環(huán)游的條件:,(二)歐拉環(huán)游及弗萊里算法,一個圖存在歐拉環(huán)游的條件是:網(wǎng)絡(luò)有歐拉環(huán)游當(dāng)且僅當(dāng)中每一點(diǎn)的次為偶數(shù)。,一般地,一個圖能“一筆畫”(不要求回到起點(diǎn)),當(dāng)且僅當(dāng)該圖或沒有奇點(diǎn),或只有2個奇點(diǎn)。 利用上述結(jié)論,我們判定“七橋問題”不能實(shí)現(xiàn)“一筆畫”,因?yàn)槠邩騿栴}中的圖有4個奇點(diǎn)。 但是要注意,一個圖存在歐拉環(huán)游,如果方法不對,仍然可能找不到具體的歐拉環(huán)游。,11

4、,弗萊里算法:,(二)歐拉環(huán)游及弗萊里算法,12,弗萊里算法求歐拉環(huán)游的實(shí)例:,(二)歐拉環(huán)游及弗萊里算法,A()B,A()BA,A()BAC,A()BACD,A()BACDE,A()BACDEC,A()BACDECBE()DA,以A為起點(diǎn),13,問題提出:,( 三)中國郵遞員問題,郵遞員從郵局中取出郵件,遞送到不同地點(diǎn),然后再返回郵局。假設(shè)要求他至少一次走過他投遞范圍內(nèi)的每一條街道,我們希望選擇一條盡可能短的路線。 中國郵遞員問題要求的是在具有非負(fù)權(quán)的網(wǎng)絡(luò)中找出一條權(quán)最小的環(huán)游,即最優(yōu)環(huán)游。 如果網(wǎng)絡(luò)存在歐拉環(huán)游,我們可以按照上面的弗萊里算法求得其歐拉環(huán)游。對于一個沒有歐拉環(huán)游的網(wǎng)絡(luò),可以通

5、過添重復(fù)邊的方法使得添加重復(fù)邊后的網(wǎng)絡(luò)具有歐拉環(huán)游。這里的關(guān)鍵問題是要求所添加重復(fù)邊的權(quán)的和盡可能地小。,問題解法:,點(diǎn)數(shù)較多時(shí),可用Edmonds和Johnson算法(這一算法較為復(fù)雜,這里不作介紹); 點(diǎn)數(shù)較少時(shí),可用奇偶點(diǎn)圖上作業(yè)法求解。,14,奇偶點(diǎn)圖上作業(yè)法:,( 三)中國郵遞員問題,奇偶點(diǎn)圖上作業(yè)法口訣: 先分奇偶點(diǎn),奇點(diǎn)對對連; 連線不重迭,重迭需改變; 圈上連線長,不得過半圈。,15,奇偶點(diǎn)圖上作業(yè)法實(shí)例:,( 三)中國郵遞員問題,再利用弗萊里算法求得的歐拉環(huán)游即最優(yōu)環(huán)游。 此投遞路線的總長度為:71+54+47+26+15=72。,16,二、最小生成樹模型,(一)森、樹、生成

6、樹等有關(guān)概念 (二)樹的性質(zhì) (三)求最小生成樹的三種算法,17,(一)森、樹、生成樹等有關(guān)概念,問題的提出:,18,(一)森、樹、生成樹等有關(guān)概念,一個圖的生成樹可能不只一個,例如右面的一個圖:,它有許多生成樹,例如下面每個樹都是它的生成樹:,19,(二)樹的性質(zhì),20,(三)求最小生成樹的三種算法,算法一 (克魯斯凱爾,Kruskal) 算法二 (普賴姆,Prim) 算法三 (破圈法),21,算法一 (克魯斯凱爾,Kruskal),算法一(克魯斯凱爾,Kruskal)的中心思想是每次添加權(quán)盡可能小的邊,使新的圖無圈,直至得到生成樹為止。該方法形象地簡稱為“最小邊加入法”。,22,算法一 (

7、克魯斯凱爾,Kruskal),e1e2=e3=e4e5e6=e7=e8,從e1,e2開始,加入e3,不可,則去掉e3,保留e4、保留e5,加入e8,不可,則去掉e8,加入e7,不可,則去掉e7,加入e6,不可,則去掉e6,實(shí)例:,23,算法二 (普賴姆,Prim),算法二 (普賴姆,Prim)這是一種迭代算法,每進(jìn)行一次迭代將產(chǎn)生組成網(wǎng)絡(luò) N 最小生成樹 T 的一條邊。它是一種“蠶食”性的算法,慢慢擴(kuò)張自己的地盤。,24,算法二 (普賴姆,Prim),實(shí)例:,25,算法三 (破圈法),算法三 (破圈法)就是在圖中任意取一個圈,從圈中去掉權(quán)最大的邊,將這個圈破掉。重復(fù)這個過程,直到圖中沒有圈為止

8、,保留下的邊組成的圖即為最小生成樹。,26,算法三 (破圈法),27,三、最短路模型,(一)有向圖及最短有向路 (二)Dijkstra算法,28,(一)有向圖及最短有向路,問題的提出:,29,(一)有向圖及最短有向路,30,(一)有向圖及最短有向路,31,(一)有向圖及最短有向路,32,(二)Dijkstra算法,Dijkstra(狄克斯特拉)算法是一種求 最短有向路的方法 限于時(shí)間,此方法的介紹省略。 下面補(bǔ)充一種用0-1規(guī)劃的計(jì)算機(jī)方法求解最短有向路,33,(二)Dijkstra算法,求下圖中從v1到v7的最短有向路:,34,(二)Dijkstra算法,! 設(shè)每個有向路用xij來表示,其中

9、i是起點(diǎn)編號、j是終點(diǎn)編號; ! xij非0即1:最短路經(jīng)過此邊時(shí)為1;否則為0, LINGO程序如下; min=2*x12+5*x13+3*x14 +7*x26+2*x23 +5*x36+3*x35 +1*x43+5*x45 +1*x56+7*x57 +5*x67; x12+x13+x14=1; x67+x57=1; x12-x23-x26=0; x23+x13+x43-x35-x36=0; x14-x43-x45=0; x35+x45-x57-x56=0; x26+x36+x56-x67=0; bin(x12);bin(x13);bin(x14);bin(x26);bin(x23);bin(x36); bin(x35);bin(x43);bin(x45);bin(x56);bin(x57);bin(x67); ! 結(jié)果:X14=X43=X35=X56=X67=1,其余為0; ! 此為最

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論