第５章 图与网络分析
5．1 图论的基本概念
5．１．1 引言
瑞士数学欧拉(Euler)在1736年发表了图论方面的第一篇论文,题为“依据几何位置的解题方法”，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河,该河上有两个岛,河上有七座桥,如图５-1(a)所示。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥,且每座桥只走过一次，最后回到出发点。
A A · C D C · · B B （a） 图5-1 （b）
D · 欧拉用Ａ、B、Ｃ、Ｄ四点表示河的两岸和小岛，用两点间的联线表示桥,如图5-１（b），该问题可归结为：能否从任一点出发,通过每条边一次且仅一次,再回到该点?即一笔画问题。欧拉证明了这是不可能的,因为图中每点都只与奇数条线相连。这是古典图论中的一个著名问题。
运筹学中的“中国邮递员问题”:一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个总是就与欧拉回路有密切的关系。
图论的第一本专著是匈牙利数学家Ｏ．Konig著的“有限图与无限图的理论”,发表于１９36年。随着科学技术的发展及电子计算机的出现和广泛应用,图论得到进一步发展，广泛应用于管理科学、计算机科学、心理学及工程技术管理中，并取得了丰硕的成果。 5.1.2 基本概念
自然界和人类社会中,大量的事物以及事物之间的关系，常可以用图形来表示。如为了反映城市之间有没有航班，我们可用图５-2来示意。甲城与乙城，乙城与丙城有飞机到达，
而甲、丙两城没有直飞航班。再如工作分配问题,我们可以用点表示每人与需要完成的工作,点间连线表示每个人可以胜任哪些工作如图5-3所示。
乙 · ·甲 · 丙 图5-2 工人 ·甲 ·乙 丙 ·工作 · A · B C · D · 图5-3
在上面的例子中，我们关心图中有多少个点,点与点之间有无连线。这种图是反映对象之间关系的一种工具。
图可分为无向图和有向图。两点之间不带箭头的联线为边,两点之间带箭头的联线为弧。 由点、边构成的图是无向图,记G??V,E? 由点、弧构成的图是有向图，记D??V,A?
e1 v2 · a2 e2v1·e5v3 a3· · a5a8 a6v5· a10 va11 v· e6 e3 v1 ·a1a4 a9 a7· v2v4· e e4 · 7v3 v4· 图5-4 图５－４是一个无向图
图5-5 V??v1,v2,v3,v4?,E??e1,e2,e3,e4,e5,e6,e7?
其中,
e1??v1,v2?,e2??v1,v2?,e3??v2,v3?,e4??v3,v4?,e5??v1,v4?,e6?(v1,v3),e7??v4,v4?图5－5是一个有向图
V??v1,v2,v3,v4,v5,v6,v7?，A??a1,a2,a3,?,a11?
其中,
a1??v1,v2?,a2??v1,v3?,a3??v3,v2?,a4??v3,v4?,a5??v2,v4?,a6??v4,v5?,a7??v4,v6?,a8??v5,v3?,a9??v5,v4?,a10??v5,v6?,a11??v6,v7?
给定一个图G??V,E?，一个点、边的交错序列?vi1,ei1,vi2,ei2,?,vik?1,eik?1,vik?,如果满足
eit??vit,vit?1?,?t?1,2,,k?1?，则称为一条联结vi1和vik的链,记为?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 图的矩阵表示
用矩阵表示图对研究图的性质及应用常是比较方便的,图的矩阵表示方法有权矩阵、邻接矩阵、关联矩阵、回路矩阵等,这里只介绍其中两种常用矩阵。
定义１?网络G??V,E?，其边是vi,vj有权wij,构造矩阵A?aij????n?n
??wij其中，aij????0or??v,v??E??
ij其他??? 7 v1? v5 ? 称矩阵A为网络G的权矩阵。 图５-6表示图的权矩阵为
4 2 9 v2? 6 v?4 ?0?9?A??2??4??79247?0340??3085?
?4806?0560??4 5 3 图5-6 v?3 8
定义2?对于图G??V,E?,构造一个矩阵A?aij??jn?n，其中,
?1aij???0则称矩阵A为图G的邻接矩阵。
?v,v??E?
i其他??
上海交通大学管理科学-运筹学课件
