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

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

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

3、”看成“點(diǎn)”。連接他們之間的“七座橋”看成“邊”，得到圖2。,“七橋問(wèn)題”可以歸結(jié)為“一筆畫(huà)”問(wèn)題：即能否用一支筆不離開(kāi)紙面地畫(huà)出經(jīng)過(guò)所有橋一次的路線。用圖論的術(shù)語(yǔ)，就是一個(gè)圖是否存在歐拉環(huán)游？如果有，如何找出來(lái)？,10,存在歐拉環(huán)游的條件：,（二）歐拉環(huán)游及弗萊里算法,一個(gè)圖存在歐拉環(huán)游的條件是：網(wǎng)絡(luò)有歐拉環(huán)游當(dāng)且僅當(dāng)中每一點(diǎn)的次為偶數(shù)。,一般地，一個(gè)圖能“一筆畫(huà)”（不要求回到起點(diǎn)），當(dāng)且僅當(dāng)該圖或沒(méi)有奇點(diǎn)，或只有2個(gè)奇點(diǎn)。 利用上述結(jié)論，我們判定“七橋問(wèn)題”不能實(shí)現(xiàn)“一筆畫(huà)”，因?yàn)槠邩騿?wèn)題中的圖有4個(gè)奇點(diǎn)。 但是要注意，一個(gè)圖存在歐拉環(huán)游，如果方法不對(duì)，仍然可能找不到具體的歐拉環(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,問(wèn)題提出：,（ 三）中國(guó)郵遞員問(wèn)題,郵遞員從郵局中取出郵件，遞送到不同地點(diǎn)，然后再返回郵局。假設(shè)要求他至少一次走過(guò)他投遞范圍內(nèi)的每一條街道，我們希望選擇一條盡可能短的路線。 中國(guó)郵遞員問(wèn)題要求的是在具有非負(fù)權(quán)的網(wǎng)絡(luò)中找出一條權(quán)最小的環(huán)游，即最優(yōu)環(huán)游。 如果網(wǎng)絡(luò)存在歐拉環(huán)游，我們可以按照上面的弗萊里算法求得其歐拉環(huán)游。對(duì)于一個(gè)沒(méi)有歐拉環(huán)游的網(wǎng)絡(luò)，可以通

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

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

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

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

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