天津大学管理学课件第二章图论

1、2021-11-12管理运筹学 图的基本概念图的基本概念 网络分析网络分析最小支撑树问题最小支撑树问题 最短路径问题最短路径问题网络最大流问题网络最大流问题网络计划问题网络计划问题2021-11-12管理运筹学abcdacbd图论起源图论起源哥尼斯堡七桥问题哥尼斯堡七桥问题结论：结论：每个结点关联的边数均为偶数。每个结点关联的边数均为偶数。问题：问题：一个散步者能否从任一块陆地出发，走过七一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？座桥，且每座桥只走过一次，最后回到出发点？2021-11-12管理运筹学1 图的基本概念图的基本概念由点和边组成，记作由点和边组

2、成，记作g=(v，e)，其中，其中v=v1，v2，vn为结点的集合，为结点的集合，e=e1，e2，em 为边的集合。为边的集合。点表示研究对象点表示研究对象边表示表示研究对象之间的特定关系边表示表示研究对象之间的特定关系1. 图图2021-11-12管理运筹学图图无向图，记作无向图，记作g=(v，e)有向图，记作有向图，记作d=(v，a)例例1：哥尼斯堡桥问题的图为一个无向图。：哥尼斯堡桥问题的图为一个无向图。有向图的边有向图的边称为称为弧弧。例例2：五个球队的比赛情况，：五个球队的比赛情况，v1v2表示表示v1胜胜v2。v1v2v3v4v52、图的分类、图的分类2021-11-12管理运筹学

3、v1v2v3v4v53、链与路、圈与回路、链与路、圈与回路链链点边交错的序列点边交错的序列圈圈起点起点=终点的链终点的链路路点弧交错的序列点弧交错的序列回路回路起点起点=终点的路终点的路v1v2v3v4v5无向图：无向图：有向图：有向图：2021-11-12管理运筹学4、连通图、连通图任何两点之间至少存在一条链的图称为连通图，任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。否则称为不连通图。g1g2g1为不连通图，为不连通图， g2为连通图为连通图例例 ：2021-11-12管理运筹学5、支撑子图、支撑子图图图g=(v，e)和和g=(v ，e )，若，若v =v 且且e e ，则称

4、，则称g 为为g的的支撑子图支撑子图。g2为为g1的支撑子图的支撑子图v1v2v3v4v5g1v1v2v3v4v5g2例例 ：2021-11-12管理运筹学6、赋权图（网络）、赋权图（网络）图的每条边都有一个表示一定实际含义的图的每条边都有一个表示一定实际含义的权数，称为权数，称为赋权图赋权图。记作。记作d=(v，a，c)。55.5v1v2v3v4v53.57.5423例例 ：2021-11-12管理运筹学2 最小支撑树问题最小支撑树问题本节主要内容：本节主要内容：树树支撑树支撑树最小支撑树最小支撑树 例例今有煤气站今有煤气站a，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用

5、户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5abcdefghijks22222254526345312021-11-12管理运筹学1、树中任两点中有且仅有一条链；、树中任两点中有且仅有一条链；2、树任删去一边则不连通，故树是使图保持连通且具有最少边、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。数的一种图形。3、边数、边数 = 顶点数顶点

6、数 1。树树无圈连通图无圈连通图(a)(b)(c)树的性质：树的性质：例例 判断下面图形哪个是树：判断下面图形哪个是树：一、树的概念与性质一、树的概念与性质2021-11-12管理运筹学 若一个图若一个图 g =（v , e）的支撑子图）的支撑子图 t=（v , e ） 构成树，则称构成树，则称 t 为为g的支撑树的支撑树，又称，又称生成树生成树、部分树部分树。二、二、图的支撑树图的支撑树(g)(g1)(g2)(g3)(g4)例例2021-11-12管理运筹学例例 某地新建某地新建5处居民点，拟修处居民点，拟修道路连接道路连接5处，经勘测其道路可铺处，经勘测其道路可铺成如图所示。为使成如图所示

7、。为使5处居民点都有处居民点都有道路相连，问至少要铺几条路？道路相连，问至少要铺几条路？解：解：该问题实为求图该问题实为求图的支撑树问题，的支撑树问题，共需铺共需铺4条路。条路。v1v2v3v4v5 图的支撑树的应用举例图的支撑树的应用举例v1v2v3v4v555.57.53.54232021-11-12管理运筹学问题：问题：求网络的支撑树，使其权和最小。求网络的支撑树，使其权和最小。三、最小支撑树问题三、最小支撑树问题55.5v1v2v3v4v57.53.5423算法算法1（避圈法）：（避圈法）：把边按权从小到大依次把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，添入图中，若出现圈

