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

第 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 的基础图...