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

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

2、對象”，“邊”表示“對象之間的關(guān)系”，引出了“圖”這個概念。4幾個基本概念：圖：由若干個不同的點(diǎn)與連接其中某些頂點(diǎn)的邊所組成的圖形，稱為圖 圖有二要素：“點(diǎn)”和“邊”：“點(diǎn)”表示對象，“邊”反映對象之間的關(guān)系。 （一）圖的概念5環(huán)游與歐拉環(huán)游：（一）圖的概念7七橋問題：（二）歐拉環(huán)游及弗萊里算法 流經(jīng)哥尼斯堡的普雷格河的河灣有兩個小島，七座橋連接了兩岸和小島（如圖1），當(dāng)?shù)亓鱾饕粋€游戲：要求在一次散步中恰好通過每座橋一次。8存在歐拉環(huán)游的條件：（二）歐拉環(huán)游及弗萊里算法一個圖存在歐拉環(huán)游的條件是：網(wǎng)絡(luò)有歐拉環(huán)游當(dāng)且僅當(dāng)中每一點(diǎn)的次為偶數(shù)。 一般地，一個圖能“一筆畫”（不要求回到起點(diǎn)），當(dāng)且僅當(dāng)

3、該圖或沒有奇點(diǎn)，或只有2個奇點(diǎn)。 利用上述結(jié)論，我們判定“七橋問題”不能實(shí)現(xiàn)“一筆畫”，因?yàn)槠邩騿栴}中的圖有4個奇點(diǎn)。 但是要注意，一個圖存在歐拉環(huán)游，如果方法不對，仍然可能找不到具體的歐拉環(huán)游。 10弗萊里算法：（二）歐拉環(huán)游及弗萊里算法11弗萊里算法求歐拉環(huán)游的實(shí)例：（二）歐拉環(huán)游及弗萊里算法A()BA()BAA()BACA()BACDA()BACDEA()BACDECA()BACDECBE()DA以A為起點(diǎn)12奇偶點(diǎn)圖上作業(yè)法：（ 三）中國郵遞員問題奇偶點(diǎn)圖上作業(yè)法口訣：先分奇偶點(diǎn)，奇點(diǎn)對對連；連線不重迭，重迭需改變；圈上連線長，不得過半圈。 14奇偶點(diǎn)圖上作業(yè)法實(shí)例：（ 三）中國郵遞員

4、問題再利用弗萊里算法求得的歐拉環(huán)游即最優(yōu)環(huán)游。此投遞路線的總長度為：71+54+47+26+15=72。15（一）森、樹、生成樹等有關(guān)概念問題的提出：17（一）森、樹、生成樹等有關(guān)概念 一個圖的生成樹可能不只一個，例如右面的一個圖：它有許多生成樹，例如下面每個樹都是它的生成樹：18（二）樹的性質(zhì)19（三）求最小生成樹的三種算法算法一 (克魯斯凱爾，Kruskal)算法二 (普賴姆，Prim)算法三 (破圈法)20算法一 (克魯斯凱爾，Kruskal)算法一(克魯斯凱爾，Kruskal)的中心思想是每次添加權(quán)盡可能小的邊，使新的圖無圈，直至得到生成樹為止。該方法形象地簡稱為“最小邊加入法”。 21算法一 (克魯斯凱爾，Kruskal)e1e2=e3=e4e5e6=e7v4-v3-v5-v6-v7，最短路的長度為1334教材 P106-107 第 1、2、3 、4 題要求：1） 第 4 題主要用程序方法求