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

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

2、，e2，em 為邊為邊的集合。的集合。點表示研究對象點表示研究對象邊表示表示研究對象之間的特定關系邊表示表示研究對象之間的特定關系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、賦權圖網絡）、賦權圖網絡）圖的每條邊都有一個表示一定實際含義的圖的每條邊都

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

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

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

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

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

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

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

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

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

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

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

15、 14 44 4圖圖1 1 光纜鋪設費用圖光纜鋪設費用圖案例分析：默登公司的聯網問題案例分析：默登公司的聯網問題ABCEGFD225131圖圖 1 光纜鋪設最小費用圖光纜鋪設最小費用圖問題：求網絡中起點到其它點之間的一問題：求網絡中起點到其它點之間的一條最短路線。條最短路線。v2v1v3v4v5v6v7v8v9163222266133101044例例 求網絡中求網絡中v1到到v9的最短路的最短路算法：算法：Dijkstra狄克斯拉標號法狄克斯拉標號法基本思想：從起點基本思想：從起點vs開始，逐步給每個結開始，逐步給每個結點點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課堂練習課堂練習 無向圖情形無向圖情形求網絡中求網絡中v1至至v7的最短路。的最短路。v1v2v3v4v5v6v7225355715713課堂練習課堂練習 無向圖情形無向圖情形答案答案1）：）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v6課堂練習課堂練習 無向圖情形無向圖情形答案答案2）：）：v1v2v3v4v5v6v72253557157130,v12,v13

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

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

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

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

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