组合图论图论及其算法课件.ppt

图论及其算法,张莉 Tongji University lizhangtongji.edu.cn,§1 最小支撑树问题,1. 树：无回路的无向连通图.,一.基本概念,2. 叶：树中度数为1的顶点.,3. 森林：连通分支大于1，且每个连通分支均为树的非连通图.,1. 例1：在偏远地区，可以通过公路连接分散的村落，但没有任何电话服务。我们希望铺设电话线路，使得每一对村落都可以通过电话线连接(不必是直接的)。沿着现存的公路铺设电话线最便宜，问沿着哪些公路铺设电话线，可以确保每一对村落被连接，且电话线的总长度达到最小(电话线总长度可能与安装总成本成正比)？,二.最小生成树,解：寻找最小生成树.,例2：假设在一个没有良好高速公路的偏远地区涌现了几个城市，理想的是建筑足够多的高速公路，使得城市之间或者直接通过高速公路往来，或者可以通过去其他城市来实现彼此的互相往来. 现在我们希望成本最小化.,注: (1)成本最小化即：可以实现城市间的互通，同时，每条高速路都不浪费(即去掉后就不能互通了).,(2)不允许高速路在所研究的城市以外的某点处连接.,此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和(如ABAC).,最短网络问题:,如何用最短的线路将三部电话连起来？,但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径O要短。 这样得到的网络不仅比原来节省材料，而且稳定性也更好。,斯坦纳（Steiner）最小树是可以在给定的点之外再增加 若干个点(称为斯坦纳点)，然后将所有这些点连起来。,如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树。,在前面的例子中Steiner最小树的长为 .,最小生成树的长为2.,1968年贝尔实验室波雷克(Pollak)和研究员吉尔伯特 (Gilbert)提出如下猜想：平面上任意n点集，斯坦纳最 小树长与最小生成树之长的比值的最小值是 .,1967年前，贝尔公司按照连结各分部的最小生成树的长度来收费。1967年一家航空公司戳了贝尔公司一个大洞。当时这家企业申请要求贝尔公司增加一些服务点，而这些服务点恰恰位于构造该公司各分部的斯坦纳最小树需增加的斯坦纳顶点上。这使得贝尔公司不仅要拉新线，增加服务网点，而且还要减少收费。这一意外事件迫使贝尔公司自此以后便采用了斯坦纳最小树原则 。,Steiner猜想起源于在美国贝尔电话公司发生的一个富有戏剧性的事件。,1. 问题描述：如村落间铺设电话线的问题.,三. Kruskal算法,2. 算法思想(贪婪算法)：总是选择权最小的边.,3. 算法描述：,步骤1：按照权的递增顺序排列图G的边，置集合T为空集.,步骤2：检查排列序表中第一条未检查的边，此边被放入T中当且仅当它不与T中的边形成回路。若这条边被加入T中，进入步骤3，否则重复步骤2.,步骤3：若T有n-1条边，则停止，T即为所找的最小支撑树，否则，进入步骤2.,5. 实例：,解：abcdde-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. 实例：,解：abbddc-de,1). 选点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. 算法思想：,2. 算法描述(从u0到un-1)：,3. 实例：,1) S0=x,其他l(v)=,l(x)=0 2) 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的.,3. 近似算法(最邻近算法),4. 实例：求下列赋权完全图的最优Hamilton回路.,解：ACEBDA: 权和 25 BACEDB: 权和 25 CABEDC： 权和 22 DACEBD： 权和 25 EACDBE: 权和 27,所选初始点不同，得到的近似解也不同.,5. 修改方法：最邻近插入法,思想方法：每次迭代中都让其构成一个闭的旅行路线，它由多个阶段形成，每次都比上一次多一个顶点。求解时，在已建立旅程之外的顶点中，寻找最邻近于旅程中某个顶点的顶点，将其插入该旅程中，并使增加的距离尽可能小，当全部顶点收入这个旅程后，就找到了最短哈密尔顿回路的近似解.,实例：,(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算法,(1) 标号过程,(2) 调整过程,8.算法思想：从任何一个可行流(如零流)出发，寻找增广路，调节修正流量.,缺陷：符号顺序任意，导致增广路任意.,改进：最短增广路算法.,注：算法最终停止时，S为已标号点，T为未标号点，C(S, T)即为最大流.,7. 实例,找到一条x-y增广路P=xv2v5v1v4y,调整P中边的流量:,再重新标号，只能从x标到v3，S=x,v3,T=v1,v2,v4, v5,v6,y,C(S,T)=11=v(f).,