數學建模圖論模型(1)數學與統計學院李書選

shuxuanli@126.com/07/17第1頁不積硅步，無以至千里--荀子·勸學第2頁1.幾個引例2.基本概念

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

4.簡單應用

第3頁ABCD哥尼斯堡七橋示意圖問題1:七橋問題

能否從任一陸地出發經過每座橋恰好一次而回到出發點？1.幾個引例第4頁七橋問題模擬圖ABDC歐拉指出：假如每塊陸地所連接橋都是偶數座，則從任一陸地出發，必能經過每座橋恰好一次而回到出發地。第5頁

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

=

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

我一位學生今天請我解釋一個我過去不知道，現在仍不甚了了事實。他說假如任意劃分一個圖形并給各部分著上顏色，使任何含有公共邊界部分顏色不一樣，那么需要且僅需要四種顏色就夠了。下列圖是需要四種顏色例子（圖1）。……第8頁問題4(關鍵路徑問題)

一項工程任務,大到建造一座大壩,一座體育中心,小至組裝一臺機床,一架電視機,都要包含許多工序.這些工序相互約束,只有在一些工序完成之后,一個工序才能開始.即它們之間存在完成先后次序關系,普通認為這些關系是預知,而且也能夠預計完成每個工序所需要時間.

這時工程領導人員迫切希望了解最少需要多少時間才能夠完成整個工程項目,影響工程進度要害工序是哪幾個？

第9頁2.圖論基本概念1)圖概念2)賦權圖與子圖3)圖矩陣表示4)圖頂點度5)路和連通第10頁1)圖概念

定義

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

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

E(G)是頂點集V(G)中無序或有序元素偶對表示圖，簡記用第11頁

定義若一個圖頂點集和邊集都是有限集，則稱其為有限圖.只有一個頂點圖稱為平凡圖，其它全部圖都稱為非平凡圖.第12頁

定義若圖G中邊均為有序偶對,稱G為有向邊為無向邊，稱e連接和，頂點和稱圖.稱邊為有向邊或弧,稱是從連接，稱為e尾，稱為e頭.若圖G中邊均為無序偶對，稱G為無向圖.稱為e端點.現有沒有向邊又有有向邊圖稱為混合圖.第13頁

慣用術語1)邊和它兩端點稱為相互關聯.2)與同一條邊關聯兩個端點稱為相鄰頂點，與同一個頂點點關聯兩條邊稱為相鄰邊.3)端點重合為一點邊稱為環，端點不相同邊稱為連桿.4)若一對頂點之間有兩條以上邊聯結，則這些邊稱為重邊．5)既沒有環也沒有重邊圖，稱為簡單圖．第14頁

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

，且X中任意兩頂點不，

相鄰，Y中任意兩頂點不相鄰，則稱為二部圖或偶圖；若X中每一頂點皆與Y中一切頂點相鄰,稱為完全二部圖或完全偶圖,記為(m=|X|,n=|Y|)．8)圖叫做星.二部圖第15頁2)賦權圖與子圖

定義若圖每一條邊e都賦以一個實數w(e)，稱w(e)為邊e權，G連同邊上權稱為賦權圖.

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

3)若，且，以為頂點集，以兩端點均在中邊全體為邊集圖子圖，稱為由導出子圖，記為.4)若，且，以為邊集，以端點集為頂點集圖子圖，稱為由導出邊導出子圖，記為.第16頁3)若，且，以為頂點集，以兩端點均在中邊全體為邊集圖子圖，稱4)若，且，以為邊集，以端點集為頂點集圖子圖，稱為由導出邊導出子圖，記為.為由導出子圖，記為.第17頁3)圖矩陣表示

鄰接矩陣:1)對無向圖，其鄰接矩陣，其中：(以下均假設圖為簡單圖).第18頁2)對有向圖,其鄰接矩陣,其中：第19頁其中：3)對有向賦權圖,其鄰接矩陣,對于無向賦權圖鄰接矩陣可類似定義.第20頁關聯矩陣1)對無向圖，其關聯矩陣,其中：第21頁2)對有向圖，其關聯矩陣,其中：第22頁⑴

