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

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