1、數(shù)學(xué)建模圖論模型(1),有圖有真相，有你更精彩,數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 李書選 2012/07/17,不積硅步，無以至千里 -荀子勸學(xué),1. 幾個(gè)引例,2. 基本概念,1. 基本概念,3. 最短路問題及算法,4. 簡(jiǎn)單應(yīng)用,哥尼斯堡七橋示意圖,問題1:七橋問題 能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點(diǎn)？,1. 幾個(gè)引例,七橋問題模擬圖,歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。,萊昂哈德歐拉(Leonhard Euler，1707.4.5-1783.9.18) 瑞士的數(shù)學(xué)家和物理學(xué)家。他被稱為歷史上最偉大的兩位數(shù)學(xué)家之一（另一位是卡爾弗里

2、德里克高斯）。歐拉出生于瑞士，在那里受教育。他是一位數(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ū)者之一。歐拉是有史

3、以來最多產(chǎn)的數(shù)學(xué)家，他的全集共計(jì)75卷。歐拉實(shí)際上支配了18世紀(jì)的數(shù)學(xué)，對(duì)于當(dāng)時(shí)新發(fā)明的微積分，他推導(dǎo)出了很多結(jié)果。在他生命的最后7年中，歐拉的雙目完全失明，盡管如此，他還是以驚人的速度產(chǎn)出了生平一半的著作。 小行星歐拉2002是為了紀(jì)念歐拉而命名的。,萊昂哈德歐拉,問題2:哈密頓圈（環(huán)球旅行游戲） 十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能 否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過每個(gè) 城市恰好一次最后回到出發(fā)點(diǎn)？,問題3:四色問題,對(duì)任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的 國家染不同的顏色，則只需要四種顏色就夠了。,德摩爾根致哈密頓的信（1852年10月23日） 我的一位學(xué)生今天請(qǐng)我解釋一個(gè)我

4、過去不知道，現(xiàn)在仍不甚 了了的事實(shí)。他說如果任意劃分一 個(gè)圖形并給各部分著上顏色，使任 何具有公共邊界的部分顏色不同， 那么需要且僅需要四種顏色就夠了 。下圖是需要四種顏色的例子 （圖1）。 ,問題4(關(guān)鍵路徑問題) 一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺(tái)機(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è)？,2.圖論的基本

5、概念,1) 圖的概念,2) 賦權(quán)圖與子圖,3) 圖的矩陣表示,4) 圖的頂點(diǎn)度,5) 路和連通,1) 圖的概念,定義 一個(gè)圖G是指一個(gè)二元組(V(G),E(G)，其中:,其中元素稱為圖G的頂點(diǎn).,組成的集合，即稱為邊集,其中元素稱為邊.,定義 圖G的階是指圖的頂點(diǎn)數(shù)|V(G)|, 用,來表示；,2) E(G)是頂點(diǎn)集V(G)中的無序或有序的元素偶對(duì),定義 若一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱,其為有限圖. 只有一個(gè)頂點(diǎn)的圖稱為平凡圖，其他的,所有圖都稱為非平凡圖.,定義若圖G中的邊均為有序偶對(duì),稱G為有向,邊 為無向邊，稱e連接 和 ，頂點(diǎn) 和 稱,連接,，稱 為e的尾，稱 為e的頭.,若圖

6、G中的邊均為無序偶對(duì) ，稱G為無向圖.稱,為e的端點(diǎn).,既有無向邊又有有向邊的圖稱為混合圖.,常用術(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) 若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊,稱為重邊,5) 既沒有環(huán)也沒有重邊的圖，稱為簡(jiǎn)單圖,常用術(shù)語,6) 任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖,稱為完全圖. 記為Kv.,7) 若 ， ，且X 中任意兩頂點(diǎn)不,，,相鄰，Y 中任意兩頂點(diǎn)不相鄰，則稱為二部圖或,偶圖；若X中每一頂點(diǎn)皆與Y 中一切頂點(diǎn)相鄰,稱為,完

7、全二部圖或完全偶圖,記為 (m=|X|,n=|Y|),8) 圖 叫做星.,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)出的子圖，記為 .,3) 若 ，且 ，以 為頂點(diǎn)集，以兩端點(diǎn),均在 中的邊的全體為邊集的圖

8、的子圖，稱,4) 若 ，且 ，以 為邊集，以 的端點(diǎn),集為頂點(diǎn)集的圖 的子圖，稱為 的由 導(dǎo)出的,邊導(dǎo)出的子圖，記為 .,為 的由 導(dǎo)出的子圖，記為 .,3) 圖的矩陣表示,鄰接矩陣:,1) 對(duì)無向圖 ，其鄰接矩陣 ，其中：,(以下均假設(shè)圖為簡(jiǎn)單圖).,2) 對(duì)有向圖 ,其鄰接矩陣 ,其中：,其中：,3) 對(duì)有向賦權(quán)圖 , 其鄰接矩陣 ,對(duì)于無向賦權(quán)圖的鄰接矩陣可類似定義.,關(guān)聯(lián)矩陣,1) 對(duì)無向圖 ，其關(guān)聯(lián)矩陣 ,其中：,2) 對(duì)有向圖 ，其關(guān)聯(lián)矩陣 ,其中：, 鄰接矩陣 A = (aij )nn ,例 寫出右圖的鄰接矩陣,解：,圖的矩陣表示, 權(quán)矩陣A = (aij ) nn,例 寫出右圖

