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

1、數(shù)學(xué)建模理論與實(shí)踐 基于圖論的數(shù)學(xué)建模1基于圖論的數(shù)學(xué)建模一、歐拉環(huán)游問(wèn)題與中國(guó)郵遞員問(wèn)題二、最小生成樹(shù)模型三、最短路模型2一、歐拉環(huán)游問(wèn)題與中國(guó)郵遞員問(wèn)題（一）圖的概念（二）歐拉環(huán)游及弗萊里算法（三）中國(guó)郵遞員問(wèn)題3（一）圖的概念問(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ì)象之間的關(guān)系，我們將“點(diǎn)”代表“

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

3、該圖或沒(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)游。 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è)法：（ 三）中國(guó)郵遞員問(wèn)題奇偶點(diǎn)圖上作業(yè)法口訣：先分奇偶點(diǎn)，奇點(diǎn)對(duì)對(duì)連；連線不重迭，重迭需改變；圈上連線長(zhǎng)，不得過(guò)半圈。 14奇偶點(diǎn)圖上作業(yè)法實(shí)例：（ 三）中國(guó)郵遞員

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