鄰接矩陣

A=(aij)n×n,例寫出右圖鄰接矩陣解：圖矩陣表示第23頁⑵權矩陣A=(aij)n×n例寫出右圖權矩陣：解：圖矩陣表示第24頁4)圖頂點度定義1)在無向圖G中，與頂點v關聯邊數目(環算兩次),稱為頂點v度或次數，記為d(v)或dG(v).稱度為奇數頂點為奇點，度為偶數頂點為偶點.2)在有向圖中，從頂點v引出邊數目稱為頂點

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

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

度或次數．定理個數為偶數．推論任何圖中奇點第25頁5)路和連通定義1)無向圖G一條路徑（或通道或鏈）是指一個有限非空序列，它項交替

地為頂點和邊，使得對，端點是和,稱W是從到一條路徑，或一條路徑.整數k稱為W長.頂點和分別稱為起點和終點,而稱為W內部頂點.2)若路徑W邊互不相同但頂點可重復，則稱W為跡或簡單鏈.3)若路徑W頂點和邊均互不相同，則稱W為路或路徑.一條起點為,終點為路稱為路記為第26頁定義1)路徑中由相繼項組成子序列稱為路徑W節.

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，則定義為無窮大.第27頁

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

7)對于有向圖G，若，且有類似地，可定義有向跡，有向路和有向圈.頭和尾，則稱W為有向路徑.例在右圖中：路徑或鏈：跡或簡單鏈：路或路徑：圈或回路：第28頁例一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河東，因為船小，一次只能帶一物過河，而且，狼與羊，羊與菜不能獨處，給出渡河方法。第29頁解：用四維0-1向量表示（人，狼，羊，菜）在西岸狀態，（在西岸則分量取1，不然取0.）共24=16種狀態，由題設，狀態（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許，從而對應狀態（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許，圖論基本概念第30頁人在河西：（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）人在河東：以十個向量作為頂點，將可能相互轉移狀態連線，則得10個頂點偶圖。問題：怎樣從狀態（1,1,1,1）轉移到（0,0,0,0）？方法：從（1,1,1,1）開始，沿關聯邊抵達沒有抵達相鄰頂點，到（0,0,0,0）終止，得到有向圖即是。圖論基本概念第31頁3．最短路問題及算法最短路問題是圖論應用基本問題，很多實際問題，如線路布設、運輸安排、運輸網絡最小費用流等問題,都可經過建立最短路問題模型來求解.最短路定義最短路問題兩種方法：Dijkstra和Floyd算法.1)求賦權圖中從給定點到其余頂點最短路.2)求賦權圖中任意兩點間最短路.第32頁

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

3)把賦權圖G中一條路權稱為它長，把(u,v)路最小權稱為u和v之間距離，并記作d(u,v).第33頁1)賦權圖中從給定點到其余頂點最短路假設G為賦權有向圖或無向圖，G邊上權均非負．若，則要求最短路是一條路，且最短路任一節也是最短路．求下面賦權圖中頂點u0到其余頂點最短路．第34頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第35頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第36頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第37頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第38頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第39頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第40頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第41頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第42頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第43頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第44頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第45頁Dijkstra算法:求G中從頂點u0到其余頂點最短路.

1)置，對，，且.

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

3)若，則停頓；若，則用i+1代替i，并轉2).第46頁第47頁定義依據頂點v標號l(v)取值路徑，使到v最短路中與v相鄰前一個頂點w，稱為v先驅點，記為z(v),即z(v)=w.先驅點可用于追蹤最短路徑.例5標號過程也可按以下方式進行：首先寫出左圖帶權鄰接矩陣因G是無向圖，故W是對稱陣．第48頁第49頁第50頁Dijkstra算法：求G中從頂點u0到其余頂點最短路設G為賦權有向圖或無向圖，G邊上權均均非負.對每個頂點，定義兩個標識（l