基于圖論的數(shù)學(xué)建模

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

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

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

4、,弗萊里算法：,（二）歐拉環(huán)游及弗萊里算法,12,弗萊里算法求歐拉環(huán)游的實例：,（二）歐拉環(huán)游及弗萊里算法,A()B,A()BA,A()BAC,A()BACD,A()BACDE,A()BACDEC,A()BACDECBE()DA,以A為起點,13,問題提出：,（ 三）中國郵遞員問題,郵遞員從郵局中取出郵件，遞送到不同地點，然后再返回郵局。假設(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)的和盡可能地小。,問題解法：,點數(shù)較多時，可用Edmonds和Johnson算法（這一算法較為復(fù)雜，這里不作介紹）； 點數(shù)較少時，可用奇偶點圖上作業(yè)法求解。,14,奇偶點圖上作業(yè)法：,（ 三）中國郵遞員問題,奇偶點圖上作業(yè)法口訣： 先分奇偶點，奇點對對連； 連線不重迭，重迭需改變； 圈上連線長，不得過半圈。,15,奇偶點圖上作業(yè)法實例：,（ 三）中國郵遞員問題,再利用弗萊里算法求得的歐拉環(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,實例：,23,算法二 (普賴姆，Prim),算法二 (普賴姆，Prim)這是一種迭代算法，每進(jìn)行一次迭代將產(chǎn)生組成網(wǎng)絡(luò) N 最小生成樹 T 的一條邊。它是一種“蠶食”性的算法，慢慢擴(kuò)張自己的地盤。,24,算法二 (普賴姆，Prim),實例：,25,算法三 (破圈法),算法三 (破圈法)就是在圖中任意取一個圈，從圈中去掉權(quán)最大的邊，將這個圈破掉。重復(fù)這個過程，直到圖中沒有圈為止

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

9、i是起點編號、j是終點編號; ! xij非0即1：最短路經(jīng)過此邊時為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； ! 此為最