9、的權(quán)矩陣：,解：,圖的矩陣表示,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),5) 路和連通,定義1) 無向圖G的一條途徑（或通道或鏈）是指,一個(gè)有限非空序列 ，它的項(xiàng)交替,地為頂點(diǎn)和邊，使得對(duì) ， 的端點(diǎn)是 和 ,稱W是從 到

10、的一條途徑，或一條 途徑. 整,數(shù)k稱為W的長. 頂點(diǎn) 和 分別稱為的起點(diǎn)和終點(diǎn) ,而 稱為W的內(nèi)部頂點(diǎn).,2) 若途徑W的邊互不相同但頂點(diǎn)可重復(fù)，則稱W,為跡或簡(jiǎn)單鏈.,3) 若途徑W的頂點(diǎn)和邊均互不相同，則稱W為路,或路徑. 一條起點(diǎn)為 ,終點(diǎn)為 的路稱為 路,記為,定義,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中

11、最短(u,v)路的長；若沒,沒有路連接u和v，則定義為無窮大.,6) 圖G中任意兩點(diǎn)皆連通的圖稱為連通圖,7) 對(duì)于有向圖G，若 ，且 有,類似地，可定義有向跡，有向路和有向圈.,頭 和尾 ，則稱W為有向途徑.,例 在右圖中：,途徑或鏈：,跡或簡(jiǎn)單鏈：,路或路徑：,圈或回路：,例 一擺渡人欲將一只狼，一頭羊，一籃菜從 河西渡過河到河?xùn)|，由于船小，一次只能帶一物 過河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡 河方法。,解：,用四維0-1向量表示（人，狼，羊，菜）的在西岸 狀態(tài)，（在西岸則分量取1，否則取0.）,共24=16種狀態(tài)，,由題設(shè)，狀態(tài)（0,1,1,0）,(0,0,1,1),(0,1,1,

12、1)是不 允許的，,從而對(duì)應(yīng)狀態(tài)（1,0,0,1），(1,1,0,0),(1,0,0,0)也是 不允許的，,圖論的基本概念,人在河西：,（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）終止，得到有向圖即是。,圖論的基

13、本概念,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)間的最短路.,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

14、,v),路的最小權(quán)稱為u和v之間的距離，并記作 d(u,v).,1) 賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路,假設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均非,負(fù)若 ，則規(guī)定,最短路是一條路，且最短路的任一節(jié)也是最短路,求下面賦權(quán)圖中頂點(diǎn)u0到其余頂點(diǎn)的最短路,Dijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代,替i，并轉(zhuǎn)2).,Dijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,

15、代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代,替i，并轉(zhuǎn)2).,Dijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代,替i，并轉(zhuǎn)2).,Dijkstra算法: 求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.,1) 置 ，對(duì) ， ， 且 .,2) 對(duì)每個(gè) ，用,代替 ，計(jì)算 ，并把達(dá)到這個(gè)最小值的,一個(gè)頂點(diǎn)記為 ，置,3) 若 ，則停止；若 ，則用 i+1 代,替i，并轉(zhuǎn)2).,定義 根據(jù)頂

16、點(diǎn)v的標(biāo)號(hào)l(v)的取值途徑，使 到v,的最短路中與v相鄰的前一個(gè)頂點(diǎn)w，稱為v的先驅(qū),點(diǎn)，記為z(v), 即z(v)=w.,先驅(qū)點(diǎn)可用于追蹤最短路徑. 例5的標(biāo)號(hào)過程也,可按如下方式進(jìn)行：,首先寫出左圖帶權(quán)鄰接矩陣,因G是無向圖，故W是對(duì)稱陣,Dijkstra算法：求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路,設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均均非負(fù).,對(duì)每個(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)號(hào)的

17、頂點(diǎn)集.,輸入: G的帶權(quán)鄰接矩陣 w(u,v),備用-將求最短路與最短路徑結(jié)合起來:,算法步驟：,首先寫出帶權(quán)鄰接矩陣,例 求下圖從頂點(diǎn)u0到其余頂點(diǎn)的最短路,因G是無向圖，故W是對(duì)稱陣,2) 求賦權(quán)圖中任意兩頂點(diǎn)間的最短路,算法的基本思想,（I）求距離矩陣的方法.,（II）求路徑矩陣的方法.,（III）查找最短路路徑的方法.,Floyd算法：求任意兩頂點(diǎn)間的最短路.,舉例說明,算法的基本思想,（I）求距離矩陣的方法.,（II）求路徑矩陣的方法.,在建立距離矩陣的同時(shí)可建立路徑矩陣R,（III）查找最短路路徑的方法.,然后用同樣的方法再分頭查找若：,（IV）Floyd算法：求任意兩頂點(diǎn)間的最短路.,例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑.,插入點(diǎn) v1，得：,矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素.,插入點(diǎn) v2，得：,矩陣