上海交通大学管理科学-运筹学课件VIP免费

第1页共34页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共34页第5章图与网络分析5.1图论的基本概念5.1.1引言瑞士数学欧拉（Euler）在1736年发表了图论方面的第一篇论文，题为“依据几何位置的解题方法”，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河该河上有两个岛，河上有七座桥，如图5-1（a）所示。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。欧拉用A、B、C、D四点表示河的两岸和小岛，用两点间的联线表示桥，如图5-1（b），该问题可归结为：能否从任一点出发，通过每条边一次且仅一次，再回到该点？即一笔画问题。欧拉证明了这是不可能的，因为图中每点都只与奇数条线相连。这是古典图论中的一个著名问题。运筹学中的“中国邮递员问题”：一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个总是就与欧拉回路有密切的关系。图论的第一本专著是匈牙利数学家O.Konig著的“有限图与无限图的理论”，发表于1936年。随着科学技术的发展及电子计算机的出现和广泛应用，图论得到进一步发展，广泛应用于管理科学、计算机科学、心理学及工程技术管理中，并取得了丰硕的成果。5.1.2基本概念自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形来表示。如为了反映城市之间有没有航班，我们可用图5-2来示意。甲城与乙城，乙城与丙城有飞机到第2页共34页第1页共34页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共34页达，而甲、丙两城没有直飞航班。再如工作分配问题，我们可以用点表示每人与需要完成的工作，点间连线表示每个人可以胜任哪些工作如图5-3所示。在上面的例子中，我们关心图中有多少个点，点与点之间有无连线。这种图是反映对象之间关系的一种工具。图可分为无向图和有向图。两点之间不带箭头的联线为边，两点之间带箭头的联线为弧。由点、边构成的图是无向图，记G=(V,E)由点、弧构成的图是有向图，记D=(V,A)图5-4是一个无向图V=(v1,v2,v3,v4)，E={e1,e2,e3,e4,e5,e6,e7}其中，第3页共34页第2页共34页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共34页图5-5是一个有向图V={v1,v2,v3,v4,v5,v6,v7}，A={a1,a2,a3,⋯,a11}其中，给定一个图G=(V,E)，一个点、边的交错序列(vi1,ei1,vi2,ei2,⋯,vik−1,eik−1,vik)，如果满足eit=[vit,vit+1]，，则称为一条联结vi1和的链，记为(vi1,vi2,⋯,vik)。对于有向图D=(V,A)，从D中去掉所有弧上的箭头，应得到一个无向图，称为D的基础图，记为G(D)。设(vi1,ai1,vi2,ai2,⋯,vik−1,aik−1,vik)是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。在实际问题中，往往只用图来描述的所研究对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，称为“权”，权可以代表如距离、费用通过能力（容量）等等。这种点或边带有某种数量指标的图称为网络（即赋权图）。5.1.3图的矩阵表示用矩阵表示图对研究图的性质及应用常是比较方便的，图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等，这里只介绍其中两种常用矩阵。定义1网络G=(V,E)，其边是(vi,vj)有权wij，构造矩阵A=(aij)n×n其中，第4页共34页第3页共34页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第4页共34页称矩阵A为网络G的权矩阵。图5-6表示图的权矩阵为A=[0924790340230854480670560]定义2对于图G=(V,E)，构造一个矩阵A=(aij)n×n，其中，aij={1(vi,vj)∈E0其他}则称矩阵A为图G的邻接矩阵。图5-7所示图的邻接矩阵A为A=v1v2v3v4v5[0101010110000000000101100]当G为无向图时，邻接矩阵为对称矩阵。5.2最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等。问题表述：给定一个赋权有向图D=(V,A)，对每一弧aij=(vi,vj)，相应地有权w(aij)=wij，又有两点vs,vt∈...