數(shù)學(xué)建模圖論模型

數(shù)學(xué)建模圖論模型第一頁，共七十五頁，編輯于2023年，星期三不積硅步，無以至千里--荀子·勸學(xué)第二頁，共七十五頁，編輯于2023年，星期三1.幾個引例2.基本概念

1.基本概念3.最短路問題及算法

4.簡單應(yīng)用

第三頁，共七十五頁，編輯于2023年，星期三ABCD哥尼斯堡七橋示意圖問題1:七橋問題

能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點？1.幾個引例第四頁，共七十五頁，編輯于2023年，星期三七橋問題模擬圖ABDC歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。第五頁，共七十五頁，編輯于2023年，星期三

萊昂哈德·歐拉(LeonhardEuler，1707.4.5-1783.9.18)瑞士的數(shù)學(xué)家和物理學(xué)家。他被稱為歷史上最偉大的兩位數(shù)學(xué)家之一（另一位是卡爾·弗里德里克·高斯）。歐拉出生于瑞士，在那里受教育。他是一位數(shù)學(xué)神童。作為數(shù)學(xué)教授，他先后任教于圣彼得堡(1727-1741)和柏林，爾后再返圣彼得堡(1766)。歐拉的一生很虔誠。然而，那個廣泛流傳的傳說卻不是真的。傳說中說到，歐拉在葉卡捷琳娜二世的宮廷里，挑戰(zhàn)德尼·狄德羅：“先生，(a+b)n/n

=

x；所以上帝存在，這是回答！”歐拉的離世也很特別：據(jù)說當(dāng)時正是下午茶時間，正在逗孫兒玩的時候，被一塊蛋糕卡在喉頭窒息而死。歐拉是第一個使用“函數(shù)”一詞來描述包含各種參數(shù)的表達(dá)式的人，例如：y=F(x)(函數(shù)的定義由萊布尼茲在1694年給出)。他是把微積分應(yīng)用于物理學(xué)的先驅(qū)者之一。歐拉是有史以來最多產(chǎn)的數(shù)學(xué)家，他的全集共計75卷。歐拉實際上支配了18世紀(jì)的數(shù)學(xué)，對于當(dāng)時新發(fā)明的微積分，他推導(dǎo)出了很多結(jié)果。在他生命的最后7年中，歐拉的雙目完全失明，盡管如此，他還是以驚人的速度產(chǎn)出了生平一半的著作。小行星歐拉2002是為了紀(jì)念歐拉而命名的。萊昂哈德·歐拉第六頁，共七十五頁，編輯于2023年，星期三問題2:哈密頓圈（環(huán)球旅行游戲）十二面體的20個頂點代表世界上20個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？第七頁，共七十五頁，編輯于2023年，星期三問題3:四色問題對任何一張地圖進(jìn)行著色，兩個共同邊界的國家染不同的顏色，則只需要四種顏色就夠了。德·摩爾根致哈密頓的信（1852年10月23日）

我的一位學(xué)生今天請我解釋一個我過去不知道，現(xiàn)在仍不甚了了的事實。他說如果任意劃分一個圖形并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子（圖1）。……第八頁，共七十五頁，編輯于2023年，星期三問題4(關(guān)鍵路徑問題)

一項工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機(jī)床,一架電視機(jī),都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個工序才能開始.即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計完成每個工序所需要的時間.

這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項目,影響工程進(jìn)度的要害工序是哪幾個？

第九頁，共七十五頁，編輯于2023年，星期三2.圖論的基本概念1)圖的概念2)賦權(quán)圖與子圖3)圖的矩陣表示4)圖的頂點度5)路和連通第十頁，共七十五頁，編輯于2023年，星期三1)圖的概念

定義

一個圖G是指一個二元組(V(G),E(G))，其中:其中元素稱為圖G的頂點.組成的集合，即稱為邊集,其中元素稱為邊.

定義圖G的階是指圖的頂點數(shù)|V(G)|,用來表示；圖的邊的數(shù)目|E(G)|用來表示.也用來表示邊是非空有限集，稱為頂點集，1)2)

E(G)是頂點集V(G)中的無序或有序的元素偶對表示圖，簡記用第十一頁，共七十五頁，編輯于2023年，星期三

定義若一個圖的頂點集和邊集都是有限集，則稱其為有限圖.只有一個頂點的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.第十二頁，共七十五頁，編輯于2023年，星期三

定義若圖G中的邊均為有序偶對,稱G為有向邊為無向邊，稱e連接和，頂點和稱圖.稱邊為有向邊或弧,稱是從連接，稱為e的尾，稱為e的頭.若圖G中的邊均為無序偶對，稱G為無向圖.稱為e的端點.既有無向邊又有有向邊的圖稱為混合圖.第十三頁，共七十五頁，編輯于2023年，星期三

