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

《组合图论图论及其算法课件.ppt》由会员分享，可在线阅读，更多相关《组合图论图论及其算法课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合图论图论及其算法课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望1 最小支撑树问题1. 树：无回路的无向连通图.一.基本概念2. 叶：树中度数为1的顶点.3. 森林：连通分支大于1，且每个连通分支均为树的非连通图.1. 例1：在偏远地区，可以通过公路连接分散的村落，但没有任何电话服务。我们希望铺设电话线路，使得每一对村落都可以通过电话线连接(不必是直接的)。沿着现存的公路铺设电话线最便宜，问沿着哪些公路铺设电话线，可以确保每一对村落被连接，且电话线的总长

2、度达到最小(电话线总长度可能与安装总成本成正比)？二.最小生成树解：寻找最小生成树.例2：假设在一个没有良好高速公路的偏远地区涌现了几个城市，理想的是建筑足够多的高速公路，使得城市之间或者直接通过高速公路往来，或者可以通过去其他城市来实现彼此的互相往来. 现在我们希望成本最小化.注: (1)成本最小化即：可以实现城市间的互通，同时，每条高速路都不浪费(即去掉后就不能互通了).(2)不允许高速路在所研究的城市以外的某点处连接.此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和(如ABAC).ABC最短网络问题:如何用最短的线路将三部电

3、话连起来？v但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长N比原来只连三点的最短路径O要短。v这样得到的网络不仅比原来节省材料，而且稳定性也更好。 ABCP斯坦纳（斯坦纳（SteinerSteiner）最小树）最小树是可以在给定的点之外再增加若干个点(称为斯坦纳点斯坦纳点)，然后将所有这些点连起来。 如果不允许增加任何额外的点作为网络的顶点，这种最短网络称为最小生成树最小生成树。3在前面的例子中Steiner最小树的长为 . 最小生成树的长为2.1968年贝尔实验室波雷克(Pollak)和研究员吉尔伯特(Gilbert)提出如下猜想：平面上任意n点集，斯

4、坦纳最小树长与最小生成树之长的比值的最小值是 . 32 1967年前，贝尔公司按照连结各分部的最小生成树的长度来收费。1967年一家航空公司戳了贝尔公司一个大洞。当时这家企业申请要求贝尔公司增加一些服务点，而这些服务点恰恰位于构造该公司各分部的斯坦纳最小树需增加的斯坦纳顶点上。这使得贝尔公司不仅要拉新线，增加服务网点，而且还要减少收费。这一意外事件迫使贝尔公司自此以后便采用了斯坦纳最小树原则 。1. 问题描述：如村落间铺设电话线的问题.三. Kruskal算法2. 算法思想(贪婪算法)：总是选择权最小的边.3. 算法描述：步骤1：按照权的递增顺序排列图G的边，置集合T为空集.步骤2：检查排列序

5、表中第一条未检查的边，此边被放入T中当且仅当它不与T中的边形成回路。若这条边被加入T中，进入步骤3，否则重复步骤2.步骤3：若T有n-1条边，则停止，T即为所找的最小支撑树，否则，进入步骤2.5. 实例：b 53 d8 54 e 12 10 70 22a 63 c解：abcdde-bd排序：ab, cd,de,ec,bd,be,ac,ae 四. Prim算法1. 算法思想(贪婪算法)： 从顶点出发，对任意点，总是选择与其关联的权最小的边放入T中.2. 算法描述：步骤1：置集合T为空集,任选一点v放入树T中.步骤2：将连接T中的点与V-V(T)中的点的所有边中权最小的边加入到T中，若权最小的边有

6、多条，任选其一，若不可能把任一条边加入到T中，则停止，输出G非连通.步骤3：若T有n-1条边，则停止，T即为所找的最小支撑树，否则，重复步骤2.5. 实例：b 53 d8 54 e 12 10 70 22a 63 c解：abbddc-de1). 选点a,T=a,选出ab,2). T=ab,选出bd, 3). T=ab,bd,选出dc, 4). T=ab,bd,dc,选出de2 最短路径问题一. 简介1. 问题：寻找网络中两个顶点之间的最短路径问题.2. 实例：希望利用公路开车从上海到北京，希望路程最短.注：(1)点城市，边公路， 权距离，连通赋权图.(2)所有权均非负.二. Dijkstra

