第十一章+工程图与网络基础

《第十一章+工程图与网络基础》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第11章图与网络基础1736年欧拉用图论方法解决了哥尼斯堡七桥问题，成为图论的创始人之一.后来的一系列优化问题如邮路问题、迷宫问题、扫街问题、一笔画问题等都可以用欧拉的方法来解决.随着科技的发展，图与网络的理论与方法也在不断扩展.在现实生活中，很多优化和决策问题都可以归结为一个网络图，如交通网络、通讯网络、计算机网络、基因网络等，图论方法成为解决网络优化问题的有力工具.§11.1最短路与中国邮路问题11.1.1图的基本概念1．七桥问题18世纪，有一条河从哥尼斯堡这座城市中间流过，将整座城市分割成四部分.当时一共有七座

2、桥连通河两岸（）及河中的两座岛屿（），如图11-1-1所示.有人提出了这样的问题：能否从城市的某处出发，恰好一次地走过所有的桥，最后回到出发地.没有人成功办到，但人们又无法说明这样的走法一定不存在，这就是著名的“七桥问题”.1736年欧拉发表论文证明了“七桥问题”39无解，由此开创了一个新的数学分支：图论.欧拉发现，四块区域的大小形状、七座桥的长短曲直都不影响“七桥问题”的解，于是他将每块区域简化为一个点、连接两地的桥表示成连接两点的线，将问题归结为如图11-1-2所示的问题：从中任一点出发，能否恰好一次地通过每条边

3、，再回到出发点?在11.1.3节中将详细讨论该问题.2．图的基本概念很多事物及其之间的关系都可以像这样抽象成点与点之间的连线，将这样的图形称为图，用G表示；这些点称为图G的顶点，用V表示；这些点间连线称为图G的边，用E表示,一个图是由点集V和边集E所构成的二元组，记为G=(V，E).例如，任务分配问题，可以用点表示工人与待分配的任务，用边表示该工人可以胜任哪些任务，如图11-1-3所示.又比如用点表示我国十个城市，用边表示连接这十个城市的铁路线，得到一个铁路连线图11-1-4(a).值得注意的是，图论中所讨论的图与我

4、们熟悉的几何图形是不同的，在保持图的顶点和边的关系不变的情况下，边的长度、形状，点的位置的安排是无关紧要的.图11-1-4(a)也可画作11-1-4(b).39(a)(b)图11-1-3图11-1-4如果图G的任意两个顶点之间至少有一条路，则称图G是连通图.如图11-1-5所示，点是孤立点，与别的顶点之间没有连通的路.它不是连通图.今后，我们主要讨论连通图.图11-1-5图11-1-6上面讨论的图有一个共同点，即任意一条边都没有方向性，称这样的图为无向图.但是，在实际问题中，有时只用无向图还不能把问题描述清楚.比如图

5、11-1-6中，为了表示把货物从点运到点，就必须在与的连线上加上箭头指明是发货点，是收货点.像这种边具有方向性的图称为有向图.在图中，还可以在每条边旁标注与各边有关的数量指标，称之为权。权可以代表距离、费用、通过能力（容量）等等.各边39带有一个非负实数权的图称为网络，或者称为赋权图。边e旁的非负实数称为边e的权，一般记为W（e）。在赋权图中，一条路的权或者说路长就是这条路上的边权之和.11.1.2最短路问题给出一个运输网络：每个顶点表示一个城市，顶点之间赋权的边表示对应的两个城市间的运输距离.求一个城市到另一个城市

6、的最短路线,就可以归结为在一个赋权图中求指定两点间权最小的路，这就是本节要讨论的最短路问题，最短路的权就称为最短路长.求指定两点间最短路的一个较好的算法是Dijkstra标号算法.它的基本思路是：假如路（vsv1v2,…,vn-1vn）是从vs到vn的最短路，则其子路（vsv1v2,…,vn-1）必是从vs到vn-1的最短路.但该法只适用于非负权网络.下面仅介绍可适用于带有负权边网络的逐次逼近法，它可以找到从指定起点vs到网络中其余各点的最短路，具体算法如下：步骤一、列出网络D的邻接权矩阵，其中，为有向边上的权值；若

7、网络中没有有向边，取为∞.步骤二、设表示从到的最短路长，令初始解；步骤三、使用迭代公式进行第k-1次迭代：，.直到，则停止迭代.步骤四、就是从到的最短路长，同时用反向追踪法求得相应的最短路径.例1．求图11-1-7所示有向网络从vs到其他各点的最短路.39图11-1-7解：列出网络的邻接权矩阵，见表11-1-1的左半部分，右半部分则按列填写各次迭代的结果.（1）初始解：；（2）第一次迭代：，，，，，，39，继续第二次迭代，得：，由于对，故停止迭代，见表11-1-1表11-1-105700006555102177701

8、11140999088410表中最后一列数字分别表示从vs到其他各点的最短路长.用反向追踪法可得最短路径.比如需要求出到的最短路径.由最后一列知，根据公式，记下点.再考察：根据，记下点.所以从到的最短路为.本题结果见表11-1-2：表11-1-2最短路径从无任何通路最短路长571198无39例2图11-1-8所示的单向运输网络中的8个顶点表示8