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

第5章 图与网络分析 图论的根本概念 引言 瑞士数学欧拉〔Euler〕在1736年发表了图论方面的第一篇论文，题为“依据几何位置的解题方法〞，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该河上有两个岛，河上有七座桥，如图5-1〔a〕所示。当时那里的居民热衷于这样的问题一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。 欧拉用A、B、C、D四点表示河的两岸和小岛，用两点间的联线表示桥，如图5-1〔b〕，该问题可归结为能否从任一点出发，通过每条边一次且仅一次，再回到该点即一笔画问题。欧拉证明了这是不可能的，因为图中每点都只与奇数条线相连。这是古典图论中的一个著名问题。 运筹学中的“中国邮递员问题〞一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个总是就与欧拉回路有密切的关系。 图论的第一本专著是匈牙利数学家著的“有限图与无限图的理论〞，发表于1936年。随着科学技术的开展及电子计算机的出现和广泛应用，图论得到进一步开展，广泛应用于管理科学、计算机科学、心理学及工程技术管理中，并取得了丰硕的成果。 5 根本概念 自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形来表示。如为了反映城市之间有没有航班，我们可用图5-2来示意。甲城与乙城，乙城与丙城有飞机到达，而甲、丙两城没有直飞航班。再如工作分配问题，我们可以用点表示每人与需要完成的工作，点间连线表示每个人可以胜任哪些工作如图5-3所示。 在上面的例子中，我们关心图中有多少个点，点与点之间有无连线。这种图是反映对象之间关系的一种工具。 图可分为无向图和有向图。两点之间不带箭头的联线为边，两点之间带箭头的联线为弧。 由点、边构成的图是无向图，记 由点、弧构成的图是有向图，记 图5-4是一个无向图 ， 其中， 图5-5是一个有向图 ， 其中， 给定一个图，一个点、边的交错序列，如果满足，，那么称为一条联结和的链，记为。 对于有向图，从中去掉所有弧上的箭头，应得到一个无向图，称为的根底图，记为。 设是中的一个点弧交错序列，如果这个序列在根底图中所对应的点边序列是一条链，那么称这个点弧交错序列是的一条链。 在实际问题中，往往只用图来描述的所研究对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，称为“权〞，权可以代表如距离、费用、通过能力〔容量〕等等。这种点或边带有某种数量指标的图称为网络〔即赋权图〕。 图的矩阵表示 用矩阵表示图对研究图的性质及应用常是比拟方便的，图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等，这里只介绍其中两种常用矩阵。 定义1网络，其边是有权，构造矩阵 其中， 称矩阵为网络的权矩阵。 图5-6表示图的权矩阵为 定义2对于图，构造一个矩阵，其中， 那么称矩阵为图的邻接矩阵。 图5-7所示图的邻接矩阵为 当为无向图时，邻接矩阵为对称矩阵。 最短路问题 最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等。 问题表述给定一个赋权有向图，对每一弧，相应地有权，又有两点，设是中到的一条路，路的权是中所有弧的权之和，记为。最短路问题就是求从到的路中一条权最小的路， 。 Dijkstra算法 该算法是由Dijkstra于1959年提出来，用于求解指定两点、之间的最短路，或从指定点到其余各点的最短路，目前被认为是求情形下最短路问题的最好方法。算法的根本思路基于以下原理假设是从到的最短路，是中的一个点，那么从沿到的路是从到的最短路。 采用标号法标号与标号。标号为试探性标号，为永久性标号。给点一个标号时，表示从到点的最短路权，点的标号不再改变。给点一个标号时，表示从到点的估计最短路权的上界，是一种临时标号。凡没有得到标号的点都有标号。算法每一步都把某一点的标号改为标号，当终点得到标号时，全部计算结束。 Dijkstra算法根本步骤 ⑴给以标号，，其余各点均给标号，。 ⑵假设点为刚得到标号的点，考虑，且为标号。对的标号进行如下的更改 ⑶比拟所有具有标号的点，把最小者改为标号，即 当存在两个以上最小者时，可同时改为标号。 ⑷假设全部点均为标号那么停止。否那么用代替转回⑵。 例5.1 用Dijkstra算法求图5-8中从的最短路 解⑴首先给以标号，，给其余所有点标号 ， ⑵由于，，，且是标号点，所以修改标号为 在所有标号中，最小，于是令。 ⑶是刚得到标号的点，故考察。因为，，且是标号，故新的标号为 在所有标号中，最小，故令。 ⑷考察，因， 在所有标号中，最小，令。 ⑸考察，，， 在所有标号中，最小，令。 ⑹考察，，， 在所有标号中，最小，故令。 ⑺考察， 令，所有点都标上标号，计算结束。 从之最短路是，路长13，同时得到到其余各点的最短路。 逐次逼近算法 Dijkstra算法只适用于所有的情形，当赋权有向图中存在负权时，那么算法失效。例如在图5-9所示的赋权有向图中，用Dijkstra算法得到到最短路的权是5，但这里显然不对；因为到的最短路是，权为3。 在存在负权时，我们采取逐次逼近算法来求解最短路。为方便起见，不妨设从任一点到任一点都有一条弧，如果在中，，那么添加弧，令。显然，从到的最短路总是从出发，沿着一条路到某点，再沿到的，所以，从到的这条路必定是从到的最短路。故有，的距离必满足如下方程 为了求解这个方程的解，，为的点数，令 ，为迭代步数。 假设第步，对所有，有 那么为到任一点的最短路权。 例5-2 求图5-10所示赋权有向图中从到各点的最短路。 解迭代初始条件为 有，，，，，，，。用表5-1表示全部计算过程。 表5-1 〔表中空格为〕 j i wij Dtv1,vj V1 V2 V3 V4 V5 V6 V7 V8 V1 0 -1 -2 3 0 0 0 0 V2 6 0 2 -1 -5 -5 -5 V3 -3 0 -5 1 -2 -2 -2 -2 V4 8 0 2 3 -7 -7 -7 V5 -1 0 1 -3 -3 V6 1 0 1 7 -1 -1 -1 V7 -1 0 5 -5 -5 V8 -3 -5 0 6 6 当时，发现，说明已得到到各点的最短路的权，即表中最后一列数。 如果需要知道点到各点的最短路径，可以采用“反向追踪〞的方法。如，，因故记下。因，记下，从而从到的最短路径是。 递推公式中实际意义为从到点，至