7、算法(1959)1. 算法思想：00()0,( ),l uvl vu对其他点 则标号为在算法进行过程中，不断修改这些标号，使得每个点都最终可以得到一个标号，这个标号首先给始点一个标号到该点的最就是始点短路长.SSS直观思路即：从始点开始，每次找到始点最近的边，将其顶点设为 ，不断地将始点与 之间的最短路所涉及的边之端点加入到 ，直至到达终点.0001111(,0.)0, ( ),)();min ( )2, ( )min ( ), (.3-1,-1,:12,.iiiiiviiiSv l vSuw uvl vl uivS l vluSv l uSininiui步骤：置且步骤 ：对每个置对其他点计算

8、并把达到这个最小值的一个顶点步骤 ：记若则停止，若则，转步骤为2. 算法描述(从u0到un-1)：3. 实例： a 3 d 3 5 x 8 b 2 1 y 4 e 8 c 1 1) S0=x,其他l(v)=,l(x)=02) l(a)=3,l(b)=8,l(c)=4,S1=x,a3) l(b)=8,l(c)=4,l(d)=6, S2=x,a,c4) l(b)=8,l(e)=5,l(d)=6,S3=x,a,c,e5) l(d)=6,l(b)=7,l(y)=13, S4=a,c,e,d6) l(b)=7,l(y)=11,S5=a,c,e,d,b7) l(y)=11,S6=a,c,e,d,b,y 一

9、笔画问题)v在哥尼斯堡有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。 Euler在1736年访问Konigsberg时，他发现当地的市民正从事一项非常有趣的消遣活动。这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。 Euler证明了不可能存在这样的路线。三. 中国邮递员问题(1962，管梅谷) 1. 问题：邮递员每天从邮局选好邮件，送到他所管辖的邮区的客户手中，再返回邮局，他每天必须走过每条街道至少一次，问如何选择邮递路线，使得他走过的投递总行程最短？2. 模型：非负赋权图G：顶点-交叉口或终端，边-街道，权-街道长度，此即求图

10、的通过每条边至少一次的闭途径,称为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).

11、步骤4：求K|v0|中的权最小的完美匹配M.步骤5：在G中求以M中每条边的两端点为端点的最短路.步骤6：将步骤5中所求的每条最短路上的每条边都添上一条等权的“倍边”，得到新图G.步骤7：在新图G中用Fleury算法求欧拉环游，则即为G的最优环游.5. Edmonds-Johnson算法三. 旅行商问题1. 问题：设有n个城镇，已知每两个城镇之间的距离，一个售货员自一个城镇出发巡回售货，问他该如何选择路线，能使每个城镇经过一次且仅一次，最后再回到出发地而且行程最短。2. 模型：此即在赋权完全图中，寻找最小权的哈密尔顿圈.注：这个问题是NPC的.1 0001110 10110 110 11,2(

12、) , ,311,:12,.niiiii ivevVvev vvv vGvvviniivv vvvCvvv 步骤：任选一点 作为起点，找一条与 关联的权最小的边的另一端点记为即得初始路.步骤 ：若已选定路，在中取一个与 最近(即权最小)的顶点，设为得到已选出.步骤 ：若则令，转步骤 ，否则，记结束3. 近似算法(最邻近算法)4. 实例：求下列赋权完全图的最优Hamilton回路. A 2 1 3 4 B 5 E 9 7 10 6 C 8 D解：ACEBDA: 权和 25 BACEDB: 权和 25 CABEDC： 权和 22 DACEBD： 权和 25 EACDBE: 权和 27所选初始点不同

13、，得到的近似解也不同.5. 修改方法：最邻近插入法思想方法：每次迭代中都让其构成一个闭的旅行路线，它由多个阶段形成，每次都比上一次多一个顶点。求解时，在已建立旅程之外的顶点中，寻找最邻近于旅程中某个顶点的顶点，将其插入该旅程中，并使增加的距离尽可能小，当全部顶点收入这个旅程后，就找到了最短哈密尔顿回路的近似解.实例： A 2 1 3 4 B 5 E 9 7 10 6 C 8 D(1) 初始点为A，组成闭旅程AA，下一阶段，最邻近A的顶点为C，建立闭旅程ACA,再寻找最邻近A与C的顶点B，组成闭旅程ACBA.(2) 从D,E中找一个最邻近ACBA的顶点D，将其插入，分别得到ACDBA(权和20)

14、，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).iijijijjiijijjijjijiji

15、jijjixvvCvAffvvCvvvyyxfyAfv源 标号选择一个已标号的顶点对其所有未标号的邻点作如下处理：若弧令标号弧令标号重复 过程直到且并给若且并给汇 被标号，或不再有顶点可以标号为止若 得到标号，说明存在一条增广2.Pyf路 ，进入步骤 调整过程；若 未得到标号，标号过程无法进行，说明 即为最大流(1) 标号过程(,),)( min (), min( ,)( ,)( ,),1).( )2). 1ijijijijjivPvPijijijijijvjvijiminffPfv vPfCfv vPv vPffv f，调令 得到新的可行流，其总流量为去掉所整增广路 中 的流量有标号，回到步

16、骤 ，重复以上过程，直到无法 如下：进行为止.(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).