天津大學管理運籌學課件第二章_圖論ppt課件

1、 圖的基本概念圖的基本概念 網(wǎng)絡(luò)分析網(wǎng)絡(luò)分析最小支撐樹問題最小支撐樹問題 最短路徑問題最短路徑問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)計劃問題網(wǎng)絡(luò)計劃問題ABCDACBD圖論起源圖論起源哥尼斯堡七橋問題哥尼斯堡七橋問題結(jié)論：每個結(jié)點關(guān)聯(lián)的邊數(shù)均為偶數(shù)。結(jié)論：每個結(jié)點關(guān)聯(lián)的邊數(shù)均為偶數(shù)。問題：一個散步者能否從任一塊陸地出發(fā)，走過七問題：一個散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點？座橋，且每座橋只走過一次，最后回到出發(fā)點？1 圖的基本概念圖的基本概念由點和邊組成，記作由點和邊組成，記作G=(V，E)，其中，其中V=v1，v2，vn為結(jié)點的集為結(jié)點的集合，合，E=e1

2、，e2，em 為邊為邊的集合。的集合。點表示研究對象點表示研究對象邊表示表示研究對象之間的特定關(guān)系邊表示表示研究對象之間的特定關(guān)系1. 圖圖圖圖無向圖，記作無向圖，記作G=(V，E)有向圖，記作有向圖，記作D=(V，A)例例1：哥尼斯堡橋問題的圖為一個無向圖。：哥尼斯堡橋問題的圖為一個無向圖。有向圖的邊有向圖的邊稱為弧。稱為弧。例例2：五個球隊的比賽情況，：五個球隊的比賽情況，v1v2 表示表示v1勝勝v2。v1v2v3v4v52、圖的分類、圖的分類v1v2v3v4v53、鏈與路、圈與回路、鏈與路、圈與回路鏈鏈點邊交錯的序列點邊交錯的序列圈圈起點起點=終點的鏈終點的鏈路路點弧交錯的序列點弧交錯

3、的序列回路回路起點起點=終點的路終點的路v1v2v3v4v5無向圖：無向圖：有向圖：有向圖：4、連通圖、連通圖任何兩點之間至少存在一條鏈的圖稱為連通圖，任何兩點之間至少存在一條鏈的圖稱為連通圖，否則稱為不連通圖。否則稱為不連通圖。G1G2G1為不連通圖，為不連通圖， G2為連通圖為連通圖例例 ：5、支撐子圖、支撐子圖圖圖G=(V，E)和和G=(V ，E )，若，若V =V 且且E E ，則稱，則稱G 為為G的支撐子圖。的支撐子圖。G2為為G1的支撐子圖的支撐子圖v1v2v3v4v5G1v1v2v3v4v5G2例例 ：6、賦權(quán)圖網(wǎng)絡(luò)）、賦權(quán)圖網(wǎng)絡(luò)）圖的每條邊都有一個表示一定實際含義的圖的每條邊都

4、有一個表示一定實際含義的權(quán)數(shù)，稱為賦權(quán)圖。記作權(quán)數(shù)，稱為賦權(quán)圖。記作D=(V，A，C)。55.5v1v2v3v4v53.57.5423例例 ：2 最小支撐樹問題最小支撐樹問題本節(jié)主要內(nèi)容：本節(jié)主要內(nèi)容：樹樹支撐樹支撐樹最小支撐樹最小支撐樹 例例今有煤氣站今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。一個最經(jīng)濟的煤氣管道路線，并求所需的總費用

5、。3.5ABCDEFGHIJKS22222254526345311、樹中任兩點中有且僅有一條鏈；、樹中任兩點中有且僅有一條鏈；2、樹任刪去一邊則不連通，故樹是使圖保持連通且具有最少邊、樹任刪去一邊則不連通，故樹是使圖保持連通且具有最少邊數(shù)的一種圖形。數(shù)的一種圖形。3、邊數(shù)、邊數(shù) = 頂點數(shù)頂點數(shù) 1。樹樹無圈連通圖無圈連通圖(A)(B)(C)樹的性質(zhì)：樹的性質(zhì)：例例 判斷下面圖形哪個是樹：判斷下面圖形哪個是樹：一、樹的概念與性質(zhì)一、樹的概念與性質(zhì) 若一個圖若一個圖 G =（V , E的支撐子圖的支撐子圖 T=（V , E） 構(gòu)成樹，則稱構(gòu)成樹，則稱 T 為為G的支撐樹，又稱生成樹、部分樹。的支