8、，则删去其中最大边，直至填满直至填满n-1条边为止（条边为止（n为结点数）为结点数） 。例例 求上例中的最小支撑树求上例中的最小支撑树解：解：3v12v4v545v23.5v32021-11-12管理运筹学算法算法2（破圈法）：（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。至图中不存在圈。55.5v1v2v3v4v57.53.54232021-11-12管理运筹学算法算法2（破圈法）：（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。至图中不存在圈

9、。55.5v1v2v3v4v53.54232021-11-12管理运筹学算法算法2（破圈法）：（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。至图中不存在圈。5v1v2v3v4v53.54232021-11-12管理运筹学算法算法2（破圈法）：（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。至图中不存在圈。5v1v2v3v4v53.5232021-11-12管理运筹学 例例今有煤气站今有煤气站a，将给一居民区供应煤气，居民区各，将给一居民区供应煤气

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

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

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

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

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

15、济的煤气管道路线，并求所需的总费用。ijabcdefghks22222223431此即为最经济的煤气管道路线，所需的总费用为此即为最经济的煤气管道路线，所需的总费用为25万元万元2021-11-12管理运筹学案例分析：案例分析：默登公司的联网问题默登公司的联网问题 默登（默登（modernmodern）公司的管理层决定铺设最先进）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图的光纤网络，为它的主要中心之间提供高速通信。图1 1中的节点显示了该公司主要中心的分布图。虚线是中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本铺设光缆可

16、能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。（单位：百万美元）。 问：问：需要铺设哪些光缆使得总成本最低？需要铺设哪些光缆使得总成本最低？ a ab bc ce eg gf fd d2 25 52 27 74 45 57 71 13 31 14 44 4图图1 1 光缆铺设费用图光缆铺设费用图2021-11-12管理运筹学案例分析：案例分析：默登公司的联网问题默登公司的联网问题abcegfd225131图图 1 光缆铺设最小费用图光缆铺设最小费用图2021-11-12管理运筹学问题：问题：求网络中起点到其它点之间的一求网络中起点到其它点之间的一条最短路线。条最短路线。v2v1v3v

17、4v5v6v7v8v9163222266133101044例例 求网络中求网络中v1到到v9的最短路的最短路2021-11-12管理运筹学算法：算法：dijkstra（狄克斯拉）标号法（狄克斯拉）标号法基本思想：基本思想：从起点从起点vs开始，逐步给每个结开始，逐步给每个结点点vj标号标号dj，vi，其中，其中dj为起点为起点vs到到vj的的最短距离，最短距离，vi为该最短路线上的前一节点。为该最短路线上的前一节点。10v2v1v3v4v5v6v7v8v916322226613310440, v11, v1(1) 给起点给起点v1标号标号0, v1(3) 考虑所有这样的边考虑所有这样的边vi

18、, vj，其中，其中viva， vjvb，挑选，挑选其中与起点其中与起点v1距离最短（距离最短（mindi+cij）的）的vj，对，对vj进行标号进行标号(4) 重复重复(2)、(3)，直至终点，直至终点vn标上号标上号dn, vi，则，则dn即为即为v1 vn的最短距离，反向追踪可求出最短路。的最短距离，反向追踪可求出最短路。步骤：步骤：(2) 把顶点集把顶点集v分成分成va：已标号点集：已标号点集vb：未标号点集：未标号点集2021-11-12管理运筹学0, v11, v13, v1(1) 给起点给起点v1标号标号0, v1(3) 考虑所有这样的边考虑所有这样的边vi , vj，其中，其中

19、viva， vjvb，挑选，挑选其中与起点其中与起点v1距离最短（距离最短（mindi+cij）的）的vj，对，对vj进行标号进行标号(4) 重复重复(2)、( 3)，直至终点，直至终点vn标上号标上号dn, vi，则，则dn即为即为v1 vn的最短距离，反向追踪可求出最短路。的最短距离，反向追踪可求出最短路。步骤：步骤：(2) 把顶点集把顶点集v分成分成va：已标号点集：已标号点集vb：未标号点集：未标号点集10v2v1v3v4v5v6v7v8v916322226613310442021-11-12管理运筹学0, v11, v13, v15, v310v2v1v3v4v5v6v7v8v916

20、322226613310442021-11-12管理运筹学0, v11, v13, v15, v36, v210v2v1v3v4v5v6v7v8v916322226613310442021-11-12管理运筹学0, v11, v13, v15, v36, v29, v510v2v1v3v4v5v6v7v8v916322226613310442021-11-12管理运筹学0, v11, v13, v15, v36, v29, v510, v510v2v1v3v4v5v6v7v8v916322226613310442021-11-12管理运筹学0, v11, v13, v15, v36, v29,