常用術(shù)語1)邊和它的兩端點稱為互相關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個端點稱為相鄰的頂點，與同一個頂點點關(guān)聯(lián)的兩條邊稱為相鄰的邊.3)端點重合為一點的邊稱為環(huán)，端點不相同的邊稱為連桿.4)若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．5)既沒有環(huán)也沒有重邊的圖，稱為簡單圖．第十四頁，共七十五頁，編輯于2023年，星期三

常用術(shù)語6)任意兩頂點都相鄰的簡單圖,稱為完全圖.記為Kv.7)若，

，且X中任意兩頂點不，

相鄰，Y中任意兩頂點不相鄰，則稱為二部圖或偶圖；若X中每一頂點皆與Y中一切頂點相鄰,稱為完全二部圖或完全偶圖,記為(m=|X|,n=|Y|)．8)圖叫做星.二部圖第十五頁，共七十五頁，編輯于2023年，星期三2)賦權(quán)圖與子圖

定義若圖的每一條邊e

都賦以一個實數(shù)w(e)，稱w(e)為邊e的權(quán)，G連同邊上的權(quán)稱為賦權(quán)圖.

定義設(shè)和是兩個圖.1)若,稱是的一個子圖,記2)若，，則稱是的生成子圖.

3)若，且，以為頂點集，以兩端點均在中的邊的全體為邊集的圖的子圖，稱為的由導(dǎo)出的子圖，記為.4)若，且，以為邊集，以的端點集為頂點集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.第十六頁，共七十五頁，編輯于2023年，星期三3)若，且，以為頂點集，以兩端點均在中的邊的全體為邊集的圖的子圖，稱4)若，且，以為邊集，以的端點集為頂點集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.為的由導(dǎo)出的子圖，記為.第十七頁，共七十五頁，編輯于2023年，星期三3)圖的矩陣表示

鄰接矩陣:1)對無向圖，其鄰接矩陣，其中：(以下均假設(shè)圖為簡單圖).第十八頁，共七十五頁，編輯于2023年，星期三2)對有向圖,其鄰接矩陣,其中：第十九頁，共七十五頁，編輯于2023年，星期三其中：3)對有向賦權(quán)圖,其鄰接矩陣,對于無向賦權(quán)圖的鄰接矩陣可類似定義.第二十頁，共七十五頁，編輯于2023年，星期三關(guān)聯(lián)矩陣1)對無向圖，其關(guān)聯(lián)矩陣,其中：第二十一頁，共七十五頁，編輯于2023年，星期三2)對有向圖，其關(guān)聯(lián)矩陣,其中：第二十二頁，共七十五頁，編輯于2023年，星期三⑴

鄰接矩陣

A=(aij)n×n,例寫出右圖的鄰接矩陣解：圖的矩陣表示第二十三頁，共七十五頁，編輯于2023年，星期三⑵權(quán)矩陣A=(aij)n×n例寫出右圖的權(quán)矩陣：解：圖的矩陣表示第二十四頁，共七十五頁，編輯于2023年，星期三4)圖的頂點度定義1)在無向圖G中，與頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點為奇點，度為偶數(shù)的頂點為偶點.2)在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點

v的出度，記為d+(v)，從頂點v引入的邊的數(shù)目稱為

v的入度，記為d-(v).稱d(v)=d+(v)+d-(v)為頂點v的

度或次數(shù)．定理的個數(shù)為偶數(shù)．推論任何圖中奇點第二十五頁，共七十五頁，編輯于2023年，星期三5)路和連通定義1)無向圖G的一條途徑（或通道或鏈）是指一個有限非空序列，它的項交替

地為頂點和邊，使得對，的端點是和,稱W是從到的一條途徑，或一條途徑.整數(shù)k稱為W的長.頂點和分別稱為的起點和終點,而稱為W的內(nèi)部頂點.2)若途徑W的邊互不相同但頂點可重復(fù)，則稱W為跡或簡單鏈.3)若途徑W的頂點和邊均互不相同，則稱W為路或路徑.一條起點為,終點為的路稱為路記為第二十六頁，共七十五頁，編輯于2023年，星期三定義1)途徑中由相繼項構(gòu)成子序列稱為途徑W的節(jié).

2)起點與終點重合的途徑稱為閉途徑.

3)起點與終點重合的的路稱為圈(或回路)，長為k的圈稱為k階圈，記為Ck.

4)若在圖G中存在(u,v)路，則稱頂點u和v在圖G中連通.

5)若在圖G中頂點u和v是連通的，則頂點u和v之之間的距離d(u,v)是指圖G中最短(u,v)路的長；若沒沒有路連接u和v，則定義為無窮大.第二十七頁，共七十五頁，編輯于2023年，星期三

6)圖G中任意兩點皆連通的圖稱為連通圖．

