運籌學圖與網絡分析ppt課件

1、圖與網絡分析圖與網絡分析 (Graph Theory and Network Analysis)圖與網絡的根本知識圖與網絡的根本知識最短路問題最短路問題樹及最小樹問題樹及最小樹問題最大流問題最大流問題哥尼斯堡七橋問題哥尼斯堡七橋問題哥尼斯堡現名加里寧格勒是歐洲一個城哥尼斯堡現名加里寧格勒是歐洲一個城市，市，PregeiPregei河把該城分成兩部分，河中有兩個小河把該城分成兩部分，河中有兩個小島，十八世紀時，河兩邊及小島之間共有七座橋，島，十八世紀時，河兩邊及小島之間共有七座橋，當時人們提出這樣的問題：有沒有方法從某處當時人們提出這樣的問題：有沒有方法從某處如如A A出發(fā)，經過各橋一次且僅一次

2、最后回到出發(fā)，經過各橋一次且僅一次最后回到原地呢？原地呢？BDACABCD哥尼斯堡七空橋哥尼斯堡七空橋一筆畫問題一筆畫問題引論引論 圖的用途圖的用途 某公司的 組織機構設置圖總公司總公司分公司分公司工廠或工廠或辦事處辦事處一、一、 圖與網絡的根本知識圖與網絡的根本知識一、圖與網絡的根本概念一、圖與網絡的根本概念 EADCB 1、一個圖是由點和連線組成。連線可帶箭頭，也可、一個圖是由點和連線組成。連線可帶箭頭，也可不帶，前者叫弧，后者叫邊不帶，前者叫弧，后者叫邊v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例 654321,vvvvvvV ,10987654321eeeee

3、eeeeeE， ,211vve ,212vve ,323vve ,434vve ,315vve ,536vve ,537vve ,658vve ,669vve ,6110vve 圖圖1一個圖是由點集一個圖是由點集 和和 中元素的無序對的一個中元素的無序對的一個集合集合 構成的二元組，記為構成的二元組，記為G =(VG =(V，E )E )，其中，其中V V中的中的元素元素 叫做頂點，叫做頂點，V V表示圖表示圖G G 的點集合；的點集合；E E中的元素中的元素 叫做叫做邊，邊，E E 表示圖表示圖G G的邊集合。的邊集合。keE jvkeV jvV 2 2、不帶箭頭的連線叫做邊。假設一個圖是由

4、點和邊所構成的，、不帶箭頭的連線叫做邊。假設一個圖是由點和邊所構成的，那么稱其為無向圖，記作那么稱其為無向圖，記作G = (VG = (V，E)E)，銜接點的邊記作，銜接點的邊記作vi , vjvi , vj，或者或者vj , vivj , vi。 3 3、假設點與點之間的連線有方向，稱為弧。假設一個圖是由、假設點與點之間的連線有方向，稱為弧。假設一個圖是由點和弧所構成的，那么稱它為有向圖，記作點和弧所構成的，那么稱它為有向圖，記作D=(V, A)D=(V, A)，其中，其中V V 表示表示有向圖有向圖D D 的點集合，的點集合，A A 表示有向圖表示有向圖D D 的弧集合。一條方向從的弧集合

5、。一條方向從vivi指向指向vj vj 的弧，記作的弧，記作(vi , vj)(vi , vj)。v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 圖圖2 4 4、一條邊的兩個端點是一樣的、一條邊的兩個端點是一樣的, ,那么稱這條邊是環(huán)。那么稱這條邊是環(huán)。 5 5、假設兩個端點之間有兩條以上的邊，那么稱它們?yōu)?、假設兩個端點之間有兩條以上的邊，那么稱它

6、們?yōu)槎嘀剡?。多重邊?6 6、不含環(huán)和多重邊的圖稱為簡單圖；有多重邊的圖稱、不含環(huán)和多重邊的圖稱為簡單圖；有多重邊的圖稱為多重圖。為多重圖。 7、每一對頂點間都有邊相連的無向簡單圖稱為完全圖。、每一對頂點間都有邊相連的無向簡單圖稱為完全圖。 有向完全圖那么是指恣意兩個頂點之間有且僅有一條有向完全圖那么是指恣意兩個頂點之間有且僅有一條有向邊的簡單圖。有向邊的簡單圖。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 次為零的點稱為弧立點，次為次為零的點稱為弧立點，次為1 1的點稱為懸掛點。懸掛的點稱為懸掛點。懸掛點的關聯邊稱為懸掛邊。次為奇數的點稱為奇點，次為偶點的關聯邊稱為懸掛

