运筹学教学课件第十章图与网络分析.ppt

六、图与网络分析 第十章 图与网络分析 第十一章 网络计划与图解评审法 第十章 图与网络分析 §1 图的基本概念 §2 树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题 §6 中国邮递员问题 重点和难点 一、重点(二、难点) 1、图的基本概念 2、图的基本性质 3、树的概念和性质 4、连通图的支撑树和最小支撑树的破圈法和避圈法。 5、赋权有向图的最短路问题及其Dijkstra算法与应用。 6、网络最大流的概念、性质和Ford-Fulkson标号法 图论的起源 　　欧拉 (Euler) 在1736 年发表图论方面的第一篇论文，解决了著名的哥尼斯堡七孔桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个小岛，河上有七座桥，参见图 5.1(a) 。 　　当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。 　　 §1 图的基本概念 现实世界中的图 在实际生活中，人们为了反映一些对象之间的关系，常常在纸上用点和线画出各种各样的示意图。 例1 图10－2是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，用点和点之间的联线代表这两个城市之间的铁路线。诸如此类的还有电话线分布图、煤气管道图、航空线图等等。 图10-2 例2 有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况，也可以用图表示出来。已知甲队和其它各队都比赛过一次，乙队和甲丙队比赛过，丙队和乙、丁队比赛过，丁队和丙、戊队比赛过，戊队和甲、丁队比赛过。为了反映这个情况，可以用点v1,v2,v3,v4,v5分别代表这五个队，某两个队之间比赛过，就在这两个队所相应的点之间联一条线，这条线不过其它的点，如图10-3所示。 图10-3 例3 某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的，为了反映这个情况可以用v1,v2,…,v8点分别代表这八种药品，若药品vi和药品vj是不能存放在同一个库房的，则在vi和vj之间联一条线，如图10-4所示。 图10-4 从这个图中可以看到 至少要有四个库房，因为v1,v2,v5,v8必须存放在不同的库房里，事实上，四个库房就足够了。 例如：{v1},{v2,v4,v7},{v3,v5},{v6,v8}各存放在一个库房里，（这一类寻求库房的最少个数问题，属于图论中的所谓染色问题，一般情况下是尚未解决的）。 从以上几个例子可见 可以用由点及点与点的联线所构成的图，去反映实际生活中，某些对象之间的某个特定的关系，通常用点代表研究的对象（如城市、球队、药品等等），用点与点的联线表示这两个对象之间有特定的关系（如两个城市间有铁路线、两个球队比赛过、两种药品不能存放在同一个库房里等）。 图是反映对象之间关系的一种工具 因此，可以说，在一般情况下，图中点的相对位置如何，点与点之间联线的长短曲直，对于反映对象之间的关系，并不是重要的。 如例2，也可以用如图10－5所示的图去反映五个球队的比赛情况，这与图10－3没有本质的区别。所以，图论中的图与几何图、工程图等是不同的。 图10－5 对称关系与非对称关系 v1 对称关系与非对称关系 前面几个例子中涉及到的对象之间的“关系”具有“对称性”，就是说，如果甲与乙有这种关系，那么同时乙也与甲有这种关系。例如甲药品不能和乙药品放在一起，那么，乙药品当然也不能和甲药品放在一起。在实际生活中，有许多关系不具有这种对称性。比如人们之间的认识关系，甲认识乙并不意味着乙也认识甲，比赛中的胜负关系也是这样，甲胜乙和乙胜甲是不同的。反映这种非对称的关系，只用一条联线就不行了，如例2. 对称关系与非对称关系 如果人们关心的是五个球队比赛的胜负情况，那么从图10－3中就看不出来了，为了反映这一类关系，可以用一条带箭头的联线表示，例如球队v1胜了球队v2，可以从v1引一条带箭头的联线到v2.图10－6反映了五个球队比赛的胜负情况，可见v1三胜一负，v4打了三场球，全负等等 . 对称关系与非对称关系 类似胜负这种非对称性的关系，在生产和生活中是常见的，如交通运输中的“单行线”，部门之间的领导与被领导的关系、一项工程中各工序之间的先后关系等等。 综上所述，一个图是由一些点及一些点之间的联线（不带箭头或带箭头）所组成的。 无向图 为了区别起见，把两点之间的不带箭头的联线称为边，带箭头的联线称为弧。 如果一个图G是由点及边所构成的，则称之为无向图（也简称为图），记为G=(V,E),式中V，E分别是G的点集合和边集合。一条联结点的边记为[vi,vj](或[vj,vi])。 有向图 如果一个图D是由点及弧所构成的，则称为有向图，记为D=(V,A)式中，V，A分别表示D的点集合和弧集合，一条方向是从vi指向vj