運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析.ppt
《運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析.ppt》由會員分享,可在線閱讀,更多相關(guān)《運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析.ppt(67頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
引言 圖論是專門研究圖的理論的一門數(shù)學(xué)分支,屬于離散數(shù)學(xué)范疇,與運(yùn)籌學(xué)有交叉,它有200多年歷史,大體可劃分為三個階段:第一階段是從十八世紀(jì)中葉到十九世紀(jì)中葉,處于萌芽階段,多數(shù)問題圍游戲而產(chǎn)生,最有代表性的工作是所謂的Euler七橋問題,即一筆畫問題。,第八章 圖與網(wǎng)絡(luò)分析,第二階段是從十九世紀(jì)中葉到二十世紀(jì)中葉,這時,圖論問題大量出現(xiàn),如Hamilton問題,地圖染色的四色問題以及可平面性問題等,這時,也出現(xiàn)用圖解決實(shí)際問題,如Cayley把樹應(yīng)用于化學(xué)領(lǐng)域,Kirchhoff用樹去研究電網(wǎng)絡(luò)等.,第三階段是二十世紀(jì)中葉以后,由生產(chǎn)管理、軍事、交通、運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)等方面提出實(shí)際問題,以及大型計(jì)算機(jī)使大規(guī)模問題的求解成為可能,特別是以Ford和Fulkerson建立的網(wǎng)絡(luò)流理論,與線性規(guī)劃、動態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透,促進(jìn)了圖論對實(shí)際問題的應(yīng)用。,例:哥尼斯堡七橋問題 哥尼斯堡(現(xiàn)名加里寧格勒)是歐洲一個城市,Pregei河把該城分成兩部分,河中有兩個小島,十八世紀(jì)時,河兩邊及小島之間共有七座橋,當(dāng)時人們提出這樣的問題:有沒有辦法從某處(如A)出發(fā),經(jīng)過各橋一次且僅一次最后回到原地呢?,A,B,C,D,最后,數(shù)學(xué)家Euler在1736年巧妙地給出了這個問題的答案,并因此奠定了圖論的基礎(chǔ),Euler把A、B、C、D四塊陸地分別收縮成四個頂點(diǎn),把橋表示成連接對應(yīng)頂點(diǎn)之間的邊,問題轉(zhuǎn)化為從任意一點(diǎn)出發(fā),能不能經(jīng)過各邊一次且僅一次,最后返回該點(diǎn)。這就是著名的Euler問題。,A,C,B,D,例:哈密頓(Hamilton)回路是十九世紀(jì)英國數(shù)學(xué)家哈密頓提出,給出一個正12面體圖形,共有20個頂點(diǎn)表示20個城市,要求從某個城市出發(fā)沿著棱線尋找一條經(jīng)過每個城市一次而且僅一次,最后回到原處的周游世界線路(并不要求經(jīng)過每條邊)。,圖的基本概念 圖論是專門研究圖的理論的一門數(shù)學(xué)分支,主要研究點(diǎn)和線之間的 幾何關(guān)系。,一、圖與網(wǎng)絡(luò)的基本概念 1、圖及其分類 定義1:(圖)一個圖由點(diǎn)集V和V中的元素?zé)o序?qū)Φ囊粋€集合,記為 G=(V,E) 其中:V= ( v1, v2,. vm)是m個頂點(diǎn)集合; E= ( e1, e2,. en) 是n條邊集合。 當(dāng)V和E為有限集合時,G為有限圖。 2個點(diǎn)u,v屬于V,如果邊(u,v)屬于E, u,v相鄰; u,v為邊(u,v)的端點(diǎn)。 具有公共端點(diǎn)u的兩條邊,稱為點(diǎn)u的關(guān)聯(lián)邊。,第一節(jié) 圖與網(wǎng)絡(luò)的基本知識,如果任一邊(u,v)屬于E且端點(diǎn)無序,無向邊;圖G為無向圖。 如果任一邊(u,v)屬于E且端點(diǎn)有序,有向邊;圖G為有向圖 m(G)= E ,表示圖G的邊數(shù); n(G)= V ,表示圖G的點(diǎn)數(shù);,環(huán)(自回路):一條邊的兩個端點(diǎn)如果相同。 兩個點(diǎn)之間多于一條邊的,多重邊。 定義2:不含環(huán)和多重邊的圖,簡單圖。 含有多重邊的圖,多重圖。 有向圖中的兩點(diǎn)之間有不同方向的兩條邊,不是多重邊。,簡單圖,定義3:每一對頂點(diǎn)間都有邊相連的無向簡單圖,完全圖。 有向完全圖:指每一對頂點(diǎn)間有且僅有一條有向邊的簡單圖。 定義4:圖G=(V,E)的點(diǎn)集V可以分為2個非空子集X,Y,使得E中每條邊的兩個端點(diǎn)必有一個端點(diǎn)屬于X,另一個端點(diǎn)屬于Y,G為二部圖(偶圖),有時記為: G=(X,Y,E),V1,V4,V3,V2,X,Y,2、頂點(diǎn)的次 定義5:以點(diǎn)v為端點(diǎn)的邊的個數(shù)稱為點(diǎn)v的次,記作d(v), 如次為零的點(diǎn)稱為弧立點(diǎn); 次為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的邊稱為懸掛邊。 次為奇數(shù)的點(diǎn)稱為奇點(diǎn),次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。 偶點(diǎn):d(v)=偶數(shù); 奇點(diǎn):d(v)=奇數(shù);,v1,v3,v2,v4,v6,v5,e1,e3,e5,e6,e4,e8,e7,e2,V= ( v1, v2,. v6) E= ( e1, e2,. e8) (e1)= (v1, v2) (e2)= (v1, v2) (e7)= (v3, v5) (e8)= (v4, v4) (e8)= (v4, v4),稱為自回路(環(huán)); v6是孤立點(diǎn),v5為懸掛點(diǎn),e7為懸掛邊,頂點(diǎn)v3的次為4,頂點(diǎn)v4的次為4。,定理1 在一個圖中,所有頂點(diǎn)次的和等于邊的兩倍。 定理2 在任意一個圖中,次為奇數(shù)的頂點(diǎn)必為偶數(shù)個。 定義6:有向圖中,以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次,d+(vi); 以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次,d-(vi); 所有頂點(diǎn)的入次之和=所有頂點(diǎn)的出次之和;,3、子圖 定義:設(shè)G=(V,E)和G1=(V1,E1)。 如果V1 V, E1 E則稱G1為G的子圖; 如果G1 =( V1,E1 )是G=(V,E)子圖,并且V1 = V,則稱G1為G的生成子圖;,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,v1,v5,v4,v2,e1,e5,e3,(a)的子圖,v1,v5,v4,v2,v3,e8,e6,e5,e2,(a)的生成子圖,二、連通圖 定義8:如果圖中的某些點(diǎn)、邊可以排列成點(diǎn)和邊的交錯序列(v0 ,e1 ,v1 ,e2 ,v2,e3 ,v3 ,vn-1 , en , vn ) ,ei=(vi-1,vi),則稱此為一條鏈。 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)邊構(gòu)成的點(diǎn)邊序列。 初等鏈:鏈中無重復(fù)的點(diǎn)和邊; 定義9:無向圖中,如一條鏈中起點(diǎn)和終點(diǎn)重合,則稱此鏈為圈。 初等圈:圈中無重復(fù)的點(diǎn)和邊; 有向圖中,當(dāng)鏈(圈)上的邊方向相同時,為道路(回路)。,道路 道路 回路,鏈、初等鏈、初等圈,道路、回路,連通圖:圖中任意兩點(diǎn)之間均至少有一條通路,否則稱為不連通圖。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向圖,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向圖,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向圖,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向圖,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向圖,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向圖,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,鏈,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,v1,v5,v4,v2,e1,e7,e6,e3,圈,三、圖的矩陣表示 一個圖非常直觀,但是不容易計(jì)算,特別不容易在計(jì)算機(jī)上進(jìn)行計(jì)算,一個有效的解決辦法是將圖表示成矩陣形式,通常采用的矩陣是鄰接矩陣、邊長鄰接矩陣、弧長矩陣和關(guān)聯(lián)矩陣。,1、鄰接矩陣 鄰接矩陣A表示圖G的頂點(diǎn)之間的鄰接關(guān)系,它是一個nxn的矩陣,如果兩個頂點(diǎn)之間有邊相聯(lián)時,記為1,否則為0。,定義12:對于G=(V,E),構(gòu)造矩陣A=(aij)nxn aij= 1, (vi,vj) E 0 矩陣A為鄰接矩陣。,V1,V3,V5,V6,V4,V2,v1 v2 v3 v4 v5 v6,2、權(quán)矩陣 在圖的各邊上一個數(shù)量指標(biāo),具體表示這條邊的權(quán)(距離,單價(jià),通過能力等),以邊長代替鄰接矩陣中的元素得到邊長鄰接矩陣。 定義11:賦權(quán)圖G=(V,E),其邊(vi,vj)有權(quán)wij,構(gòu)造矩陣A=(aij)nxn aij= wij, (vi,vj) E 0 矩陣A為權(quán)矩陣。,v1,v2,v5,v4,v3,9,2,4,3,8,6,7,4,5,v1 v2 v3 v4 v5,四、歐拉回路與中國郵政問題 1、歐拉回路與道路 定義13:連通圖G,如果存在一條道路,經(jīng)過每邊一次且僅一次,則稱這條路為歐拉道路; 如果存在一條回路,經(jīng)過每邊一次且僅一次,則稱這條路為歐拉回路; 具有歐拉回路的圖為歐拉圖。 定理3:無向連接圖G是歐拉圖,當(dāng)且僅當(dāng)G中無奇 點(diǎn)。 推論1:無向連接圖G為歐拉圖,當(dāng)且僅當(dāng)G的邊集可劃為若干個初等回路。 推論2:無向連接圖G為歐拉道路,當(dāng)且僅當(dāng)G恰好有2個奇點(diǎn)。,定理4:連通有向圖G是歐拉圖,當(dāng)且僅當(dāng)它每個奇點(diǎn)的出次等于入次。 2、中國郵路問題 一個郵遞員,從郵局出發(fā),走遍所有街道后回到郵局,如何安排,使其總的路程最短? 圖論:給定一個連通圖,每邊有非負(fù)權(quán),要求一條回路過每邊至少一次,且滿足總權(quán)最小。 定理5:已知圖G*=G+E1無奇點(diǎn),則L(E1)= l(e)最小的充要條件 (1)每條邊最多重復(fù)一次; (2)對圖G中每個初等圈,重復(fù)邊的長度和不超過圈長的1/2;,例:求解網(wǎng)絡(luò)的中國郵路問題,第一步:確定初始可行方案 先檢查圖中是否有奇點(diǎn),如果無奇點(diǎn),為歐拉圖;如果有奇點(diǎn),圖中的奇點(diǎn)的個數(shù)比為偶數(shù)個,所以可以兩兩配對,構(gòu)造二重邊。圖中有4個奇點(diǎn),v2,v4,v6,v8,配對 v2-v4,v6-v8,構(gòu)造二重邊。重復(fù)邊 的總長: 2l23+ 2l36+ l69+ l98+ l23+ 2l87+ 2l74+ l41+ l12=51,第二步:調(diào)整可行方案,使重復(fù)邊最多為一次 重復(fù)邊 的總長: l69+ l98+ l41+ l12=21,第三步:檢查每個初等圈是否 定理?xiàng)l件2,如果不滿足,進(jìn)行 調(diào)整,直至滿足為止。 圈v1v2v5v4v1總長度24,重復(fù)邊14,14/21大于1/2,調(diào)整(v2,v5),(v5,v4)代替(v1,v2),(v1,v4),圈v1v2v5v4v1總長度24, 重復(fù)邊6+4=10,重復(fù)邊 的總長: l69+ l98+ l45+ l52=17 再檢查圈v2v3v6v9v8v5v2總長=24,重復(fù)邊 的長度13,繼續(xù)調(diào)整,再次調(diào)整的重復(fù)邊 的總長:=15,滿足條件要求。 圖中任一歐拉回路為最優(yōu)郵遞回路。 方法:簡單;但要檢查每一個初等圈。,總結(jié):圖的基本概念,G=(V,E),子圖,矩陣表示,含元素的個數(shù),點(diǎn)的次,邊,特殊的圖,點(diǎn)邊關(guān)系,簡單圖,多重圖,連通圖,樹,生成子圖,G=(V,E),矩陣表示 A 鄰接矩陣 B 權(quán)矩陣,邊e=(u,v),關(guān)聯(lián)邊,自回路,多重邊 平行邊,簡單圖,多重圖,0 1 奇數(shù) 偶數(shù),點(diǎn)邊關(guān)系,點(diǎn)邊關(guān)系,生成樹,有向圖,道路、回路,1.思考題 子圖與生成子圖的區(qū)別是什么? 2.討論題 中國郵路問題的解題步驟?,小結(jié): 1.圖的基本知識。 2.圖的矩陣表示。 3.歐拉道路與歐拉回路。,- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
14.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析 運(yùn)籌學(xué) 課件 第八 網(wǎng)絡(luò)分析
鏈接地址:http://ioszen.com/p-2893144.html