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

1、引言 圖論是專門研究圖的理論的一門數(shù)學(xué)分支，屬于離散數(shù)學(xué)范疇，與運(yùn)籌學(xué)有交叉，它有200多年歷史，大體可劃分為三個(gè)階段：第一階段是從十八世紀(jì)中葉到十九世紀(jì)中葉，處于萌芽階段，多數(shù)問(wèn)題圍游戲而產(chǎn)生，最有代表性的工作是所謂的Euler七橋問(wèn)題，即一筆畫問(wèn)題。第八章 圖與網(wǎng)絡(luò)分析引言第八章 圖與網(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ì)中葉到二十世紀(jì)中葉，這時(shí)，圖論問(wèn)題大量出第三階段是二十

2、世紀(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)用。第三階段是二十世紀(jì)中葉以后，由生產(chǎn)管理、軍事、交通、運(yùn)輸、計(jì)例：哥尼斯堡七橋問(wèn)題 哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個(gè)城市，Pregei河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒(méi)有辦法從某處（如A）出發(fā)，經(jīng)過(guò)各橋一次且僅一次最后回到原地呢？例：哥尼斯堡七橋問(wèn)題ABCDABCD 最后，數(shù)學(xué)家Eu

3、ler在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)題。 最后，數(shù)學(xué)家Euler在1736年巧妙地給出了這個(gè)ACBDACBD例：哈密頓（Hamilton）回路是十九世紀(jì)英國(guó)數(shù)學(xué)家哈密頓提出，給出一個(gè)正12面體圖形，共有20個(gè)頂點(diǎn)表示20個(gè)城市，要求從某個(gè)城市出發(fā)沿著棱線尋找一條經(jīng)過(guò)每個(gè)城市一次而且僅一次，最后回到原處的周游世界線路（并不要求經(jīng)過(guò)每條邊）。例：哈密頓（Hamilton）回路是十九世紀(jì)英國(guó)

4、數(shù)學(xué)家哈密頓運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析運(yùn)籌學(xué)課件-第八章-圖與網(wǎng)絡(luò)分析 圖的基本概念 圖論是專門研究圖的理論的一門

5、數(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í)一、圖與網(wǎng)絡(luò)的基本概念第一節(jié) 圖與網(wǎng)絡(luò)的基本知識(shí)如果任一邊(u,v)屬于E且端點(diǎn)無(wú)序，無(wú)向邊；圖G為無(wú)向圖。如果任一邊(u,v)屬于

6、E且端點(diǎn)有序，有向邊；圖G為有向圖m(G)= E ，表示圖G的邊數(shù)；n(G)= V ，表示圖G的點(diǎn)數(shù)；如果任一邊(u,v)屬于E且端點(diǎn)無(wú)序，無(wú)向邊；圖G為無(wú)向圖。環(huán)（自回路）：一條邊的兩個(gè)端點(diǎn)如果相同。兩個(gè)點(diǎn)之間多于一條邊的，多重邊。定義2：不含環(huán)和多重邊的圖，簡(jiǎn)單圖。 含有多重邊的圖，多重圖。有向圖中的兩點(diǎn)之間有不同方向的兩條邊，不是多重邊。簡(jiǎn)單圖環(huán)（自回路）：一條邊的兩個(gè)端點(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)

7、屬于X，另一個(gè)端點(diǎn)屬于Y，G為二部圖（偶圖），有時(shí)記為： G=(X,Y,E)V1V4V3V2XY定義3：每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖，完全圖。V1V4 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ù)； 2、頂點(diǎn)的次 v1v3v2v4v6v5e1e3e5e6e4e8e7e2v1v3v2v4v6v5e1e3e5e6e4e8e7e2V= （ v1， v2，. v6）E= （ e1， e2，. e8）（e1）= （

8、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。V= （ v1， v2，. v6）定理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)的出次之和；定理1 在一個(gè)圖中，所有頂點(diǎn)次的和等于邊的兩倍。3、子圖定義：設(shè)G=（V，E）和G

9、1=（V1，E1）。 如果V1 V， E1 E則稱G1為G的子圖； 如果G1 =（ V1，E1 ）是G=（V，E）子圖，并且V1 = V，則稱G1為G的生成子圖；3、子圖v1v5v4v2v3e1e8e7e6e5e4e3e2v1v5v4v2v3e1e8e7e6e5e4e3e2v1v5v4v2e1e5e3（a）的子圖v1v5v4v2e1e5e3（a）的子圖v1v5v4v2v3e8e6e5e2（a）的生成子圖v1v5v4v2v3e8e6e5e2（a）的生成子圖二、連通圖定義8:如果圖中的某些點(diǎn)、邊可以排列成點(diǎn)和邊的交錯(cuò)序列(v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1 , en ，

10、 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)之間均至少有一條通路，否則稱為不連通圖。連通圖：圖中任意兩點(diǎn)之間均至少有一條通路，否則稱為不連通圖。v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e

11、3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5v4v2v3e1e8e7e6e5e4e3e2有向圖v1v5

