《天津大学管理运筹学课件第二章图论教学幻灯片》由会员分享，可在线阅读，更多相关《天津大学管理运筹学课件第二章图论教学幻灯片（110页珍藏版）》请在金锄头文库上搜索。
1、2020/6/30,管理运筹学,第二章 图论与网络分析,图的基本概念,网络分析,最小支撑树问题 最短路径问题 网络最大流问题 网络计划问题,2020/6/30,管理运筹学,图论起源哥尼斯堡七桥问题,结论：每个结点关联的边数均为偶数。,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？,2020/6/30,管理运筹学,1 图的基本概念,由点和边组成，记作G=(V，E)，其中V=v1，v2，vn为结点的集合，E=e1，e2，em 为边的集合。,点表示研究对象,边表示表示研究对象之间的特定关系,1. 图,2020/6/30,管理运筹学,图,无向图，记作G=(V，E
2、),有向图，记作D=(V，A),例1：哥尼斯堡桥问题的图为一个无向图。,有向图的边称为弧。,2、图的分类,2020/6/30,管理运筹学,4、连通图,G1为不连通图， G2为连通图,例 ：,2020/6/30,管理运筹学,5、支撑子图,图G=(V，E)和G=(V ，E )，若V =V 且E E ，则称G 为G的支撑子图。,G2为G1的支撑子图,例 ：,2020/6/30,管理运筹学,6、赋权图（网络）,图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作D=(V，A，C)。,例 ：,2020/6/30,管理运筹学,2 最小支撑树问题,本节主要内容：,树,支撑树,最小支撑树,2020/6/
3、30,管理运筹学,1、树中任两点中有且仅有一条链； 2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。 3、边数 = 顶点数 1。,树,无圈连通图,树的性质：,例 判断下面图形哪个是树：,一、树的概念与性质,2020/6/30,管理运筹学,若一个图 G =（V , E）的支撑子图 T=（V , E） 构成树，则称 T 为G的支撑树，又称生成树、部分树。,二、图的支撑树,例,2020/6/30,管理运筹学,例 某地新建5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？,解：,该问题实为求图的支撑树问题，共需铺4条路。,图的
4、支撑树的应用举例,2020/6/30,管理运筹学,问题：求网络的支撑树，使其权和最小。,三、最小支撑树问题,算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数） 。,例 求上例中的最小支撑树,解：,2020/6/30,管理运筹学,算法2（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。,2020/6/30,管理运筹学,算法2（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。,5,5.5,v1,v2,v3,v4,v5,3.5,4,2,3,2020/6/30,管理运筹学,算法2（破圈法）
5、： 在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。,5,v1,v2,v3,v4,v5,3.5,4,2,3,2020/6/30,管理运筹学,算法2（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。,5,v1,v2,v3,v4,v5,3.5,2,3,2020/6/30,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2020/6/30,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如
6、图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2020/6/30,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2020/6/30,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2020/6/30,管理运筹学,
7、例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2020/6/30,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。,2020/6/30,管理运筹学,例今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管
8、道路线，并求所需的总费用。,此即为最经济的煤气管道路线，所需的总费用为25万元,2020/6/30,管理运筹学,案例分析：默登公司的联网问题,默登（Modern）公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图1中的节点显示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。每条虚线旁边的数字表示成本（单位：百万美元）。 问：需要铺设哪些光缆使得总成本最低？,2020/6/30,管理运筹学,案例分析：默登公司的联网问题,2020/6/30,管理运筹学,3 最短路问题,问题：求网络中起点到其它点之间的一条最短路线。,2020/6/30,管理运筹学,算法：Dijkstra（
9、狄克斯拉）标号法,基本思想：从起点vs开始，逐步给每个结点vj标号dj，vi，其中dj为起点vs到vj的最短距离，vi为该最短路线上的前一节点。,0, v1,1, v1,(1) 给起点v1标号0, v1,(3) 考虑所有这样的边vi , vj，其中viVA， vjVB，挑选其中与起点v1距离最短（mindi+cij）的vj，对vj进行标号,(4) 重复(2)、(3)，直至终点vn标上号dn, vi，则dn即为v1 vn的最短距离，反向追踪可求出最短路。,步骤：,2020/6/30,管理运筹学,0, v1,1, v1,3, v1,2020/6/30,管理运筹学,0, v1,1, v1,3, v1
10、,5, v3,2020/6/30,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,2020/6/30,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,2020/6/30,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,2020/6/30,管理运筹学,0, v1,1, v1,3, v1,5, v3,6, v2,9, v5,10, v5,12, v5,此时终点v9已标号12, v5，则12即为v1 vn的最短距离，反向追踪可求出最短路,2020/6/30,管理运筹学,0, v1,1, v1
11、,3, v1,5, v3,6, v2,9, v5,10, v5,12, v5,v1到v9的最短路为：v1 v3 v2 v5 v9，最短距离为12,2020/6/30,管理运筹学,课堂练习 P129 习题5.3,0, v1,4, v1,3, v1,5, v2,6, v2,9, v7,7, v4/ v6,8.5, v6,6, v2,2020/6/30,管理运筹学,课堂练习 无向图情形,求网络中v1至v7的最短路。,2020/6/30,管理运筹学,课堂练习 无向图情形,答案（1）：,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1
12、,4,v2/ v4,7,v3,8,v5,13,v6,2020/6/30,管理运筹学,课堂练习 无向图情形,答案（2）：,v1,v2,v3,v4,v5,v6,v7,2,2,5,3,5,5,7,1,5,7,1,3,0,v1,2,v1,3,v1,4,v2/ v4,7,v3,8,v5,13,v6,最短路模型的应用设备更新问题（P119 例 5.3）,16,分析：,结点：V=v1，v6， vi表示第i年初；,边： E=(vi，vj) 表示第i年初购买，用至第j年初；i= 1,5; j= 2,6,权cij： i年初 j年初的费用，即cij= i年初购买费+（j-i）年里的维修费,30,22,41,59,1
13、6,22,30,41,17,23,31,17,23,18,2020/6/30,管理运筹学,4 网络最大流问题,引例：下图为V1到V6的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V1到V6的产品数量最多。,2020/6/30,管理运筹学,设有网络D=(V, A, C)，其中C=cij， cij为弧(vi,vj)上的容量，现在D上要通过一个流f=fij， fij为弧(vi,vj)上的流量。 问题：如何安排fij，可使网络D上的总流量V最大？,一、一般提法：,2020/6/30,管理运筹学,二、最大流问题的模型,max v=v（f）,容量约束,平衡约束,注：满足约束条件的流f称为可行
14、流,2020/6/30,管理运筹学,三、基本概念与定理,2020/6/30,管理运筹学,2. 增广链,f为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,2020/6/30,管理运筹学,2. 增广链,f为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,2020/6/30,管理运筹学,2. 增广链,f为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,2020/
15、6/30,管理运筹学,2. 增广链,f为一可行流，u为vs至vt的链，令u+=正向弧， u-=反向弧。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。,2020/6/30,管理运筹学,3. 截集与截量,把V分成两部分：V1和V2(V1 V2= , V1 V2= V)且vs V1、 vt V2，则弧集(V1,V2)称为D的截集。 截集上的容量和称为截量，记为C(V1,V2) 。,(vs,v2), (v1,vt)； 截量为： C(V1,V2) =4+3=7,截集为：,2020/6/30,管理运筹学,4. 流量与截量的关系,任一可行流的流量都不会超过任一截集的截量 （ v(f)=f (V1,V2) - f (V2,V1) f (V1,V2) C (V1,V2) ）,最大流最小截定理：网络的最大流量等于最小截量。,2020/6/30,管理运筹学,例. 如图所示的网络中，
