图论及其算法

图论及其算法张莉[e-mail]§1最小支撑树问题1.树：无回路的无向连通图.一.基本概念2.叶：树中度数为1的顶点.3.森林：连通分支大于1，且每个连通分支均为树的非连通图.1.例1：在偏远地区，可以通过公路连接分散的村落，但没有任何电话服务。我们希望铺设电话线路，使得每一对村落都可以通过电话线连接(不必是直接的)。沿着现存的公路铺设电话线最便宜，问沿着哪些公路铺设电话线，可以确保每一对村落被连接，且电话线的总长度达到最小(电话线总长度可能与安装总成本成正比)？二.最小生成树解：寻找最小生成树.例2：假设在一个没有良好高速公路的偏远地区涌现了几个城市，理想的是建筑足够多的高速公路，使得城市之间或者直接通过高速公路往来，或者可以通过去其他城市来实现彼此的互相往来.现在我们希望成本最小化.注:(1)成本最小化即：可以实现城市间的互通，同时，每条高速路都不浪费(即去掉后就不能互通了).(2)不允许高速路在所研究的城市以外的某点处连接.此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和(如AB∪AC).ABC最短网络问题:如何用最短的线路将三部电话连起来？但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。ABCP斯坦纳（Steiner）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳点)，然后将所有这些点连起来。如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。3在前面的例子中Steiner最小树的长为.最小生成树的长为2.1968年贝尔实验室波雷克(Pollak)和研究员吉尔伯特(Gilbert)提出如下猜想：平面上任意n点集，斯坦纳最小树长与最小生成树之长的比值的最小值是.321967年前，贝尔公司按照连结各分部的最小生成树的长度来收费。1967年一家航空公司戳了贝尔公司一个大洞。当时这家企业申请要求贝尔公司增加一些服务点，而这些服务点恰恰位于构造该公司各分部的斯坦纳最小树需增加的斯坦纳顶点上。这使得贝尔公司不仅要拉新线，增加服务网点，而且还要减少收费。这一意外事件迫使贝尔公司自此以后便采用了斯坦纳最小树原则。Steiner猜想起源于在美国贝尔电话公司发生的一个富有戏剧性的事件。1.问题描述：如村落间铺设电话线的问题.三.Kruskal算法2.算法思想(贪婪算法)：总是选择权最小的边.3.算法描述：步骤1：按照权的递增顺序排列图G的边，置集合T为空集.步骤2：检查排列序表中第一条未检查的边，此边被放入T中当且仅当它不与T中的边形成回路。若这条边被加入T中，进入步骤3，否则重复步骤2.步骤3：若T有n-1条边，则停止，T即为所找的最小支撑树，否则，进入步骤2.5.实例：b53d854e12107022a63c解：ab—cd—de--bd排序：ab,cd,de,ec,bd,be,ac,ae四.Prim算法1.算法思想(贪婪算法)：从顶点出发，对任意点，总是选择与其关联的权最小的边放入T中.2.算法描述：步骤1：置集合T为空集,任选一点v放入树T中.步骤2：将连接T中的点与V-V(T)中的点的所有边中权最小的边加入到T中，若权最小的边有多条，任选其一，若不可能把任一条边加入到T中，则停止，输出G非连通.步骤3：若T有n-1条边，则停止，T即为所找的最小支撑树，否则，重复步骤2.5.实例：b53d854e12107022a63c解：ab—bd—dc--de1).选点a,T={a},选出ab,2).T={ab},选出bd,3).T={ab,bd},选出dc,4).T={ab,bd,dc},选出de§2最短路径问题一.简介1.问题：寻找网络中两个顶点之间的最短路径问题.2.实例：希望利用公路开车从上海到北京，希望路程最短.注：(1)点—城市，边—公路，权—距离，连通赋权图.(2)所有权均非负.二.Dijkstra算法(1959)1.算法思想：00()0,,(),luvlvu对其他点则标号为在算法进行过程中，不断修改这些标号，使得每个点都最终可以得到一个标号，这个标号首先给始点一个标号到该点的最就是始点短路长.SSS直观思路即：从始点开始，每次找到始点最近的边，将其顶点设为，不断地将始点与之间的最短路所涉及的边之端点加入到，直至到达终点.0001111(,0.)0,,(),)()};min{()2,()min{(),(.{}.3-1,-1,:12,.}iiiiiviiiSvlvSuwuvlvluivSlvluSvluSininiui步骤：置且步骤：对每个置对其他点计算并把达到这个最小值的一个顶点步骤：记若则停止，若则，转步骤为2.算法描述(从u0到un-1)：3.实例：a3d35x8b21y4e8c11)S0={x},其他l(v)=∞,l(x)=02)l(a)=3,l(b)=8,l(c)=4,S1={x,a}3)l(b)=8,l(c)=4,l(d)=6,S2={x,a,c}4)l(b)=8,l(e)=5,l(d)=6,S3={x,a,c,e}5)l(d)=6,l(b)=7,l(y)=13,S4={a,c,e,d}6)l(b)=7,l(y)=11,S5={a,c,e,d,b}7)l(y)=11,S6={a,c,e,d,b,y}一笔画问题)在哥尼斯堡有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。Euler在1736年访问Konigsberg时，他发现当地的市民正从事一项非常有趣的消遣活动。这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。Euler证明了不可能存在这样的路线。三.中国邮递员问题(1962，管梅谷)1.问题：邮递员每天从邮局选好邮件，送到他所管辖的邮区的客户手中，再返回邮局，他每天必须走过每条街道至少一次，问如何选择邮递路线，使得他走过的投递总行程最短？2.模型：非负赋权图G：顶点----交叉口或终端，边----街道，权-----街道长度，此即求图的通过每条边至少一次的闭途径,称为G的环游.3.最优环游：即具有最小权的环游.注：(1)若G是欧拉图，则欧拉环游即最优.(2)若G不是欧拉图，则重复边权和最小的即最优.4.定理：设P是赋权连通图G中一条包含G的所有边至少一次的闭途径，则P最优当且仅当它满足以下两个条件：(1)P中没有二重以上的边.(2)对G中的任意圈C，其重复边集E的长度之和不超过圈长的一半，即w(E)≤1/2w(C).步骤1：取V0={v|d(v)为奇数}，(G中一定有偶数个奇点).步骤2：对V0中任意u,v，求d(u,v),(用Dijkstra算法).步骤3：构造完全图K|v0|,其中边{u,v}的权为d(u,v).步骤4：求K|v0|中的权最小的完美匹配M.步骤5：在G中求以M中每条边的两端点为端点的最短路.步骤6：将步骤5中所求的每条最短路上的每条边都添上一条等权的“倍边”，得到新图G‘.步骤7：在新图G’中用Fleury算法求欧拉环游，则即为G的最优环游.5.Edmonds-Johnson算法三.旅行商问题1.问题：设有n个城镇，已知每两个城镇之间的距离，一个售货员自一个城镇出发巡回售货，问他该如何选择路线，能使每个城镇经过一次且仅一次，最后再回到出发地而且行程最短。2.模型：此即在赋权完全图中，寻找最小权的哈密尔顿圈.注：这个问题是NPC的.100011101011011011,2(){,,},311,:12,,,.niiiiiivevVvevvvvvGvvviniivvvvvCvvv步骤：任选一点作为起点，找一条与关联的权最小的边的另一端点记为即得初始路.步骤：若已选定路，在中取一个与最近(即权最小)的顶点，设为得到已选出.步骤：若＜则令，转步骤，否则，记结束3.近似算法(最邻近算法)4.实例：求下列赋权完全图的最优Hamilton回路.A2134B5E97106C8D解：ACEBDA:权和25BACEDB:权和25CABEDC：权和22DACEBD：权和25EACDBE:权和27所选初始点不同，得到的近似解也不同.5.修改方法：最邻近插入法思想方法：每次迭代中都让其构成一个闭的旅行路线，它由多个阶段形成，每次都比上一次多一个顶点。求解时，在已建立旅程之外的顶点中，寻找最邻近于旅程中某个顶点的顶点，将其插入该旅程中，并使增加的距离尽可能小，当全部顶点收入这个旅程后，就找到了最短哈密尔顿回路的近似解.实例：A2134B5E97106C8D(1)初始点为A，组成闭旅程AA，下一阶段，最邻近A的顶点为C，建立闭旅程ACA,再寻找最邻近A与C的顶点B，组成闭旅程ACBA.(2)从D,E中找一个最邻近ACBA的顶点D，将其插入，分别得到ACDBA(权和20)，ACBDA(23),ADCBA(23),选择ACDBA.(3)最后将E插入ACDBA,有4个位置AECDBA(30),ACEDBA(25),ACDEBA(22),ACDBEA(27)，选择最小的ACDEBA(22)即为所求.网络流问题随着中国经济快速的增长，城市化是未来中国的发展方向。我们要把物流业作为战略重点列入要大力发展的新兴服务产业。如何制定一个运输计划使得生产地到销售地的产品输送量最大？这就是一个网络最大流问题。6.Ford-Fulkerson算法,,),min{,},,),)1).()2).,(,(+(0,(3,min{,},,),).2).iijijijjiijijjijjijijijijjixvvCvAffvvCvvvyyxfyAfv源标号选择一个已标号的顶点对其所有未标号的邻点作如下处理：若弧令标号弧令标号重复过程直到且并给若且并给汇被标号，或不再有顶点可以标号为止若得到标号，说明存在一条增广2.Pyf路，进入步骤调整过程；若未得到标号，标号过程无法进行，说明即为最大流(1)标号过程(,),)({min(),min}(,)(,)(,),1).''()2).1ijijijijjivPvPijijijijijvjvijiminffPfvvPfCfvvPvvPffvf，调令得到新的可行流，其总流量为去掉所整增广路中的流量有标号，回到步骤，重复以上过程，直到无法如下：进行为止.(2)调整过程8.算法思想：从任何一个可行流(如零流)出发，寻找增广路，调节修正流量.缺陷：符号顺序任意，导致增广路任意.改进：最短增广路算法.注：算法最终停止时，S为已标号点，T为未标号点，C(S,T)即为最大流.7.实例v1(5,2)v4(5,5)(3,3)(4,2)x(4,2)v2(3,0)v5(3,3)y(3,2)(2,2)(5,4)v3(2,2)v6(-v5,2)(+v1,2)v1(5,2)v4(5,5)(3,3)(4,2)x(4,2)v2(3,0)v5(3,3)y(△,∞)(+x,2)(+v2,2)(+v4,2)(3,2)(2,2)(5,4)v3(2,2)v6(+x,1)找到一条x-y增广路P=xv2v5v1v4y,调整P中边的流量:v1(5,4)v4(5,5)(3,1)(4,4)x(4,4)v2(3,2)v5(3,3)y(3,2)(2,2)(5,4)v3(2,2)v6再重新标号，只能从x标到v3，S={x,v3},T={v1,v2,v4,v5,v6,y},C(S,T)=11=v(f).