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

數(shù)學(xué)建模圖論模型第1頁，課件共75頁，創(chuàng)作于2023年2月不積硅步，無以至千里--荀子·勸學(xué)第2頁，課件共75頁，創(chuàng)作于2023年2月1.幾個(gè)引例2.基本概念

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

4.簡單應(yīng)用

第3頁，課件共75頁，創(chuàng)作于2023年2月ABCD哥尼斯堡七橋示意圖問題1:七橋問題

能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點(diǎn)？1.幾個(gè)引例第4頁，課件共75頁，創(chuàng)作于2023年2月七橋問題模擬圖ABDC歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。第5頁，課件共75頁，創(chuàng)作于2023年2月

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

=

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

我的一位學(xué)生今天請我解釋一個(gè)我過去不知道，現(xiàn)在仍不甚了了的事實(shí)。他說如果任意劃分一個(gè)圖形并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子（圖1）?！?頁，課件共75頁，創(chuàng)作于2023年2月問題4(關(guān)鍵路徑問題)

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

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

第9頁，課件共75頁，創(chuàng)作于2023年2月2.圖論的基本概念1)圖的概念2)賦權(quán)圖與子圖3)圖的矩陣表示4)圖的頂點(diǎn)度5)路和連通第10頁，課件共75頁，創(chuàng)作于2023年2月1)圖的概念

定義

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

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

E(G)是頂點(diǎn)集V(G)中的無序或有序的元素偶對表示圖，簡記用第11頁，課件共75頁，創(chuàng)作于2023年2月

定義若一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱其為有限圖.只有一個(gè)頂點(diǎn)的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.第12頁，課件共75頁，創(chuàng)作于2023年2月

定義若圖G中的邊均為有序偶對,稱G為有向邊為無向邊，稱e連接和，頂點(diǎn)和稱圖.稱邊為有向邊或弧,稱是從連接，稱為e的尾，稱為e的頭.若圖G中的邊均為無序偶對，稱G為無向圖.稱為e的端點(diǎn).既有無向邊又有有向邊的圖稱為混合圖.第13頁，課件共75頁，創(chuàng)作于2023年2月

常用術(shù)語1)邊和它的兩端點(diǎn)稱為互相關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱為相鄰的頂點(diǎn)，與同一個(gè)頂點(diǎn)點(diǎn)關(guān)聯(lián)的兩條邊稱為相鄰的邊.3)端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)，端點(diǎn)不相同的邊稱為連桿.4)若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．5)既沒有環(huán)也沒有重邊的圖，稱為簡單圖．第14頁，課件共75頁，創(chuàng)作于2023年2月

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

，且X中任意兩頂點(diǎn)不，

相鄰，Y中任意兩頂點(diǎn)不相鄰，則稱為二部圖或偶圖；若X中每一頂點(diǎn)皆與Y中一切頂點(diǎn)相鄰,稱為完全二部圖或完全偶圖,記為(m=|X|,n=|Y|)．8)圖叫做星.二部圖第15頁，課件共75頁，創(chuàng)作于2023年2月2)賦權(quán)圖與子圖

定義若圖的每一條邊e

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

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

3)若，且，以為頂點(diǎn)集，以兩端點(diǎn)均在中的邊的全體為邊集的圖的子圖，稱為的由導(dǎo)出的子圖，記為.4)若，且，以為邊集，以的端點(diǎn)集為頂點(diǎn)集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.第16頁，課件共75頁，創(chuàng)作于2023年2月3)若，且，以為頂點(diǎn)集，以兩端點(diǎn)均在中的邊的全體為邊集的圖的子圖，稱4)若，且，以為邊集，以的端點(diǎn)集為頂點(diǎn)集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.為的由導(dǎo)出的子圖，記為.第17頁，課件共75頁，創(chuàng)作于2023年2月3)圖的矩陣表示

鄰接矩陣:1)對無向圖，其鄰接矩陣，其中：(以下均假設(shè)圖為簡單圖).第18頁，課件共75頁，創(chuàng)作于2023年2月2)對有向圖,其鄰接矩陣,其中：第19頁，課件共75頁，創(chuàng)作于2023年2月其中：3)對有向賦權(quán)圖,其鄰接矩陣,對于無向賦權(quán)圖的鄰接矩陣可類似定義.第20頁，課件共75頁，創(chuàng)作于2023年2月關(guān)聯(lián)矩陣1)對無向圖，其關(guān)聯(lián)矩陣,其中：第21頁，課件共75頁，創(chuàng)作于2023年2月2)對有向圖，其關(guān)聯(lián)矩陣,其中：第22頁，課件共75頁，創(chuàng)作于2023年2月⑴

鄰接矩陣

A=(aij)n×n,例寫出右圖的鄰接矩陣解：圖的矩陣表示第23頁，課件共75頁，創(chuàng)作于2023年2月⑵權(quán)矩陣A=(aij)n×n例寫出右圖的權(quán)矩陣：解：圖的矩陣表示第24頁，課件共75頁，創(chuàng)作于2023年2月4)圖的頂點(diǎn)度定義1)在無向圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點(diǎn)v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為偶點(diǎn).2)在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn)

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

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

度或次數(shù)．定理的個(gè)數(shù)為偶數(shù)．推論任何圖中奇點(diǎn)第25頁，課件共75頁，創(chuàng)作于2023年2月5)路和連通定義1)無向圖G的一條途徑（或通道或鏈）是指一個(gè)有限非空序列，它的項(xiàng)交替

地為頂點(diǎn)和邊，使得對，的端點(diǎn)是和,稱W是從到的一條途徑，或一條途徑.整數(shù)k稱為W的長.頂點(diǎn)和分別稱為的起點(diǎn)和終點(diǎn),而稱為W的內(nèi)部頂點(diǎn).2)若途徑W的邊互不相同但頂點(diǎn)可重復(fù)，則稱W為跡或簡單鏈.3)若途徑W的頂點(diǎn)和邊均互不相同，則稱W為路或路徑.一條起點(diǎn)為,終點(diǎn)為的路稱為路記為第26頁，課件共75頁，創(chuàng)作于2023年2月定義1)途徑中由相繼項(xiàng)構(gòu)成子序列稱為途徑W的節(jié).

2)起點(diǎn)與終點(diǎn)重合的途徑稱為閉途徑.

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

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

5)若在圖G中頂點(diǎn)u和v是連通的，則頂點(diǎn)u和v之之間的距離d(u,v)是指圖G中最短(u,v)路的長；若沒沒有路連接u和v，則定義為無窮大.第27頁，課件共75頁，創(chuàng)作于2023年2月

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

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

2)在賦權(quán)圖G中，從頂點(diǎn)u到頂點(diǎn)v的具有最小權(quán)定義1)若H是賦權(quán)圖G的一個(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).第33頁，課件共75頁，創(chuàng)作于2023年2月1)賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路假設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均非負(fù)．若，則規(guī)定最短路是一條路，且最短路的任一節(jié)也是最短路．求下面賦權(quán)圖中頂點(diǎn)u0到其余頂點(diǎn)的最短路．第34頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第35頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第36頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第37頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第38頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第39頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第40頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第41頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第42頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第43頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第44頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第45頁，課件共75頁，創(chuàng)作于2023年2月Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對，，且.

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

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

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