天津大学管理运筹学课件第二章_图论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.5ABCDEFGHIJKS22222252634531 例

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

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

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

14、odernModern公司的管理层决议铺设最先进公司的管理层决议铺设最先进的光纤网络，为它的主要中心之间提供高速通讯。图的光纤网络，为它的主要中心之间提供高速通讯。图1 1中的节点显示了该公司主要中心的分布图。虚线是中的节点显示了该公司主要中心的分布图。虚线是铺设光缆能够的位置。每条虚线旁边的数字表示本钱铺设光缆能够的位置。每条虚线旁边的数字表示本钱单位：百万美圆。单位：百万美圆。 问：需求铺设哪些光缆使得总本钱最低？问：需求铺设哪些光缆使得总本钱最低？ A AB BC CE EG GF FD D2 25 52 27 74 45 57 71 13 31 14 44 4图图1 1 光缆铺设费用图

15、光缆铺设费用图案例分析：默登公司的联网问题案例分析：默登公司的联网问题ABCEGFD225131图图 1 光缆铺设最小费用图光缆铺设最小费用图问题：求网络中起点到其它点之间的一问题：求网络中起点到其它点之间的一条最短道路。条最短道路。v2v1v3v4v5v6v7v8v9163222266133101044例例 求网络中求网络中v1到到v9的最短路的最短路算法：算法：Dijkstra狄克斯拉标号法狄克斯拉标号法根本思想：从起点根本思想：从起点vs开场，逐渐给每个结开场，逐渐给每个结点点vj标号标号dj，vi，其中，其中dj为起点为起点vs到到vj的最短间隔，的最短间隔，vi为该最短道路上的前一节

16、为该最短道路上的前一节点。点。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) 把顶点集把顶点集V分成分成VA：已标号点：已

17、标号点集集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：已标号点：已标号点集集VB：未标号点集：未标号点集10v2v1v

18、3v4v5v6v7v8v916322226613310440, v11, v13, v15, v310v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v210v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v29, v510v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v8v916322226613310440, v11, v13, v15

19、, 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, v14, v13, v15, v26,

20、 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,v14,v2/ v47,v38,v513,v6最

21、短路模型的运用最短路模型的运用设备更新问题设备更新问题P119 例例 5.3v2v1v3v4v5v6第第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= i年初购买费年初购买费+j-i年里的维修费年里的维修

22、费3022415916223041172331172318引例：以下图为引例：以下图为V1到到V6的一交通网，权表示相应运输线的的一交通网，权表示相应运输线的最大经过才干，制定一方案，使从最大经过才干，制定一方案，使从V1到到V6的产品数量最多。的产品数量最多。v2v1v3v4v5v681041755311635312213362设有网络设有网络D=(V, A, C)，其中，其中C=cij， cij为弧为弧(vi,vj)上的容量，如今上的容量，如今D上要经过一个流上要经过一个流f=fij， fij为弧为弧(vi,vj)上的流量。上的流量。 问题：如何安排问题：如何安排fij，可使网络，可使网络

23、D上的总流量上的总流量V最大？最大？v2v1v3v4v5v681041755311635312213362一、普通提法：一、普通提法：max v=vf ijijcf 0 tsitifvsifvffjjjiij,0)()(容量约束容量约束平衡约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362注：满足约束条件的流注：满足约束条件的流f称为可行流称为可行流饱和弧饱和弧 fij=cij非饱和弧非饱和弧 fijp，那么正常工期即为，那么正常工期即为T*；v 否那么，在关键工序上紧缩。先紧缩否那么，在关键工序上紧缩。先紧缩q最小的，直至最小的，直至不能再压为止，再压

24、次小的，以此类推。直至不能再压为止，再压次小的，以此类推。直至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求规定工期下的最小本钱方案求规定工期下的最小本钱方案方法：方法： 求出正常工期和关键工序求出正常工期和关键工序 在关键工序上压，先紧缩其中直接费用率最低的，在关键工序上压，先紧缩其中直接费用率最低的，当出现多于一条的关键道路时要同时压，直至满足当出现多于一条的关键道路时要同时压，直至满足规定为止。规定为止。间接费用率是确定的，与工序无关，只需思索直接费用间接费用率是确定的，与工序无关，只需思索直接费用例、某建筑公司