6、撐樹，又稱生成樹、部分樹。二、圖的支撐樹二、圖的支撐樹(G)(G1)(G2)(G3)(G4)例例例例 某地新建某地新建5處居民點，擬修處居民點，擬修道路連接道路連接5處，經(jīng)勘測其道路可鋪處，經(jīng)勘測其道路可鋪成如圖所示。為使成如圖所示。為使5處居民點都有處居民點都有道路相連，問至少要鋪幾條路？道路相連，問至少要鋪幾條路？解：解：該問題實為求圖該問題實為求圖的支撐樹問題，的支撐樹問題，共需鋪共需鋪4條路。條路。v1v2v3v4v5 圖的支撐樹的應(yīng)用舉例圖的支撐樹的應(yīng)用舉例v1v2v3v4v555.57.53.5423問題：求網(wǎng)絡(luò)的支撐樹，使其權(quán)和最小。問題：求網(wǎng)絡(luò)的支撐樹，使其權(quán)和最小。三、最小支

7、撐樹問題三、最小支撐樹問題55.5v1v2v3v4v57.53.5423算法算法1避圈法）：把邊按權(quán)從小到大依次避圈法）：把邊按權(quán)從小到大依次添入圖中，若出現(xiàn)圈，則刪去其中最大邊，添入圖中，若出現(xiàn)圈，則刪去其中最大邊，直至填滿直至填滿n-1條邊為止條邊為止n為結(jié)點數(shù)）為結(jié)點數(shù)） 。例例 求上例中的最小支撐樹求上例中的最小支撐樹解：解：3v12v4v545v23.5v3算法算法2破圈法）：破圈法）： 在圖中找圈，并刪除其中最大邊。如此進行下去，直在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。至圖中不存在圈。55.5v1v2v3v4v57.53.5423算法算法2破圈法）：破圈法）

8、： 在圖中找圈，并刪除其中最大邊。如此進行下去，直在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。至圖中不存在圈。55.5v1v2v3v4v53.5423算法算法2破圈法）：破圈法）： 在圖中找圈，并刪除其中最大邊。如此進行下去，直在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。至圖中不存在圈。5v1v2v3v4v53.5423算法算法2破圈法）：破圈法）： 在圖中找圈，并刪除其中最大邊。如此進行下去，直在圖中找圈，并刪除其中最大邊。如此進行下去，直至圖中不存在圈。至圖中不存在圈。5v1v2v3v4v53.523 例例今有煤氣站今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居

9、民區(qū)各，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222225452634531 例例今有煤氣站今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用單位：萬元如圖邊上的數(shù)字所示。要求

10、設(shè)計的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS222222452634531 例例今有煤氣站今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS22222

11、252634531 例例今有煤氣站今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。3.5ABCDEFGHIJKS2222222634531 例例今有煤氣站今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需用戶所在位置如圖所示，

12、鋪設(shè)各用戶點的煤氣管道所需的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。ABCDEFGHIJKS2222222634531 例例今有煤氣站今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。一個最經(jīng)濟的煤氣管道路線，并

13、求所需的總費用。IABCDEFGHJKS222222234531 例例今有煤氣站今有煤氣站A，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各，將給一居民區(qū)供應(yīng)煤氣，居民區(qū)各用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需用戶所在位置如圖所示，鋪設(shè)各用戶點的煤氣管道所需的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計的費用單位：萬元如圖邊上的數(shù)字所示。要求設(shè)計一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。一個最經(jīng)濟的煤氣管道路線，并求所需的總費用。IJABCDEFGHKS22222223431此即為最經(jīng)濟的煤氣管道路線，所需的總費用為此即為最經(jīng)濟的煤氣管道路線，所需的總費用為25萬元萬元案例分析：默登公司的聯(lián)網(wǎng)問題案

14、例分析：默登公司的聯(lián)網(wǎng)問題 默登默登ModernModern公司的管理層決定鋪設(shè)最先進公司的管理層決定鋪設(shè)最先進的光纖網(wǎng)絡(luò)，為它的主要中心之間提供高速通信。圖的光纖網(wǎng)絡(luò)，為它的主要中心之間提供高速通信。圖1 1中的節(jié)點顯示了該公司主要中心的分布圖。虛線是中的節(jié)點顯示了該公司主要中心的分布圖。虛線是鋪設(shè)光纜可能的位置。每條虛線旁邊的數(shù)字表示成本鋪設(shè)光纜可能的位置。每條虛線旁邊的數(shù)字表示成本單位：百萬美元）。單位：百萬美元）。 問：需要鋪設(shè)哪些光纜使得總成本最低？問：需要鋪設(shè)哪些光纜使得總成本最低？ A AB BC CE EG GF FD D2 25 52 27 74 45 57 71 13 31