7、邊。次為奇數的點稱為奇點，次為偶數的點稱為偶點。數的點稱為偶點。 8 8、以點、以點v v為端點的邊的個數稱為點為端點的邊的個數稱為點v v 的次，記作的次，記作 。)(vd圖中圖中 d(v1)= 4 d(v1)= 4，d(v6)= 4d(v6)= 4環(huán)計兩次環(huán)計兩次 定理定理1 1 一切頂點次數之和等于一切邊數的一切頂點次數之和等于一切邊數的2 2倍。倍。 定理定理2 2 在任一圖中，奇點的個數必為偶數。在任一圖中，奇點的個數必為偶數。 一切頂點的入次之和等于一切頂點的出次之和。一切頂點的入次之和等于一切頂點的出次之和。 有向圖中，以有向圖中，以 vi vi 為始點的邊數稱為點為始點的邊數稱

8、為點vivi的出次，用的出次，用 表示表示 ；以；以 vi vi 為終點的邊數稱為點為終點的邊數稱為點vi vi 的入次，的入次，用用 表示；表示；vi vi 點的出次和入次之和就是該點的次。點的出次和入次之和就是該點的次。)(ivd )(ivd v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖支撐子圖在實踐運用中，給定圖中每條邊在實踐運用中，給定圖中每條邊 ，對應，對應一個數一個數 ，稱之為，稱之為 “權。通常把這種賦權的圖稱權。通常把

9、這種賦權的圖稱為網絡。為網絡。 ),(jivvjiw 10 10、由兩兩相鄰的點及其相關聯的邊構成的點邊序列、由兩兩相鄰的點及其相關聯的邊構成的點邊序列稱為鏈。稱為鏈。 如如:v0 :v0 ，e1e1，v1v1，e2e2，v2v2，e3 e3 ，v3 ,vn-1 ,en v3 ,vn-1 ,en ，vnvn， e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10 11 11、圖中恣意兩點之間均至少有一條鏈相連，那么稱、圖中恣意兩點之間均至少有一條鏈相連，那么稱此圖為連通圖。此圖為連通圖。 其鏈長為其鏈長為 n n ，其中，其中 v0 v0 ，vn vn 分別稱為鏈的起點和終分別稱

10、為鏈的起點和終點點 。所含的點、邊均不一樣的鏈稱為初等鏈。起點和終。所含的點、邊均不一樣的鏈稱為初等鏈。起點和終點是同一個點的鏈稱為圈。點是同一個點的鏈稱為圈。二、二、 圖的矩陣表示圖的矩陣表示對于網絡賦權圖對于網絡賦權圖G=G=V V，E E，其中邊，其中邊有權有權 ，構造矩陣，構造矩陣 ，其中：，其中：稱矩陣稱矩陣A A為網絡為網絡G G的權矩陣。的權矩陣。),(jivvjiw EvvEvvwajijijiji),(0),(nnjiaA )(nnjiaA )( EvvEvvajijiji),(0),(1 設圖設圖G=G=V V，E E中頂點的個數為中頂點的個數為n n，構造一個，構造一個矩

11、陣矩陣 ，其中：，其中： 稱矩陣稱矩陣A A為網絡為網絡G G的鄰接矩陣。的鄰接矩陣。 654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 例例權矩陣為：權矩陣為：鄰接矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437654321654321 030303302004020576305020007204346040vvvvvvvvvvvvA 二、二、 樹及最小樹問題樹及最小樹問題 知有六個城市，它們之間知有六個城市，它們之間 要架設線，要求恣意兩個城要架設線，要求恣意兩個城市均可以相互通話，并且線的總長度最

12、短。市均可以相互通話，并且線的總長度最短。 v1v2v3v4v5v6 1 1、一個連通的無圈的無向圖叫做樹。、一個連通的無圈的無向圖叫做樹。 樹中次為樹中次為1 1的點稱為樹葉，次大于的點稱為樹葉，次大于1 1的點稱為分支點。的點稱為分支點。 樹樹 的性質：的性質： 1 1數必連通，但無回路圈。數必連通，但無回路圈。 2 2n n 個頂點的樹必有個頂點的樹必有n-1 n-1 條邊。條邊。 3 3樹樹 中恣意兩個頂點之間，恰有且僅有一條鏈初中恣意兩個頂點之間，恰有且僅有一條鏈初等鏈。等鏈。 4 4樹樹 連通，但去掉任一條邊，連通，但去掉任一條邊， 必變?yōu)椴贿B通。必變?yōu)椴贿B通。 5 5樹樹 無回路

