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

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

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

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

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