15、 14 44 4圖圖1 1 光纜鋪設(shè)費用圖光纜鋪設(shè)費用圖案例分析：默登公司的聯(lián)網(wǎng)問題案例分析：默登公司的聯(lián)網(wǎng)問題ABCEGFD225131圖圖 1 光纜鋪設(shè)最小費用圖光纜鋪設(shè)最小費用圖問題：求網(wǎng)絡(luò)中起點到其它點之間的一問題：求網(wǎng)絡(luò)中起點到其它點之間的一條最短路線。條最短路線。v2v1v3v4v5v6v7v8v9163222266133101044例例 求網(wǎng)絡(luò)中求網(wǎng)絡(luò)中v1到到v9的最短路的最短路算法：算法：Dijkstra狄克斯拉標號法狄克斯拉標號法基本思想：從起點基本思想：從起點vs開始，逐步給每個結(jié)開始，逐步給每個結(jié)點點vj標號標號dj，vi，其中，其中dj為起點為起點vs到到vj的最短距

16、離，的最短距離，vi為該最短路線上的前一節(jié)為該最短路線上的前一節(jié)點。點。10v2v1v3v4v5v6v7v8v916322226613310440, v11, v1(1) 給起點給起點v1標號標號0, v1(3) 考慮所有這樣的邊考慮所有這樣的邊vi , vj，其中，其中viVA， vjVB，挑，挑選其中與起點選其中與起點v1距離最短距離最短mindi+cij）的）的vj，對，對vj進行進行標號標號(4) 反復反復(2)、(3)，直至終點，直至終點vn標上號標上號dn, vi，則，則dn即即為為v1 vn的最短距離，反向追蹤可求出最短路。的最短距離，反向追蹤可求出最短路。步驟：步驟：(2) 把

17、頂點集把頂點集V分成分成VA：已標號點：已標號點集集VB：未標號點集：未標號點集0, v11, v13, v1(1) 給起點給起點v1標號標號0, v1(3) 考慮所有這樣的邊考慮所有這樣的邊vi , vj，其中，其中viVA， vjVB，挑，挑選其中與起點選其中與起點v1距離最短距離最短mindi+cij）的）的vj，對，對vj進行進行標號標號(4) 反復反復(2)、( 3)，直至終點，直至終點vn標上號標上號dn, vi，則，則dn即即為為v1 vn的最短距離，反向追蹤可求出最短路。的最短距離，反向追蹤可求出最短路。步驟：步驟：(2) 把頂點集把頂點集V分成分成VA：已標號點：已標號點集集

18、VB：未標號點集：未標號點集10v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v310v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v210v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v29, v510v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v8v916322226613

19、310440, v11, v13, v15, v36, v29, v510, v512, v5此時終點此時終點v9已標號已標號12, v5，則，則12即為即為v1 vn的的最短距離，反向追蹤可求出最短路最短距離，反向追蹤可求出最短路10v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v29, v510, v512, v5v1到到v9的最短路為：的最短路為：v1 v3 v2 v5 v9，最短距離，最短距離為為1210v2v1v3v4v5v6v7v8v91632222661331044課堂練習課堂練習 P129 習題習題5.30,

20、v14, v13, v15, v26, v29, v77, v4/ v68.5, v66, v2v2v1v5v4v3v6v8v7v943232.533523421課堂練習課堂練習 無向圖情形無向圖情形求網(wǎng)絡(luò)中求網(wǎng)絡(luò)中v1至至v7的最短路。的最短路。v1v2v3v4v5v6v7225355715713課堂練習課堂練習 無向圖情形無向圖情形答案答案1）：）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v6課堂練習課堂練習 無向圖情形無向圖情形答案答案2）：）：v1v2v3v4v5v6v72253557157130,v12,v13

21、,v14,v2/ v47,v38,v513,v6最短路模型的應(yīng)用最短路模型的應(yīng)用設(shè)備更新問題設(shè)備更新問題P119 例例 5.3）v2v1v3v4v5v6第第i年年12345價格價格ai11 11121213使用壽命使用壽命 01 1223 34 45費用費用bj56811180,v116,v122,v130,v141,v153,v3/v416分析：分析：結(jié)點：結(jié)點：V=v1，v6， vi表示第表示第i年初；年初；邊：邊： E=(vi，vj) 表示第表示第i年初購買，用至第年初購買，用至第j年初；年初；i= 1,5; j= 2,6權(quán)權(quán)cij： i年初年初 j年初的費用，即年初的費用，即cij=

