運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析.ppt

《運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《運(yùn)籌學(xué)課件 第八章 圖與網(wǎng)絡(luò)分析.ppt（67頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

引言 圖論是專門研究圖的理論的一門數(shù)學(xué)分支，屬于離散數(shù)學(xué)范疇，與運(yùn)籌學(xué)有交叉，它有200多年歷史，大體可劃分為三個(gè)階段：第一階段是從十八世紀(jì)中葉到十九世紀(jì)中葉，處于萌芽階段，多數(shù)問(wèn)題圍游戲而產(chǎn)生，最有代表性的工作是所謂的Euler七橋問(wèn)題，即一筆畫問(wèn)題。,第八章 圖與網(wǎng)絡(luò)分析,第二階段是從十九世紀(jì)中葉到二十世紀(jì)中葉，這時(shí)，圖論問(wèn)題大量出現(xiàn)，如Hamilton問(wèn)題，地圖染色的四色問(wèn)題以及可平面性問(wèn)題等，這時(shí)，也出現(xiàn)用圖解決實(shí)際問(wèn)題，如Cayley把樹應(yīng)用于化學(xué)領(lǐng)域，Kirchhoff用樹去研究電網(wǎng)絡(luò)等.,第三階段是二十世紀(jì)中葉以后，由生產(chǎn)管理、軍事、交通、運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)等方面提出實(shí)際問(wèn)題，以及大型計(jì)算機(jī)使大規(guī)模問(wèn)題的求解成為可能，特別是以Ford和Fulkerson建立的網(wǎng)絡(luò)流理論，與線性規(guī)劃、動(dòng)態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透，促進(jìn)了圖論對(duì)實(shí)際問(wèn)題的應(yīng)用。,例：哥尼斯堡七橋問(wèn)題 哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個(gè)城市，Pregei河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒(méi)有辦法從某處（如A）出發(fā)，經(jīng)過(guò)各橋一次且僅一次最后回到原地呢？,A,B,C,D,最后，數(shù)學(xué)家Euler在1736年巧妙地給出了這個(gè)問(wèn)題的答案，并因此奠定了圖論的基礎(chǔ)，Euler把A、B、C、D四塊陸地分別收縮成四個(gè)頂點(diǎn)，把橋表示成連接對(duì)應(yīng)頂點(diǎn)之間的邊，問(wèn)題轉(zhuǎn)化為從任意一點(diǎn)出發(fā)，能不能經(jīng)過(guò)各邊一次且僅一次，最后返回該點(diǎn)。這就是著名的Euler問(wèn)題。,A,C,B,D,例：哈密頓（Hamilton）回路是十九世紀(jì)英國(guó)數(shù)學(xué)家哈密頓提出，給出一個(gè)正12面體圖形，共有20個(gè)頂點(diǎn)表示20個(gè)城市，要求從某個(gè)城市出發(fā)沿著棱線尋找一條經(jīng)過(guò)每個(gè)城市一次而且僅一次，最后回到原處的周游世界線路（并不要求經(jīng)過(guò)每條邊）。,圖的基本概念 圖論是專門研究圖的理論的一門數(shù)學(xué)分支，主要研究點(diǎn)和線之間的 幾何關(guān)系。,一、圖與網(wǎng)絡(luò)的基本概念 1、圖及其分類 定義1：（圖）一個(gè)圖由點(diǎn)集V和V中的元素?zé)o序?qū)Φ囊粋€(gè)集合，記為 G=（V，E） 其中：V= （ v1， v2，. vm）是m個(gè)頂點(diǎn)集合； E= （ e1， e2，. en） 是n條邊集合。 當(dāng)V和E為有限集合時(shí)，G為有限圖。 2個(gè)點(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ò)的基本知識(shí),如果任一邊(u,v)屬于E且端點(diǎn)無(wú)序，無(wú)向邊；圖G為無(wú)向圖。 如果任一邊(u,v)屬于E且端點(diǎn)有序，有向邊；圖G為有向圖 m(G)= E ，表示圖G的邊數(shù)； n(G)= V ，表示圖G的點(diǎn)數(shù)；,環(huán)（自回路）：一條邊的兩個(gè)端點(diǎn)如果相同。 兩個(gè)點(diǎn)之間多于一條邊的，多重邊。 定義2：不含環(huán)和多重邊的圖，簡(jiǎn)單圖。 含有多重邊的圖，多重圖。 有向圖中的兩點(diǎn)之間有不同方向的兩條邊，不是多重邊。,簡(jiǎn)單圖,定義3：每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖，完全圖。 有向完全圖：指每一對(duì)頂點(diǎn)間有且僅有一條有向邊的簡(jiǎn)單圖。 定義4:圖G=(V,E)的點(diǎn)集V可以分為2個(gè)非空子集X,Y，使得E中每條邊的兩個(gè)端點(diǎn)必有一個(gè)端點(diǎn)屬于X，另一個(gè)端點(diǎn)屬于Y，G為二部圖（偶圖），有時(shí)記為： G=(X,Y,E),V1,V4,V3,V2,X,Y,2、頂點(diǎn)的次 定義5：以點(diǎn)v為端點(diǎn)的邊的個(gè)數(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 在一個(gè)圖中，所有頂點(diǎn)次的和等于邊的兩倍。 定理2 在任意一個(gè)圖中，次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。 定義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)和邊的交錯(cuò)序列(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)邊序列。 初等鏈：鏈中無(wú)重復(fù)的點(diǎn)和邊； 定義9：無(wú)向圖中，如一條鏈中起點(diǎn)和終點(diǎn)重合，則稱此鏈為圈。 初等圈：圈中無(wú)重復(fù)的點(diǎn)和邊； 有向圖中，當(dāng)鏈（圈）上的邊方向相同時(shí)，為道路（回路）。,道路 道路 回路,鏈、初等鏈、初等圈,道路、回路,連通圖：圖中任意兩點(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,圈,三、圖的矩陣表示 一個(gè)圖非常直觀，但是不容易計(jì)算，特別不容易在計(jì)算機(jī)上進(jìn)行計(jì)算，一個(gè)有效的解決辦法是將圖表示成矩陣形式，通常采用的矩陣是鄰接矩陣、邊長(zhǎng)鄰接矩陣、弧長(zhǎng)矩陣和關(guān)聯(lián)矩陣。,1、鄰接矩陣 鄰接矩陣A表示圖G的頂點(diǎn)之間的鄰接關(guān)系，它是一個(gè)nxn的矩陣，如果兩個(gè)頂點(diǎn)之間有邊相聯(lián)時(shí)，記為1，否則為0。,定義12：對(duì)于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)矩陣 在圖的各邊上一個(gè)數(shù)量指標(biāo)，具體表示這條邊的權(quán)（距離，單價(jià)，通過(guò)能力等），以邊長(zhǎng)代替鄰接矩陣中的元素得到邊長(zhǎng)鄰接矩陣。 定義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,四、歐拉回路與中國(guó)郵政問(wèn)題 1、歐拉回路與道路 定義13：連通圖G，如果存在一條道路，經(jīng)過(guò)每邊一次且僅一次，則稱這條路為歐拉道路； 如果存在一條回路，經(jīng)過(guò)每邊一次且僅一次，則稱這條路為歐拉回路； 具有歐拉回路的圖為歐拉圖。 定理3：無(wú)向連接圖G是歐拉圖，當(dāng)且僅當(dāng)G中無(wú)奇 點(diǎn)。 推論1：無(wú)向連接圖G為歐拉圖，當(dāng)且僅當(dāng)G的邊集可劃為若干個(gè)初等回路。 推論2：無(wú)向連接圖G為歐拉道路，當(dāng)且僅當(dāng)G恰好有2個(gè)奇點(diǎn)。,定理4：連通有向圖G是歐拉圖，當(dāng)且僅當(dāng)它每個(gè)奇點(diǎn)的出次等于入次。 2、中國(guó)郵路問(wèn)題 一個(gè)郵遞員，從郵局出發(fā)，走遍所有街道后回到郵局，如何安排，使其總的路程最短？ 圖論：給定一個(gè)連通圖，每邊有非負(fù)權(quán)，要求一條回路過(guò)每邊至少一次，且滿足總權(quán)最小。 定理5：已知圖G*=G+E1無(wú)奇點(diǎn)，則L(E1)= l(e)最小的充要條件 （1）每條邊最多重復(fù)一次； （2）對(duì)圖G中每個(gè)初等圈，重復(fù)邊的長(zhǎng)度和不超過(guò)圈長(zhǎng)的1/2；,例：求解網(wǎng)絡(luò)的中國(guó)郵路問(wèn)題,第一步：確定初始可行方案 先檢查圖中是否有奇點(diǎn)，如果無(wú)奇點(diǎn)，為歐拉圖；如果有奇點(diǎn)，圖中的奇點(diǎn)的個(gè)數(shù)比為偶數(shù)個(gè)，所以可以兩兩配對(duì)，構(gòu)造二重邊。圖中有4個(gè)奇點(diǎn)，v2,v4,v6,v8,配對(duì) v2-v4,v6-v8，構(gòu)造二重邊。重復(fù)邊 的總長(zhǎng)： 2l23+ 2l36+ l69+ l98+ l23+ 2l87+ 2l74+ l41+ l12=51,第二步：調(diào)整可行方案，使重復(fù)邊最多為一次 重復(fù)邊 的總長(zhǎng)： l69+ l98+ l41+ l12=21,第三步：檢查每個(gè)初等圈是否 定理?xiàng)l件2，如果不滿足，進(jìn)行 調(diào)整，直至滿足為止。 圈v1v2v5v4v1總長(zhǎng)度24，重復(fù)邊14，14/21大于1/2，調(diào)整（v2,v5），（v5,v4）代替（v1,v2），(v1,v4),圈v1v2v5v4v1總長(zhǎng)度24， 重復(fù)邊6+4=10,重復(fù)邊 的總長(zhǎng)： l69+ l98+ l45+ l52=17 再檢查圈v2v3v6v9v8v5v2總長(zhǎng)=24,重復(fù)邊 的長(zhǎng)度13，繼續(xù)調(diào)整,再次調(diào)整的重復(fù)邊 的總長(zhǎng)：=15，滿足條件要求。 圖中任一歐拉回路為最優(yōu)郵遞回路。 方法：簡(jiǎn)單；但要檢查每一個(gè)初等圈。,總結(jié):圖的基本概念,G=（V，E）,子圖,矩陣表示,含元素的個(gè)數(shù),點(diǎn)的次,邊,特殊的圖,點(diǎn)邊關(guān)系,簡(jiǎn)單圖,多重圖,連通圖,樹,生成子圖,G=(V,E),矩陣表示 A 鄰接矩陣 B 權(quán)矩陣,邊e=(u,v),關(guān)聯(lián)邊,自回路,多重邊 平行邊,簡(jiǎn)單圖,多重圖,0 1 奇數(shù) 偶數(shù),點(diǎn)邊關(guān)系,點(diǎn)邊關(guān)系,生成樹,有向圖,道路、回路,1.思考題 子圖與生成子圖的區(qū)別是什么？ 2.討論題 中國(guó)郵路問(wèn)題的解題步驟？,小結(jié): 1.圖的基本知識(shí)。 2.圖的矩陣表示。 3.歐拉道路與歐拉回路。,