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

1第5章图与网络分析5.1图论的基本概念5.1.1引言瑞士数学欧拉（Euler）在1736年发表了图论方面的第一篇论文，题为“依据几何位置的解题方法”，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该河上有两个岛，河上有七座桥，如图5-1（a）所示。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。ABCD（a）ACBD（b）图5-1····欧拉用A、B、C、D四点表示河的两岸和小岛，用两点间的联线表示桥，如图5-1（b），该问题可归结为：能否从任一点出发，通过每条边一次且仅一次，再回到该点？即一笔画问题。欧拉证明了这是不可能的，因为图中每点都只与奇数条线相连。这是古典图论中的一个著名问题。运筹学中的“中国邮递员问题”：一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个总是就与欧拉回路有密切的关系。图论的第一本专著是匈牙利数学家O.Konig著的“有限图与无限图的理论”，发表于1936年。随着科学技术的发展及电子计算机的出现和广泛应用，图论得到进一步发展，广泛应用于管理科学、计算机科学、心理学及工程技术管理中，并取得了丰硕的成果。5.1.2基本概念自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形来表示。如为了反映城市之间有没有航班，我们可用图5-2来示意。甲城与乙城，乙城与丙城有飞机到达，而甲、丙两城没有直飞航班。再如工作分配问题，我们可以用点表示每人与需要完成的工作，2点间连线表示每个人可以胜任哪些工作如图5-3所示。甲乙丙图5-2甲乙丙工人ABCD工作图5-3··········在上面的例子中，我们关心图中有多少个点，点与点之间有无连线。这种图是反映对象之间关系的一种工具。图可分为无向图和有向图。两点之间不带箭头的联线为边，两点之间带箭头的联线为弧。由点、边构成的图是无向图，记E,VG由点、弧构成的图是有向图，记A,VD1v2v3v4v1e2e3e4e5e6e7e图5-41v2v3v4v5v6v7v1a2a3a4a5a6a7a8a9a10a11a图5-5···········图5-4是一个无向图4321v,v,v,vV，7654321e,e,e,e,e,e,eE其中，112212323434514613744,,,,,,,,,,(,),,evvevvevvevvevvevvevv图5-5是一个有向图7654321v,v,v,v,v,v,vV，11321a,,a,a,aA其中，311221333243452464574685395410561167,,,,,,,,,,,,,,,,,,,,,avvavvavvavvavvavvavvavvavvavvavv给定一个图E,VG，一个点、边的交错序列ikikikiiiiv,e,v,,e,v,e,v112211，如果满足1itititv,ve，1,2,,1tk，则称为一条联结1iv和ikv的链，记为ikiiv,,v,v21。对于有向图A,VD，从D中去掉所有弧上的箭头，应得到一个无向图，称为D的基础图，记为DG。设ikikikiiiiv,a,v,,a,v,a,v112211是D中的一个点弧交错序列，如果这个序列在基础图DG中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。在实际问题中，往往只用图来描述的所研究对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，称为“权”，权可以代表如距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图称为网络（即赋权图）。5.1.3图的矩阵表示用矩阵表示图对研究图的性质及应用常是比较方便的，图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等，这里只介绍其中两种常用矩阵。定义1网络E,VG，其边是jiv,v有权ijw，构造矩阵nnijaA其中，,0ijijijwvvEaor其他称矩阵A为网络G的权矩阵。图5-6表示图的权矩阵为0650760844580320430974290A定义2对于图E,VG，构造一个矩阵nnijaA，其中，其他01Ev,vajiij则称矩阵A为图G的邻接矩阵。247635481v2v3v4v5v9图5-6•••••4图5-7所示图的邻接矩阵A为001101000000000011010101054321vvvvvA当G为无向图时，邻接矩阵为对称矩阵。5.2最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等。问题表述：给定一个赋权有向图A,VD，对每一弧jiijv,va，相应地有权ijijwaw，又有两点Vv,vts，设p是D中sv到tv的一条路，路p的权是p中所有弧的权之和，记为pw。最短路问题就是求从sv到tv的路中一条权最小的路0p，pwpwpmin0。5.2.1Dijkstra算法该算法是由Dijkstra于1959年提出来，用于求解指定两点sv、tv之间的最短路，或从指定点sv到其余各点的最短路，目前被认为是求0ijw情形下最短路问题的最好方法。算法的基本思路基于以下原理：若p是从sv到tv的最短路，iv是p中的一个点，那么从sv沿p到iv的路是从sv到iv的最短路。采用标号法：T标号与P标号。T标号为试探性标号，P为永久性标号。给iv点一个P标号时，表示从sv到iv点的最短路权，iv点的标号不再改变。给iv点一个T标号时，表示从sv到iv点的估计最短路权的上界，是一种临时标号。凡没有得到P标号的点都有T标号。算法每一步都把某一点的T标号改为P标号，当终点tv得到P标号时，全部计算结束。Dijkstra算法基本步骤：1v2v3v4v5v图5-7•••••5⑴给sv以P标号，0svP，其余各点均给T标号，ivT。⑵若iv点为刚得到P标号的点，考虑jv，Av,vji且jv为T标号。对jv的T标号进行如下的更改：ijijjwvP,vTvTmin⑶比较所有具有T标号的点，把最小者iv改为P标号，即iivTvPmin当存在两个以上最小者时，可同时改为P标号。⑷若全部点均为P标号则停止。否则用iv代替iv转回⑵。例5.1用Dijkstra算法求图5-8中从71vv的最短路解：⑴首先给1v以P标号，01vP，给其余所有点T标号ivT，72,,i⑵由于21v,v，31v,v，Av,v41，且432v,v,v是T标号点，所以修改T标号为：330minmin550minmin220minmin141441313312122,wvP,vTvT,wvP,vTvT,wvP,vTvT在所有T标号中，22vT最小，于是令22vP。⑶2v是刚得到P标号的点，故考察2v。因为32v,v，Av,v62，且63v,v是T标号，故63v,v新的T标号为：972minmin422minmin2626623233,wvP,vTvT,wvP,vTvT在所有T标号中，34vT最小，故令34vP。122352523257751v2v3v4v5v6v7v1图5-8••••••6⑷考察4v，因Av,v54，853minmin45455,wvP,vTvT在所有T标号中，43vT最小，令43vP。⑸考察3v，53v,v，Av,v63，9549minmin7348minmin3636635355,wvP,vTvT,wvP,vTvT在所有T标号中，75vT最小，令75vP。⑹考察5v，65v,v，Av,v75，1477minmin8179minmin5757756566,wvP,vTvT,wvP,vTvT在所有T标号中，86vT最小，故令86vP。⑺考察6v，Av,v76135814minmin67677,wvP,vTvT令137vP，所有点都标上P标号，计算结束。从71vv之最短路是：765321vvvvvv，路长13，同时得到1v到其余各点的最短路。5.2.2逐次逼近算法Dijkstra算法只适用于所有0ijw的情形，当赋权有向图中存在负权时，则算法失效。例如在图5-9所示的赋权有向图中，用Dijkstra算法得到1v到3v最短路的权是5，但这里显然不对；因为1v到3v的最短路是321vvv，权为3。在存在负权时，我们采取逐次逼近算法来求解最短路。为方便起见，不妨设从任一点iv到任一点jv都有一条弧，如果在D中，Av,vji，则添加弧jiv,v，令ijw。显75-41v2v3v图5-97然，从sv到jv的最短路总是从sv出发，沿着一条路到某点iv，再沿jiv,v到jv的，所以，从sv到iv的这条路必定是从sv到iv的最短路。故有sv，jv的距离jsv,vd必满足如下方程：ijisijswv,vdv,vdmin为了求解这个方程的解1v,vds，pssv,vd,,v,vd2，p为D的点数，令sjjswv,vd1p,,,j21ijistijstwv,vdminv,vd1，t为迭代步数。若第k步，对所有p,,,j21，有jskjskv,vdv,vd1则jskv,vd为sv到任一点jv的最短路权。例5-2求图5-10所示赋权有向图中从1v到各点的最短路。解：迭代初始条件为：sjjswv,vd1有0111v,vd，1211v,vd，2311v,vd，3411v,vd，511v,vd，611v,vd，711v,vd，811v,vd。用表5-1表示全部计算过程。11-1-1-1-2-3-3-56318-52721v4v2v5v8v7v图5-10•••••••8表5-1（表中空格为）jiwijD(t)(v1,vj)V1V2V3V4V5V6V7V81t2t3t4tV10-1-230000V2602-1-5-5-5V3-30-51-2-2-2-2V48023-7-7-7V5-101-3-3V61017-1-1-1V7-105-5-5V8-3-5066当4t时，发现8211314,,,jv,vdv,vdjj，表明已得到1v到各点jv的最短路的权，即表中最后一列数。如果需要知道1v点到各点的最短路径，可以采用“反向追踪”的办法。如已知，681v,vd，因81686171v,vdwv,vd故记下86v,v。因613631v,vdwv,vd，记下63v,v，从而从1v到8v的最短路径是8631vvvv。递推公式中jtv,vd1实际意义为从1v到jv点，至多含有1t个中间点的最短路权。所以在含有n个点的图中，如果不含有总权小于零的回路，求从1v到任一点的最短路权