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

1第11章图与网络基础1736年欧拉用图论方法解决了哥尼斯堡七桥问题，成为图论的创始人之一.后来的一系列优化问题如邮路问题、迷宫问题、扫街问题、一笔画问题等都可以用欧拉的方法来解决.随着科技的发展，图与网络的理论与方法也在不断扩展.在现实生活中，很多优化和决策问题都可以归结为一个网络图，如交通网络、通讯网络、计算机网络、基因网络等，图论方法成为解决网络优化问题的有力工具.§11.1最短路与中国邮路问题11.1.1图的基本概念1．七桥问题18世纪，有一条河从哥尼斯堡这座城市中间流过，将整座城市分割成四部分.当时一共有七座桥连通河两岸（41,vv）及河中的两座岛屿（32,vv），如图11-1-1所示.有人提出了这样的问题：能否从城市的某处出发，恰好一次地走过所有的桥，最后回到出发地.没有人成功办到，但人们又无法说明这样的走法一定不存在，这就是著名的“七桥问题”.1736年欧拉发表论文证明了“七桥问题”无解，由此开创了一2个新的数学分支：图论.欧拉发现，四块区域的大小形状、七座桥的长短曲直都不影响“七桥问题”的解，于是他将每块区域简化为一个点、连接两地的桥表示成连接两点的线，将问题归结为如图11-1-2所示的问题：从4321,,,vvvv中任一点出发，能否恰好一次地通过每条边，再回到出发点?在11.1.3节中将详细讨论该问题.2．图的基本概念很多事物及其之间的关系都可以像这样抽象成点与点之间的连线，将这样的图形称为图，用G表示；这些点称为图G的顶点，用V表示；这些点间连线称为图G的边，用E表示,一个图是由点集V和边集E所构成的二元组，记为G=(V，E).例如，任务分配问题，可以用点表示工人与待分配的任务，用边表示该工人可以胜任哪些任务，如图11-1-3所示.又比如用点表示我国十个城市，用边表示连接这十个城市的铁路线，得到一个铁路连线图11-1-4(a).值得注意的是，图论中所讨论的图与我们熟悉的几何图形是不同的，在保持图的顶点和边的关系不变的情况下，边的长度、形状，点的位置的安排是无关紧要的.图11-1-4(a)也可画作11-1-4(b).3(a)(b)图11-1-3图11-1-4如果图G的任意两个顶点之间至少有一条路，则称图G是连通图.如图11-1-5所示，点5v是孤立点，与别的顶点之间没有连通的路.它不是连通图.今后，我们主要讨论连通图.图11-1-5图11-1-6上面讨论的图有一个共同点，即任意一条边都没有方向性，称这样的图为无向图.但是，在实际问题中，有时只用无向图还不能把问题描述清楚.比如图11-1-6中，为了表示把货物从点iv运到点jv，就必须在iv与jv的连线上加上箭头指明iv是发货点，jv是收货点.像这种边具有方向性的图称为有向图.在图中，还可以在每条边旁标注与各边有关的数量指标，称之为权。权可以代表距离、费用、通过能力（容量）等等.各边带有一个4非负实数权的图称为网络，或者称为赋权图。边e旁的非负实数称为边e的权，一般记为W（e）。在赋权图中，一条路的权或者说路长就是这条路上的边权之和.11.1.2最短路问题给出一个运输网络：每个顶点表示一个城市，顶点之间赋权的边表示对应的两个城市间的运输距离.求一个城市到另一个城市的最短路线,就可以归结为在一个赋权图中求指定两点间权最小的路，这就是本节要讨论的最短路问题，最短路的权就称为最短路长.求指定两点间最短路的一个较好的算法是Dijkstra标号算法.它的基本思路是：假如路（vsv1v2,…,vn-1vn）是从vs到vn的最短路，则其子路（vsv1v2,…,vn-1）必是从vs到vn-1的最短路.但该法只适用于非负权网络.下面仅介绍可适用于带有负权边网络的逐次逼近法，它可以找到从指定起点vs到网络中其余各点的最短路，具体算法如下：步骤一、列出网络D的邻接权矩阵nnij)w(，其中，ijw为有向边),(jivv上的权值；若网络中没有有向边),(jivv，ijw取为∞.步骤二、设sjP表示从sv到jv的最短路长，令初始解sjsjwP)1(；步骤三、使用迭代公式进行第k-1次迭代：ijksiiksjwPP)1()(min，),3,2(k.直到),2,1()1()(njPPksjksj，则停止迭代.步骤四、)(ksjP就是从sv到jv的最短路长，同时用反向追踪法求得相应的最短路径.例1．求图11-1-7所示有向网络从vs到其他各点的最短路.5图11-1-7解：列出网络的邻接权矩阵，见表11-1-1的左半部分，右半部分则按列填写各次迭代的结果.（1）初始解：)1(6)1(5)1(4)1(3)1(2)1(1)1(,7,5,0ssssssssPPPPPPP；（2）第一次迭代：sssssssssssssssssswPwPwPwPwPwPwPP6)1(65)1(54)1(43)1(32)1(21)1(1)1()2(,,,,,,min0,,,,7,5,00min，61)1(651)1(541)1(431)1(321)1(211)1(11)1()2(1,,,,,,minwPwPwPwPwPwPwPPssssssssss5,,,,17,05,50min，62)1(652)1(542)1(432)1(322)1(212)1(12)1()2(2,,,,,,minwPwPwPwPwPwPwPPssssssssss7,,,,07,5,70min，63)1(653)1(543)1(433)1(323)1(213)1(13)1()2(3,,,,,,minwPwPwPwPwPwPwPPssssssssss11,9,4,0,7,65,0min，64)1(654)1(544)1(434)1(324)1(214)1(14)1()2(4,,,,,,minwPwPwPwPwPwPwPPssssssssss94,,,,27,5,0min，65)1(655)1(545)1(435)1(325)1(215)1(15)1()2(5,,,,,,minwPwPwPwPwPwPwPPssssssssss81,,,,17,5,0min，66)1(656)1(546)1(436)1(326)1(26)1(16)1()2(6,,,,,,minwPwPwPwPwPwPwPPsssssssssss60,,,,7,5,0min，继续第二次迭代，得：)3(6)3(5)3(4)3(3)3(2)3(1)3(,8,9,11,7,5,0ssssssssPPPPPPP，由于对)2()3(,sjsjPPj有，故停止迭代，见表11-1-1表11-1-1)(ijwsv1v2v3v4v5v6v)1(sjP)2(sjP)3(sjPsv0570001v065552v10217773v011114v40995v90886v410表中最后一列数字分别表示从vs到其他各点的最短路长.用反向追踪法可得最短路径.比如需要求出sv到5v的最短路径.由最后一列知8)3(5sP，根据公式817min25)2(25)2()3(5wPwPPsisiis，记下点2v.再考察2v：根据7min2)2(2)2()3(2sssisiiswPwPP，记下点sv.所以从sv到5v的最短路为52vvvs.本题结果见表11-1-2：表11-1-2最短路径1vvs2vvs31vvvs42vvvs52vvvs从6vvs到无任何通路最短路长571198无7例2图11-1-8所示的单向运输网络中的8个顶点表示8个运输站点.连线旁的数字代表运费（百元）.特别地，在某些路段，如从v2到v3因故，在免交运费的同时，还可以获得2百元的奖励，即认为运费为-2（百元）.现要求决策从v1运货到其他各点的运输路线，使得运费最省.图11-1-8解：即求从v1到其他各点的最短路.计算过程可用表11-1-3表示.表11-1-3)(ijw1v2v3v4v5v6v7v8v)1(sjP)2(sjP)3(sjP)4(sjP)5(sjP)6(sjP1v025-30000002v0-242222223v065000004v40-3-3-3-3-3-35v0663336v-3041166667v72014998v3-10151010108本题结果见表11-1-3表11-1-3最短路径21vv321vvv41vv56321vvvvv621vvv786321vvvvvv86321vvvvv最短路长20-330910许多优化问题如管道的铺设、线路的安排、运输网的最小费用等都可以归结为最短路问题.需要注意的是，最短路并不仅限于表示距离最短的路线；若网络中“权”表示时间，则最短路就是所费时间最短的路线；若“权”表示费用，则最短路就是所花费用最少的路线.11.1.3欧拉回路与中国邮路问题1欧拉回路在求解“七桥问题”时，欧拉提出了欧拉回路的定义：连通图中，经过每条边恰好一次且起点与终点相同的路称为欧拉回路，并称具有欧拉回路的图为欧拉图.换言之，“七桥问题”就是要在图11-1-2中寻找一条欧拉回路.欧拉分析发现：对起点来说，每次沿一条边离开后，必须能够再回到起点，即跟起点关联的边数应为偶数条；对中间点而言，每次沿一条边到达该边，必须能再沿着另一条边离开该点，才有可能最终回到起点，即跟中间点关联的边数也应为偶数条.我们把与顶点相关联的边的个数称为该点的度，度为奇数的顶点称为奇点；度为偶数的顶点称为偶点.下面给出判定欧拉图的充要条9件.定理1无向连通图是欧拉图当且仅当图中没有奇点.由于图11-1-2的4个顶点都是奇点，根据定理1，该图不是欧拉图，即图不存在欧拉回路，因此“七桥问题”无解.Fleury给出了寻找欧拉回路的一个算法：步骤一、记图G的所有顶点的全体为V，所有边的全体为E，记),(EVG.任取图G中的一顶点0v，记0vW；步骤二、如果通路iivevevW110已选出，则按下述要求继续从ieeeE,,,21中选取边1ie：（1）边1ie与顶点iv相关联；（2）除非没有别的边可供选择，否则1ie不是ieeeG,,,21的割边，即121,,,ieeeG仍应连通；步骤三、记边1ie的另一顶点为1iv，则通路11110iiiivevevevW.步骤四、重复步骤二、三，直到图G的所有的边被选出.例3求图11-1-9所示图的一个欧拉回路.图11-1-9解：不妨取1v为起点，由于边1e与点1v关联且缺少边1e，图仍然连通.故211vevW.(这里也可取721vevW)再考察与点2v关联的边，取边4e……,最终求得欧拉回路1273254678695104734211vevevevevevevevevevevW.10事实上，同一个图的欧拉回路并不唯一，如本题还可以找到：1278695104734234673211vevevevevevevevevevevW；1278695104734234673721vevevevevevevevevevevW等欧拉回路.2中国邮路问题1862年我国的管梅谷先生提出了“中国邮路问题”：一个邮递员，从邮局出发，走遍他所管辖的所有街道，再返回邮局.问应如何安排投递路线，才能使邮递员所走的总路程最短.如果把所经过的街道作为边，投递距离作为