12、v4v2v3e1e8e7e6e5e4e3e2鏈v1v5v4v2v3e1e8e7e6e5e4e3e2鏈v1v5v4v2e1e7e6e3v1v5v4v2e1e7e6e3v1v5v4v2e1e7e6e3v1v5v4v2e1e7e6e3v1v5v4v2e1e7e6e3v1v5v4v2e1e7e6e3v1v5v4v2e1e7e6e3圈v1v5v4v2e1e7e6e3圈三、圖的矩陣表示 一個(gè)圖非常直觀，但是不容易計(jì)算，特別不容易在計(jì)算機(jī)上進(jìn)行計(jì)算，一個(gè)有效的解決辦法是將圖表示成矩陣形式，通常采用的矩陣是鄰接矩陣、邊長(zhǎng)鄰接矩陣、弧長(zhǎng)矩陣和關(guān)聯(lián)矩陣。1、鄰接矩陣 鄰接矩陣A表示圖G的頂點(diǎn)之間的鄰接關(guān)系，它是一

13、個(gè)nxn的矩陣，如果兩個(gè)頂點(diǎn)之間有邊相聯(lián)時(shí)，記為1，否則為0。三、圖的矩陣表示1、鄰接矩陣定義12：對(duì)于G=(V,E)，構(gòu)造矩陣A=(aij)nxnaij= 1, （vi,vj） E 0矩陣A為鄰接矩陣。定義12：對(duì)于G=(V,E)，構(gòu)造矩陣A=(aij)nxnV1V3V5V6V4V2v1 v2 v3 v4 v5 v6V1V3V5V6V4V2v1 v2 v3 v4 v5 v62、權(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)nxnai

14、j= wij, （vi,vj） E 0矩陣A為權(quán)矩陣。2、權(quán)矩陣v1v2v5v4v3924386745 v1 v2 v3 v4 v5v1v2v5v4v3924386745 v1 v2四、歐拉回路與中國(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)。四、歐拉回路與中國(guó)郵政問(wèn)題

15、定理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；定理4：連通有向圖G是歐拉圖，當(dāng)且僅當(dāng)它每個(gè)奇點(diǎn)的出次等于入例：求解網(wǎng)絡(luò)的中國(guó)郵路問(wèn)題v1v3v6v9v8v7v4v5v2第一步：確定初始可行方案先檢查圖中是否有奇點(diǎn)，如果無(wú)奇點(diǎn)，為歐拉圖；如果有奇點(diǎn)，圖

16、中的奇點(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=51v1v3v6v9v8v7v4v5v2343449545642343449545642例：求解網(wǎng)絡(luò)的中國(guó)郵路問(wèn)題v1v3v6v9v8v7v4v5v第二步：調(diào)整可行方案，使重復(fù)邊最多為一次重復(fù)邊 的總長(zhǎng)：l69+ l98+ l41+ l12=21第三步：檢查每個(gè)初等圈是否定理?xiàng)l件2，如果不滿足，進(jìn)行調(diào)整，直至滿足為止。圈v1v2v5v4v1總長(zhǎng)度2

17、4，重復(fù)邊14，14/21大于1/2，調(diào)整（v2,v5），（v5,v4）代替（v1,v2），(v1,v4)v1v3v6v9v8v7v4v5v2圈v1v2v5v4v1總長(zhǎng)度24，重復(fù)邊6+4=10v1v3v6v9v8v7v4v5v2343449545642第二步：調(diào)整可行方案，使重復(fù)邊最多為一次第三步：檢查每個(gè)初等重復(fù)邊 的總長(zhǎng)：l69+ l98+ l45+ l52=17再檢查圈v2v3v6v9v8v5v2總長(zhǎng)=24,重復(fù)邊 的長(zhǎng)度13，繼續(xù)調(diào)整v1v3v6v9v8v7v4v5v2再次調(diào)整的重復(fù)邊 的總長(zhǎng)：=15，滿足條件要求。圖中任一歐拉回路為最優(yōu)郵遞回路。方法：簡(jiǎn)單；但要檢查每一個(gè)初等圈。v1v3v6v9v8v7v4v5v26434524重復(fù)邊 的總長(zhǎng)：v1v3v6v9v8v7v4v5v2再次調(diào)整總結(jié):圖的基本概念G=（V，E）子圖矩陣表示含元素的個(gè)數(shù)點(diǎn)的次邊特殊的圖點(diǎn)邊關(guān)系簡(jiǎn)單圖多重圖連通圖樹生成子圖總結(jié):圖的基本概念G=（V，E）子圖矩陣表示含元素的個(gè)數(shù)點(diǎn)的G=(V,E) 矩陣表示A 鄰接矩陣B 權(quán)矩陣邊e=(u,v) 關(guān)聯(lián)邊 端點(diǎn) 重合環(huán)自回路多重邊 平行邊多于1條邊簡(jiǎn)單圖不含多重圖含點(diǎn)的次 0 1 奇數(shù) 偶數(shù) 子圖孤立點(diǎn)懸掛點(diǎn)奇