22、i年初購買費年初購買費+（j-i年里的維修費年里的維修費3022415916223041172331172318引例：下圖為引例：下圖為V1到到V6的一交通網(wǎng)，權(quán)表示相應(yīng)運輸線的最的一交通網(wǎng)，權(quán)表示相應(yīng)運輸線的最大通過能力，制定一方案，使從大通過能力，制定一方案，使從V1到到V6的產(chǎn)品數(shù)量最多。的產(chǎn)品數(shù)量最多。v2v1v3v4v5v681041755311635312213362設(shè)有網(wǎng)絡(luò)設(shè)有網(wǎng)絡(luò)D=(V, A, C)，其中，其中C=cij， cij為弧為弧(vi,vj)上的容量，現(xiàn)在上的容量，現(xiàn)在D上要通過一個流上要通過一個流f=fij， fij為弧為弧(vi,vj)上的流量。上的流量。 問題

23、：如何安排問題：如何安排fij，可使網(wǎng)絡(luò)，可使網(wǎng)絡(luò)D上的總流量上的總流量V最大？最大？v2v1v3v4v5v681041755311635312213362一、一般提法：一、一般提法：max v=vf） ijijcf 0 tsitifvsifvffjjjiij,0)()(容量約束容量約束平衡約束平衡約束s.t.v2Vsv3v4v5Vt81041755311635312213362注：滿足約束條件的流注：滿足約束條件的流f稱為可行流稱為可行流飽和弧飽和弧 fij=cij非飽和弧非飽和弧 fijp，則正常工期即為，則正常工期即為T*；v 否則，在關(guān)鍵工序上壓縮。先壓縮否則，在關(guān)鍵工序上壓縮。先壓縮

24、q最小的，直至不最小的，直至不能再壓為止，再壓次小的，以此類推。直至能再壓為止，再壓次小的，以此類推。直至qp為止。為止。（注：當壓縮引起出現(xiàn)新的關(guān)鍵路線時，若壓要同時壓。）（注：當壓縮引起出現(xiàn)新的關(guān)鍵路線時，若壓要同時壓。）v 壓縮時間壓縮時間t的確定：的確定：0),(),(min),(),(min,min),( jiRjiRjitjittIji ，其其中中：的的壓壓縮縮下下限限為為工工序序),(),(jijit若若t取值取值 ，則產(chǎn)生了，則產(chǎn)生了新的關(guān)鍵路線新的關(guān)鍵路線例：設(shè)某工程有關(guān)資料如表，間接費用率例：設(shè)某工程有關(guān)資料如表，間接費用率p=5； 求最低費用工期。求最低費用工期。工序工序

25、緊前緊前工序工序工序工序時間時間直接直接費用率費用率可壓可壓天數(shù)天數(shù)A/3/BA731CA443DC562解：畫出網(wǎng)絡(luò)圖，解：畫出網(wǎng)絡(luò)圖， T=12，關(guān)鍵路線：，關(guān)鍵路線：A-C-D。1234A(3)B(7)C(4)D(5) 先壓先壓C，在，在C上可壓縮上可壓縮可節(jié)省費用：可節(jié)省費用：2天，天，（5-4)2=2 此時出現(xiàn)兩條關(guān)鍵路線，此時出現(xiàn)兩條關(guān)鍵路線， T*=101234A(3)B(7)C(2)D(5)直接費用之和直接費用之和3+45，故不能再壓。，故不能再壓。此時需此時需B、C同時壓，但其同時壓，但其（3求規(guī)定工期下的最小成本方案求規(guī)定工期下的最小成本方案方法：方法： 求出正常工期和關(guān)鍵工序求出正常工期和關(guān)鍵工序 在關(guān)鍵工序上壓，先壓縮其中直接費用率最低的，在關(guān)鍵工序上壓，先壓縮其中直接費用率最低的，當出現(xiàn)多于一條的關(guān)鍵路線時要同時壓，直至滿足當出現(xiàn)多于一條的關(guān)鍵路線時要同時壓，直至滿足規(guī)定為止。規(guī)定為止。（間接費用率是確定的，與工序無關(guān)，只需考慮直接費用）（間接費用率是確定的，與工序無關(guān)，只需考慮直接費用）例、某建筑公司安裝水管的工程