13、圈，但不相鄰的兩個點之間加一條無回路圈，但不相鄰的兩個點之間加一條邊，恰得到一個回路圈。邊，恰得到一個回路圈。v1v2v3v4v5v6 2 2、 假設圖假設圖G=(V , E )G=(V , E )的生成子圖是一個樹的生成子圖是一個樹, ,那么稱那么稱該樹該樹 是是G G 的一個生成樹支撐樹，或簡稱為圖的一個生成樹支撐樹，或簡稱為圖G G 的樹。的樹。圖圖G G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。弦。一個圖一個圖G G 有生成樹的充要條件是有生成樹的充要條件是G G 是連通圖。是連通圖。 v1v2v3v4v5v1v2v3v4v5一破圈

14、法：在圖中任選一個圈，從這個圈中去一破圈法：在圖中任選一個圈，從這個圈中去掉一條邊。在余下的圖中反復這個步驟，直到得到掉一條邊。在余下的圖中反復這個步驟，直到得到一不含圈的圖為止。一不含圈的圖為止。用破圈法求出以下圖的一個生成樹。用破圈法求出以下圖的一個生成樹。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8二避圈法：開場選一條邊，以后每一步中，總從二避圈法：開場選一條邊，以后每一步中，總從未被選取的邊中選出一條與已選邊不構成圈的邊，反未被選取的邊中選出一條與已選邊不構成圈的邊，反復這個過程，直到不能

15、進展為止。復這個過程，直到不能進展為止。v1v2v3v4v5v6 v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5根據破圈法和避圈法兩種方式得到了根據破圈法和避圈法兩種方式得到了圖的兩個不同的生成樹，由此可以看到連圖的兩個不同的生成樹，由此可以看到連通圖的生成樹不是獨一的。通圖的生成樹不是獨一的。3 3、最小生成樹問題、最小生成樹問題 一棵生成樹一切樹枝上權的總和為這個生成樹一棵生成樹一切樹枝上權的總和為這個生成樹的權。具有最小權的生成樹，稱為最小生成樹。的權。具有最小權的生成樹，稱為最小生成樹。求賦權圖求賦權圖G G的最小支撐樹的方法也有兩種，的最小支撐樹的方

16、法也有兩種，“破破圈法和圈法和“避圈法。避圈法。 破圈法：在原圖中，破圈法：在原圖中，任選一個圈，從圈中任選一個圈，從圈中去掉權最大的一條邊。去掉權最大的一條邊。在余下的圖中反復這在余下的圖中反復這個步驟，直到得到一個步驟，直到得到一不含圈的圖為止。不含圈的圖為止。655172344v1v2v3v4v5v6總造價總造價=1+4+9+3+17+23=57=1+4+9+3+17+23=57v1v2v3v4v514231352 避圈法：開場選一條權最小的邊，以后每一避圈法：開場選一條權最小的邊，以后每一步中，總從未被選取的邊中選一條權盡能夠小，步中，總從未被選取的邊中選一條權盡能夠小，且與已選邊不構