7)對于有向圖G，若，且有類似地，可定義有向跡，有向路和有向圈.頭和尾，則稱W為有向途徑.例在右圖中：途徑或鏈：跡或簡單鏈：路或路徑：圈或回路：第二十八頁，共七十五頁，編輯于2023年，星期三例一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河?xùn)|，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨處，給出渡河方法。第二十九頁，共七十五頁，編輯于2023年，星期三解：用四維0-1向量表示（人，狼，羊，菜）的在西岸狀態(tài)，（在西岸則分量取1，否則取0.）共24=16種狀態(tài)，由題設(shè)，狀態(tài)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，從而對應(yīng)狀態(tài)（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許的，圖論的基本概念第三十頁，共七十五頁，編輯于2023年，星期三人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河?xùn)|：以十個向量作為頂點，將可能互相轉(zhuǎn)移的狀態(tài)連線，則得10個頂點的偶圖。問題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？方法：從（1,1,1,1）開始，沿關(guān)聯(lián)邊到達(dá)沒有到達(dá)的相鄰頂點，到（0,0,0,0）終止，得到有向圖即是。圖論的基本概念第三十一頁，共七十五頁，編輯于2023年，星期三3．最短路問題及算法最短路問題是圖論應(yīng)用的基本問題，很多實際問題，如線路的布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費用流等問題,都可通過建立最短路問題模型來求解.最短路的定義最短路問題的兩種方法：Dijkstra和Floyd算法.1)求賦權(quán)圖中從給定點到其余頂點的最短路.2)求賦權(quán)圖中任意兩點間的最短路.第三十二頁，共七十五頁，編輯于2023年，星期三

2)在賦權(quán)圖G中，從頂點u到頂點v的具有最小權(quán)定義1)若H是賦權(quán)圖G的一個子圖，則稱H的各邊的權(quán)和為H的權(quán).類似地，若稱為路P的權(quán)．若P(u,v)是賦權(quán)圖G中從u到v的路,稱的路P*(u,v)，稱為u到v的最短路．

3)把賦權(quán)圖G中一條路的權(quán)稱為它的長，把(u,v)路的最小權(quán)稱為u和v之間的距離，并記作d(u,v).第三十三頁，共七十五頁，編輯于2023年，星期三1)賦權(quán)圖中從給定點到其余頂點的最短路假設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均非負(fù)．若，則規(guī)定最短路是一條路，且最短路的任一節(jié)也是最短路．求下面賦權(quán)圖中頂點u0到其余頂點的最短路．第三十四頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十五頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十六頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十七頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十八頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十九頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第四十頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第四十一頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第四十二頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第四十三頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第四十四頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第四十五頁，共七十五頁，編輯于2023年，星期三Dijkstra算法:求G中從頂點u0到其余頂點的最短路.

1)置，對，，且.

2)對每個，用代替，計算，并把達(dá)到這個最小值的一個頂點記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第四十六頁，共七十五頁，編輯于2023年，星期三第四十七頁，共七十五頁，編輯于2023年，星期三定義根據(jù)頂點v的標(biāo)號l(v)的取值途徑，使到v的最短路中與v相鄰的前一個頂點w，稱為v的先驅(qū)點，記為z(v),即z(v)=w.先驅(qū)點可用于追蹤最短路徑.例5的標(biāo)號過程也可按如下方式進(jìn)行：首先寫出左圖帶權(quán)鄰接矩陣因G是無向圖，故W是對稱陣．第四十八頁，共七十五頁，編輯于2023年，星期三第四十九頁，共七十五頁，編輯于2023年，星期三第五十頁，共七十五頁，編輯于2023年，星期三Dijkstra算法：求G中從頂點u0到其余頂點的最短路設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均均非負(fù).對每個頂點，定義兩個標(biāo)記（l(v)，z(v)），其中:l(v)：表從頂點u0到v的一條路的權(quán)．

z(v)：v的先驅(qū)點，用以確定最短路的路線.l(v)為從頂點u0到v的最短路的權(quán)．算法的過程就是在每一步改進(jìn)這兩個標(biāo)記，使最終S：具有永久標(biāo)號的頂點集.輸入:G的帶權(quán)鄰接矩陣w(u,v)備用-將求最短路與最短路徑結(jié)合起來:第五十一頁，共七十五頁，編輯于2023年，星期三算法步驟：l(v)u0vl(u)uw(u,v)第五十二頁，共七十五頁，編輯于2023年，星期三首先寫出帶權(quán)鄰接矩陣?yán)笙聢D從頂點u0到其余頂點的最短路．因G是無向圖，故W是對稱陣．第五十三頁，共七十五頁，編輯于2023年，星期三第五十四頁，共七十五頁，編輯于2023年，星期三第五十五頁，共七十五頁，編輯于2023年，星期三