21、 v510, v512, v5此时终点此时终点v9已标号已标号12, v5，则，则12即为即为v1 vn的最的最短距离，反向追踪可求出最短路短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v916322226613310442021-11-12管理运筹学0, v11, v13, v15, v36, v29, v510, v512, v5v1到到v9的最短路为：的最短路为：v1 v3 v2 v5 v9，最短距离为最短距离为1210v2v1v3v4v5v6v7v8v916322226613310442021-11-12管理运筹学课堂练习课堂练习 p129 习题习题5.30, v14

22、, v13, v15, v26, v29, v77, v4/ v68.5, v66, v2v2v1v5v4v3v6v8v7v943232.5335234212021-11-12管理运筹学课堂练习课堂练习 无向图情形无向图情形求网络中求网络中v1至至v7的最短路。的最短路。v1v2v3v4v5v6v72253557157132021-11-12管理运筹学课堂练习课堂练习 无向图情形无向图情形答案（答案（1）：）：v1v2v3v4v5v6v72253557157130,v12,v13,v14,v2/ v47,v38,v513,v62021-11-12管理运筹学课堂练习课堂练习 无向图情形无向图情形

23、答案（答案（2）：）：v1v2v3v4v5v6v72253557157130,v12,v13,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=

24、1,5; j= 2,6权权cij： i年初年初 j年初的费用，即年初的费用，即cij= i年初购买费年初购买费+（j-i）年里的维修费）年里的维修费30224159162230411723311723182021-11-12管理运筹学引例：下图为引例：下图为v1到到v6的一交通网，权表示相应运输线的最的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从大通过能力，制定一方案，使从v1到到v6的产品数量最多。的产品数量最多。v2v1v3v4v5v6810417553116353122133622021-11-12管理运筹学设有网络设有网络d=(v, a, c)，其中，其中c=cij， c

25、ij为弧为弧(vi,vj)上的容量，现在上的容量，现在d上要通过一个流上要通过一个流f=fij， fij为弧为弧(vi,vj)上的流量。上的流量。 问题：问题：如何安排如何安排fij，可使网络，可使网络d上的总流量上的总流量v最大？最大？v2v1v3v4v5v681041755311635312213362一、一般提法：一、一般提法：2021-11-12管理运筹学max v=v（f） ijijcf 0 tsitifvsifvffjjjiij,0)()(容量约束容量约束平衡约束平衡约束s.t.v2vsv3v4v5vt81041755311635312213362注：满足约束条件的流注：满足约束条

26、件的流f称为可行流称为可行流2021-11-12管理运筹学饱和弧饱和弧 fij=cij非饱和弧非饱和弧 fijp，则正常工期即为，则正常工期即为t*；v 否则，在关键工序上压缩。先压缩否则，在关键工序上压缩。先压缩q最小的，直至不最小的，直至不能再压为止，再压次小的，以此类推。直至能再压为止，再压次小的，以此类推。直至qp为止。为止。（注：注：当压缩引起出现新的关键路线时，若压要同时压。）当压缩引起出现新的关键路线时，若压要同时压。）v 压缩时间压缩时间t的确定：的确定：0),(),(min),(),(min,min),( jirjirjitjittiji ，其其中中：的的压压缩缩下下限限为为

27、工工序序),(),(jijit若若t取值取值 ，则产生了，则产生了新的关键路线新的关键路线2021-11-12管理运筹学例例：设某工程有关资料如表，间接费用率：设某工程有关资料如表，间接费用率p=5； 求最低费用工期。求最低费用工期。工序工序紧前紧前工序工序工序工序时间时间直接直接费用率费用率可压可压天数天数a/3/ba731ca443dc562解解：画出网络图，：画出网络图， t=12，关键路线：，关键路线：a-c-d。1234a(3)b(7)c(4)d(5) 先压先压c，在，在c上可压缩上可压缩可节省费用：可节省费用：2天，天，（5-4)2=2 此时出现两条关键路线，此时出现两条关键路线，

28、 t*=101234a(3)b(7)c(2)d(5)直接费用之和直接费用之和3+45，故不能再压。，故不能再压。此时需此时需b、c同时压，但其同时压，但其2021-11-12管理运筹学（3）求规定工期下的最小成本方案）求规定工期下的最小成本方案方法：方法： 求出正常工期和关键工序求出正常工期和关键工序 在关键工序上压，先压缩其中直接费用率最低的，在关键工序上压，先压缩其中直接费用率最低的，当出现多于一条的关键路线时要同时压，直至满足当出现多于一条的关键路线时要同时压，直至满足规定为止。规定为止。（间接费用率是确定的，与工序无关，只需考虑直接费用）（间接费用率是确定的，与工序无关，只需考虑直接费用）2021-1