天津大学管理运筹学课件第二章_图论ppt课件

1、 图的基本概念图的基本概念 网络分析网络分析最小支撑树问题最小支撑树问题 最短路径问题最短路径问题网络最大流问题网络最大流问题网络计划问题网络计划问题ABCDACBD图论起源图论起源哥尼斯堡七桥问题哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。结论：每个结点关联的边数均为偶数。问题：一个散步者能否从任一块陆地出发，走过七问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？座桥，且每座桥只走过一次，最后回到出发点？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 最小支撑树问题最小支撑树问题本节主要内容：本节主要内容：树树支撑树支撑树最小支撑树最小支撑树 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用单位：万元如图边上的数字所示。要求设计的费用单位：万元如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用

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，将给一居民区供应煤气，居

9、民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用单位：万元如图边上的数字所示。要求设计的费用单位：万元如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用单位：万元如图边上的数字所示。要求

10、设计的费用单位：万元如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222452634531 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用单位：万元如图边上的数字所示。要求设计的费用单位：万元如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222

11、252634531 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用单位：万元如图边上的数字所示。要求设计的费用单位：万元如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，

12、铺设各用户点的煤气管道所需的费用单位：万元如图边上的数字所示。要求设计的费用单位：万元如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222222634531 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用单位：万元如图边上的数字所示。要求设计的费用单位：万元如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并

13、求所需的总费用。IABCDEFGHJKS222222234531 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用单位：万元如图边上的数字所示。要求设计的费用单位：万元如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为此即为最经济的煤气管道路线，所需的总费用为25万元万元案例分析：默登公司的联网问题案

14、例分析：默登公司的联网问题 默登默登ModernModern公司的管理层决定铺设最先进公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图的光纤网络，为它的主要中心之间提供高速通信。图1 1中的节点显示了该公司主要中心的分布图。虚线是中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本铺设光缆可能的位置。每条虚线旁边的数字表示成本单位：百万美元）。单位：百万美元）。 问：需要铺设哪些光缆使得总成本最低？问：需要铺设哪些光缆使得总成本最低？ 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为该最短路线上的前一节为该最短路线上的前一节点。点。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上可压缩上可压缩可节省费用：可节省费用：2天，天，（5-4)2=2 此时出现两条关键路线，此时出现两条关键路线， T*=101234A(3)B(7)C(2)D(5)直接费用之和直接费用之和3+45，故不能再压。，故不能再压。此时需此时需B、C同时压，但其同时压，但其（3求规定工期下的最小成本方案求规定工期下的最小成本方案方法：方法： 求出正常工期和关键工序求出正常工期和关键工序 在关键工序上压，先压缩其中直接费用率最低的，在关键工序上压，先压缩其中直接费用率最低的，当出现多于一条的关键路线时要同时压，直至满足当出现多于一条的关键路线时要同时压，直至满足规定为止。规定为止。（间接费用率是确定的，与工序无关，只需考虑直接费用）（间接费用率是确定的，与工序无关，只需考虑直接费用）例、某建筑公司安装水管的工程