17、成圈的邊。且與已選邊不構成圈的邊。 某六個城市之間的道路網如圖某六個城市之間的道路網如圖 所示，要求沿著知長所示，要求沿著知長度的道路結合六個城市的線網，使線的總長度最短。度的道路結合六個城市的線網，使線的總長度最短。 v1v2v3v4v5v66515723445v1v2v3v4v5v61234最短路的普通提法為：設最短路的普通提法為：設 為連通圖，為連通圖，圖中各邊圖中各邊 有權有權 表示表示 之間沒之間沒有邊，有邊， 為圖中恣意兩點，求一條路為圖中恣意兩點，求一條路 ，使它，使它從從 到到 的一切路中總權最短。即：的一切路中總權最短。即： 最最小。小。),(EVG j il jiltsvv

18、 , sv),(jivvjivv ,tv ),()(jivvjilL( (一一) )、狄克斯徹、狄克斯徹(Dijkstra)(Dijkstra)算法算法適用于適用于wij0wij0，給出了從，給出了從vsvs到恣意一個點到恣意一個點vjvj的最短的最短路。路。三三 、最短路問題、最短路問題算法步驟：算法步驟：1.1.給始點給始點vsvs以以P P標號標號 ，這表示從，這表示從vsvs到到vsvs的的最短間隔為最短間隔為0 0，其他節(jié)點均給，其他節(jié)點均給T T標號，標號， 。2.2.設節(jié)點設節(jié)點vivi為剛得到為剛得到P P標號的點，思索點標號的點，思索點vjvj，其中，其中 ，且，且vjvj為

19、為T T標號。對標號。對vjvj的的T T標號進展如下修標號進展如下修正：正：3.3.比較一切具有比較一切具有T T標號的節(jié)點，把最小者改為標號的節(jié)點，把最小者改為P P標標號，即：號，即：當存在兩個以上最小者時，可同時改為當存在兩個以上最小者時，可同時改為P P標號。假標號。假設全部節(jié)點均為設全部節(jié)點均為P P標號那么停頓，否那么用標號那么停頓，否那么用 替代替代vivi，前往步驟，前往步驟2 2。0)( svP )(ivTEvvji ),()(, )(min)(ijijjlvPvTvT )(min)(iivTvP iv例一：用例一：用DijkstraDijkstra算法求以下圖從算法求以下

20、圖從v1v1到到v6v6的最短的最短路。路。 v1v2v3v4v6v5352242421 解：解：1首先給首先給v1以以P標號，給其他一切點標號，給其他一切點T標號。標號。0)(1 vP)6,3,2()( ivTi2 23 3330,min)(, )(min)(12122 lvPvTvT550,min)(, )(min)(13133 lvPvTvT3)(2 vP4 4413,5min)(, )(min)(23233 lvPvTvT523,min)(, )(min)(24244 lvPvTvT523,min)(, )(min)(25255 lvPvTvT4)(3 vP5 56 6544,5min

21、)(, )(min)(35355lvPvTvT5)(4 vP5)(5 vP945,min)(, )(min)(46466 lvPvTvT725,min)(, )(min)(56566 lvPvTvT7)(6 vP7 78 89 91010反向追蹤得反向追蹤得v1v1到到v6v6的最短路為：的最短路為：6521vvvvv1v2v3v4v6v5352242421二、逐次逼近法二、逐次逼近法首先設任一點首先設任一點vivi到任一點到任一點vjvj都有一條弧。都有一條弧。顯然，從顯然，從v1v1到到vjvj的最短路是從的最短路是從v1v1出發(fā)，沿著這條路到出發(fā)，沿著這條路到某個點某個點vivi再沿弧再

22、沿弧(vi,vj)(vi,vj)到到vjvj。那么。那么v1v1到到vivi的這條路的這條路必然也是必然也是v1v1到到vivi的一切路中的最短路。設的一切路中的最短路。設P1jP1j表示從表示從v1v1到到vjvj的最短路長，的最短路長，P1iP1i表示從表示從v1v1到到vivi的最短路長，的最短路長，那么有以下方程：那么有以下方程： 開場時，令開場時，令 即用即用v1v1到到vjvj的直接間隔做初始解。的直接間隔做初始解。min11jiiijlPP ),2,1(1)1(1njlPjj 從第二步起，運用遞推公式：求 ，當進展到第t步，假設出現那么停頓計算， 即為v1到各點的最短路長。）（n

23、klPPjikiikj,3,2min)1(1)(1 )(1kjP）（njPPtjtj,2,1)1(1)(1 ）（njPtj,2,1)(1 例二、例二、 18v1v2v3v4v52635135211211v6v7v83766 0-5 -3 v8-5-55 0 -1 v7-1-1-1 7101 v6-3-31 0 -1 v5-7-7-73 2 0 8v4-2-2-2-2 1 -50-3 v3-5-5-5-1 2 06v20000 3-2-10v1P(4)P(3)P(2)P(1)v8v7v6v5v4v3v2v1求圖中求圖中v1v1到到各點的最短路各點的最短路 18v1v2v3v4v526351352

24、11211v6v7v8370，0 v3 ，-5 v1 ，-2 v3 ，-7 v2 ，-3 v4 ，-5 v3 ，-1 v6 ，6例、求：例、求：5 5年內，哪些年初購置新設備，使年內，哪些年初購置新設備，使5 5年內的總費用最年內的總費用最小。小。 第第i i年度年度 1 2 3 4 1 2 3 4 5 5購置費購置費 11 11 12 12 13設備役齡設備役齡0-1 1-2 2-3 3-4 4-5維修費用維修費用 5 6 8 11 5 6 8 11 1818解：解：1分析：可行的購置方案更新方案是分析：可行的購置方案更新方案是很多的，很多的， 如：如： 1 每年購置一臺新的，那么對應的費用

25、為：每年購置一臺新的，那么對應的費用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購置新的，不斷用到第五年年底，第一年購置新的，不斷用到第五年年底，那么總費用為：那么總費用為： 11+5+6+8+11+18 = 59 顯然不同的方案對應不同的費用。顯然不同的方案對應不同的費用。 2 2方法：將此問題用一個賦權有向圖來描畫，然后求方法：將此問題用一個賦權有向圖來描畫，然后求這個賦權有向圖的最短路。這個賦權有向圖的最短路。 求解步驟：求解步驟： 1 1畫賦權有向圖：畫賦權有向圖： 設設 Vi Vi 表示第表示第i i年初，年初，(Vi ,Vj )(Vi ,Vj )

26、表示第表示第i i 年初購買年初購買新設備用到第新設備用到第j j年初年初j-1j-1年底，而年底，而Wi j Wi j 表示相應費表示相應費用，那么用，那么5 5年的一個更新方案相當于從年的一個更新方案相當于從V1 V1 到到V6V6的一條路。的一條路。 2 2求解求解 標號法標號法 W12 =11+5=16W13 =11+5+6=22W14 =11+5+6+8=30W15 =11+5+6+8+11=41W16 =11+5+6+8+11+18=59 W23 =11+5=16 W24 =11+5+6=22W 2 5 = 1 1 + 5 + 6 + 8 = 3 0 W 2 6 =11+5+6+8

27、+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6=23W36 =12+5+6+8=31 四、四、 最大流問題最大流問題一一 根本概念根本概念1、設一個賦權有向圖、設一個賦權有向圖G=V, E,在在V中指定一中指定一個發(fā)點個發(fā)點vs和一個收點和一個收點vt ,其它的點叫做中間點。對其它的點叫做中間點。對于于D中的每一個弧中的每一個弧vi , vjE ,都有一個非負數都有一個非負數cij,叫做弧的容量。我們把這樣的圖叫做弧的容量。我們把這樣的圖G叫做容量網叫做容量網絡，簡稱網絡，記做絡，簡稱網絡，記做G=V

28、，E，C。網絡網絡G上的流，是指定義在弧集合上的流，是指定義在弧集合E上的一個函上的一個函數數其中其中f(vi ,vj) =fij 叫做弧叫做弧(vi，vj)上的流量。上的流量。 ),(jijifvvff 2、稱滿足以下條件的流為可行流：、稱滿足以下條件的流為可行流：1容量條件：對于每一個弧容量條件：對于每一個弧vi ,vjE有有 0 fij cij 。 2平衡條件：平衡條件：對于發(fā)點對于發(fā)點vs，有，有對于收點對于收點vt ，有，有對于中間點，有對于中間點，有 EvvjsjsWf),(WfEvvt jtj ),( EvvEvvi jjijiijff),(),(可行流中可行流中 fijcij

29、的弧叫做飽和弧，的弧叫做飽和弧，fijcij的弧叫做非飽和弧。的弧叫做非飽和弧。vsv1v2v4v3vt374556378S),(2vvSs ),(431tvvvvS ),(),(, ),( , ),(),(4232211vvvvvvvvSSs 18567),(23241 lllSSCs 3、容量網絡G =V，E，C，vs為始點，vt為終點。假設把V分成兩個非空集合 使 ，那么一切一點屬于 ，而另一點屬于 的弧的集合，稱為由 決議的割集,記作 。割集 中一切始點在 ，終點在 的弧的容量之和，稱為這個割集的容量，記為 。 SS ,SvSvts,S),(SS),(SS),(SSCSSSS關于最大流

30、問題的定理：關于最大流問題的定理：最大流最小割定理：任一網絡中，最大流最小割定理：任一網絡中，最大流的流量等于最小割集的容量。最大流的流量等于最小割集的容量。 4、容量網絡、容量網絡G，假設，假設 為網絡中從為網絡中從vs到到vt的一條鏈，給的一條鏈，給 定向為從定向為從vs到到vt， 上的弧凡上的弧凡與與 方向一樣的稱為前向弧，凡與方向一樣的稱為前向弧，凡與 方向相反方向相反的稱為后向弧，其集合分別用的稱為后向弧，其集合分別用 和和 表示。表示。f 是一個可行流，假設滿足：是一個可行流，假設滿足： 那么稱那么稱 為從為從vs到到vt 的關于的關于f 的一條增廣的一條增廣鏈。鏈。 ),(0),(0jijijijijijivvcfvvcf 推論推論 可行流可行流f 是最大流的充分必要條件是不存是最大流的充分必要條件是不存在從在從vs到到vt 的關于的關于f 的一條可增廣鏈。的一條可增廣鏈。 2v1v3v4v5v6v7v 13 (5)9