第 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 来示意。甲城与乙城,乙城与丙城有飞机到达,而甲、丙两城没有直飞航班。再如工作分配问题,我们可以用点表示每人与需要完成的工作,点间连线表示每个人可以胜任哪些工作如图 5-3 所示。在上面的例子中,我们关心图中有多少个点,点与点之间有无连线。这种图是反映对象之间关系的一种工具。图可分为无向图和有向图。两点之间不带箭头的联线为边,两点之间带箭头的联线为弧。由点、边构成的图是无向图,记G=(V , E)由点、弧构成的图是有向图,记D=(V , A)图 5-4 是一个无向图V=(v1, v2,v3,v 4) ,E={e1,e2,e3 ,e4 ,e5 ,e6 ,e7}其中,图 5-5 是一个有向图V={v1, v2,v3,v 4,v5 ,v6, v7},A={a1,a2,a3 ,⋯,a11}其中,给定一个图G=(V , E) ,一个点、边的交错序列(vi1,ei1,vi 2,ei 2,⋯,vik−1,eik−1,vik),如果满足 eit=[vit ,vit+1],, 则 称 为 一 条 联 结 vi1和的 链 , 记 为(vi1, vi2,⋯,vik)。对于有向图D=(V , A) ,从D 中去掉所有弧上的箭头,应得到一个无向图,称为D 的基础图...