《道路与回路.ppt》由会员分享，可在线阅读，更多相关《道路与回路.ppt（43页珍藏版）》请在三一办公上搜索。
1、道路与回路,1,Lu Chaojun,SJTU,有向道路与有向回路,定义:有向图G中边序列P=(ei1,ei2,eiq),其中eij=(vk,vl)满足:vk是eij1的终点,vl是eij+1的始点,就称P是G的一条有向道路.如果eiq的终点也是ei1的始点,则称P是G的一条有向回路.简单有向道路/回路:P中边不重复出现.初级有向道路/回路:P中结点不重复出现.,Lu Chaojun,SJTU,2,Lu Chaojun,SJTU,3,道路与回路,定义:无向图G中,若点边交替序列P=(vi1,ei1,vi2,ei2,eiq1,viq)满足:vij和vij+1是eij的两个端点,则称P是G中的一条
2、链或道路(path).如果viq=vi1,则称P是G中的一个圈或回路(circuit).简单道路/回路:P中没有重复出现的边.初级道路/回路:P中没有重复出现的结点.,Lu Chaojun,SJTU,4,连通性,若无向图G的任意两个结点之间都存在道路,就称G是连通的(connected).对有向图G,若不考虑边的方向时是连通的,则称G是(弱)连通的.若G的连通子图H不是G的任何连通子图的真子图,则称H是G的极大连通子图,或称连通支(connected component).显然G的每个连通支都是它的导出子图.任何非连通图都是2个以上连通支的并.,道路与回路的判定,判断图中两个结点之间是否存在道
3、路,或说是否连通.方法:邻接矩阵法Warshall算法搜索法广探法(广度优先搜索)深探法(深度优先搜索),Lu Chaojun,SJTU,5,邻接矩阵法,利用G的邻接矩阵A=(aij)nn判断两点间是否可经一条边连通,因为aij=1 iff(vi,vj)E(G)利用A2=(aij(2)nn判断两点间是否可经两条边连通,因为aij(2)=nk=1 aik akj 0 iff k使aik=akj=1iff vk使(vi,vk),(vk,vj)E(G)一般地,利用As判断两点可经s条边连通.,Lu Chaojun,SJTU,6,邻接矩阵法(续),令P=A+A2+An=(pij)nn 若pij=t,则
4、从vi 到vj有t条道路;若pij=0,则n步之内从vi不能到达vj,从而vi和vj之间没有道路.,Lu Chaojun,SJTU,7,Warshall算法,若只关心两点间道路的存在性,不关心道路的长度和数量,则前面的方法中可改用逻辑运算:aij(s)=nk=1(aik(s1)akj(s1)P=A A2 AnP称为图G的道路矩阵:pij=1 iff vi 与vj 之间有道路.计算道路矩阵P的Warshall算法P A;for i=1 to n do for j=1 to n do for k=1 to n do pjk pjk(pji pik),Lu Chaojun,SJTU,8,Warsha
5、ll算法(续),算法思想第i次循环:对当前(第i1次循环的结果)不直接连通的顶点vj和vk(即没有边(vj,vk),看它们是否可以通过vi间接连通(即存在边(vj,vi)和(vi,vk).如果是,则在原图中增加边(vj,vk).最后得到道路矩阵定理:Warshall算法的结果确是图G的道路矩阵.,广探法,广度优先搜索(breadth first search,BFS)判断从v0到vi是否存在道路:(1)令A0=v0.(2)对Ak中的每个结点v,求+(v),令Ak+1=vAk+(v)(3)若viAk+1,则存在从v0到vi的道路;否则,若还有未搜索过的结点,令Ak Ak+1,返回(2)继续.可通
6、过做记号,避免重复搜索同一个结点.,Lu Chaojun,SJTU,10,深探法,深度优先搜索(depth first search,DFS)判断从v0到vi是否存在道路:(1)令vk=v0;(2)求vk的一个未搜索过的直接后继v;(2)若v=vi则道路存在;(3)若v vi且v有直接后继,则令vk=v并返回(2);若v vi且v没有直接后继,则返回(2)回溯.可通过把经过的结点压入堆栈,来记住回溯点.可通过做记号,避免重复搜索同一个结点.,Lu Chaojun,SJTU,11,哥尼斯堡七桥问题,1736年,Euler发表论文“哥尼斯堡的七座桥”,解决了下图中是否存在经过每条边一次且仅一次的回
7、路的问题.,12,Lu Chaojun,SJTU,欧拉道路与回路,定义:无向连通图G=(V,E)中包含所有边的简单回路(道路)称为G的欧拉回路(道路).定理:无向连通图G中存在欧拉回路的充要条件是G中各结点的度都是偶数.:对任一v,回路沿ei进入v必然有ej从v出来.:从任一v0出发必能构造一简单回路C(否则终点不是偶数度).令G=GC,对G的各连通支继续此过程.最后合并所有回路即所求.例:七桥问题无欧拉回路.,13,Lu Chaojun,SJTU,欧拉道路与回路(续),推论1:无向连通图G中存在欧拉道路当且仅当G中只有两个度为奇数的结点.证:连接这两顶点,则有回路.再删去这条边.推论2:若有
8、向连通图G中各结点的正负度相等,则G中存在有向欧拉回路.,Lu Chaojun,SJTU,14,周游世界游戏,1857年,William Rowan Hamilton发明了Icosian游戏.游戏目标是沿着一个十二面体(12个正五边形的面,20个顶点,30条棱)的棱边找到一条不重复地遍历各顶点的回路.,Lu Chaojun,SJTU,15,哈密顿回路与道路,定义:无向图G的一条经过全部结点的初级回路(道路)称为G的哈密顿回路(道路).简记为H回路(道路).对H回路问题要求V(G)=n 3只需考虑简单图,因为重边和自环不起作用H回路的判定很困难,没有发现充分必要的条件,只有若干充分条件.,Lu
9、Chaojun,SJTU,16,H道路的判定,定理:若简单图G的任意两结点vi与vj之间恒有 d(vi)d(vj)n1则G中存在H道路.证明思路:(1)由定理条件:G是连通图.(2)令P是G中最长初级道路,则P是H道路.若不是:(i)由定理条件:必有经过P中结点的初级回路C.(ii)由连通性:C必可与C外某相邻结点构成比P更长的初级道路.,Lu Chaojun,SJTU,17,H回路的判定,定理(Ore,1960):若简单图G(n3)的任一对不相邻结点vi与vj都满足d(vi)d(vj)n则G有H回路.书上推论2.4.1条件更宽,且漏了n3的条件.定理(Dirac,1952):若简单图G(n3
10、)的任一结点的度 n/2,则G有H回路.书上推论2.4.2漏了n3的条件.,Lu Chaojun,SJTU,18,H回路的判定(续),引理:简单图G若有不相邻结点vi,vj满足d(vi)d(vj)n,则G有H回路 iff G+(vi,vj)有H回路.对G不断加入这样的边(vi,vj),直至不再有满足条件的结点对,最终得到的图称为G的闭合图,记作C(G).引理:简单图G的闭合图是唯一的.定理(Bondy&Chvtal,1976)简单图G有H回路 iff C(G)有H回路.推论:若C(G)=Kn,则G有H回路.Ore定理和Dirac定理显然是这个推论的直接推论.,Lu Chaojun,SJTU,1
11、9,旅行商问题,实际问题中往往涉及赋权图.TSP(traveling salesman problem):给定一正权完全图,求总权值最小的H回路.右图:经过德国15个大城市的一个TSP行程.这是43,589,145,600个可能行程中最短的一个.,Lu Chaojun,SJTU,20,精确解法:穷举搜索,最直接的精确解法就是穷举搜索,即检查所有可能的H回路,计算各自的总权值,选择最小者.对Kn,存在(n1)!/2个H回路.(Why?)例如:对n=25,24!/2 3.11023如果每纳秒(109秒,十亿分之一秒)检查一条H回路,大约需要一千万年才能得到最优解.,Lu Chaojun,SJTU,
12、21,精确解法:分支与定界,Branch and Bound(BB)是一种求解各类最优化问题(尤其是离散与组合最优化问题)的一般算法.算法思想:系统地枚举所有的候选解,利用被优化量的上界和下界,从候选空间将大批不可能候选全部丢弃.最早由A.H.Land和A.G.Doig于1960年在线性规划领域中提出.,Lu Chaojun,SJTU,22,求解TSP:分支与定界,结点:v1,vn,边:e12,e13,e1n,e23,e24,e(n1)n初始上界d0;(1)所有边按权值从小到大排序:e(1),e(2),e(m)(2)i1,对边序列按DFS选n条边构成边集si;经过的点入栈.(3)判断si是否H
13、回路.方法:si中每个结点标号只出现2次,且所有边只构成一个回路.(4)若否:删除si中最长边e(k),换成e(k+1),得si+1.ii+1,返回(3);若是:且i=1则d0d(s1),结束;否则若d(si)d0,则d0d(si).(5)若栈空,则结束,d0即最优解.否则退栈,建立一个新分支:若新分支的d(si)d0,继续退栈;若d(si)d0,则返回(3).,Lu Chaojun,SJTU,23,近似解法:便宜算法,在Kn满足三角不等式(即:无捷径)时的一个算法:设顶点集为S=1,2,n.(1)回路T=(1,1);剩余结点S=2,3,n;w(1,1)=0;iS,kT:w(i,k)=w(i,
14、1);(2)在S与T之间求最近的一对顶点 jS,tT,即w(j,t)=miniS,kT w(i,k)将j插入到T=(,t1,t,t2,)中:若w(j,t1)w(t,t1)w(j,t2)w(t,t2)则插到t与t1之间;否则插到t与t2之间.(3)S S j;若S=则结束;否则iS,w(i,k)minw(i,k),w(i,j);转(2).,Lu Chaojun,SJTU,24,便宜算法的效果,定理:设正权完全图的边权满足三角不等式,其TSP的最佳解是On,便宜算法的解是Tn,则Tn/On2.(教材中此定理的证明对记号的使用有问题)便宜算法的计算复杂度为O(n2).,Lu Chaojun,SJTU
15、,25,最短路径问题,Shortest Path Problem:给定赋权图,求结点间的最短道路,即道路权值之和最小.Single-pair:某对结点间;Single-source:某结点到其他各结点间;All-pairs:任意结点对之间.权值的情况:都是正数;都等于1;任意实数.,Lu Chaojun,SJTU,26,约定和记号,我们讨论single-source情形.即局限于求v1到其他各点vi的最短路径.记v1到vi的一条路径P(i)的长度为(i)=eP(i)w(e)=(vj vk)P(i)wjk若P(i)中含有回路C,令P(i)是其中不含C的初级道路,显然(i)=(i)+(C).若(C
16、)0,则不存在最短P(i).若(C)0,则(i)(i).即最短路径一定是初级道路.,Lu Chaojun,SJTU,27,正权图最短路径的性质,引理1:正权图中,若P(i)是v1到vi的最短路径,且vjP(i),则P(j)是v1到vj的最短路径.v1 vj vi引理2:正权图中任意一条最短路径的长度大于其局部路径长度.将v1到各点的最短路径从小到大排列:(1)=(i1)(i2)(in)由引理2:对kl1,P(ik)不是P(il)之部分.(由短生长)再由引理1:(il)=min1 jl(ij)+wijil).此即Dijkstra算法核心思想.v1 vij vil,Lu Chaojun,SJTU,
17、28,Dijkstra最短路径算法,Dijkstra算法(1)置S=2,3,n;(1)=0;对iS,若i+(1)则(i)=w1i,否则(i)=.(2)令(j)=miniS(i).置SSj,若S=,结束.(3)对iS+(j),置(i)min(i),(j)+wji),转(2).v1 vi vj,Lu Chaojun,SJTU,29,(i),(j),wji,关键路径方法,关键路径方法(critical path method,CPM)是用来调度一系列工程活动的基于数学的算法,是项目管理的重要工具.CPM由DuPont公司于1950s开发.CPM有广泛应用.任何由相互依赖的任务组成的项目都可应用此调度
18、方法.CPM的基本技术是构造项目模型,其中包括一系列任务,各任务所需时间,任务间的依赖关系.,Lu Chaojun,SJTU,30,关键路径,关键路径是构成最长路径的任务序列.它决定了项目的最早结束时间.其中任何任务的延误都将直接影响项目完成时间.CPM计算关键路径,以及各任务的开始和结束的最早/最晚时间.此过程确定了哪些任务是关键的(不可延误),哪些是浮动的(可延迟).,Lu Chaojun,SJTU,31,求解方法,假设任务之间只存在时间次序的约束.有两种图示法:PT图PERT图,Lu Chaojun,SJTU,32,PT图,PT(potential task)图:用结点表示工序,若工序i
19、完成之后工序j才能开始,则用有向边(i,j)表示,边权wi表示工序i所需时间.必不存在有向回路.任一工序i的最早开始时间=从工序1到工序i的最长路径(时间).任一工序i的最晚开始时间=(从工序1到完工的最长路径)(从工序i到完工的最长路径).任一工序i的允许延误时间=最晚开始时间最早开始时间.,Lu Chaojun,SJTU,33,工序最早开始时间的分析,引理:若图G中不存在有向回路,则必存在负度或正度为零的结点.定理:若图G中不存在有向回路,可以将G的结点重新编号为v1,v2,vn,使得对任意边(vi,vj)E(G),都有i j.设v1到各点的最长路径为0=(v1),(v2),(vn)则(v
20、j)=max1 ij(vi)+w(vi,vj).此即最长路径算法的基础.,Lu Chaojun,SJTU,34,工序最早开始时间的算法,算法1(最长路径算法)(1)对结点如前所述重新编号:v1,v2,vn;(2)(v1)0;(3)对j从2到n,计算(vj)=maxvi-(vj)(vi)+w(vi,vj).,Lu Chaojun,SJTU,35,工序最晚开始时间的分析,设(vn)是最早完工时间,则工序i的最晚开始时间为(vi)=(vn)(vi,vn).问题变成:如何计算(vi,vn)?方法1:图G转置可得G.在G中以vn为起点,它到各点的最长路径可用前面算法实现.上式就成了(vi)=(v1)(v
21、i),可以算出(vi).方法2:更好的算法仍利用原图G进行计算.根据(vi,vn)=maxvj+(vi)(vj,vn)+w(vi,vj)逆序求出0=(vn,vn),(vn1,vn),(v1,vn).,Lu Chaojun,SJTU,36,工序最晚开始时间的算法,算法2(1)对结点如前所述重新编号:v1,v2,vn;(2)(vn)=(vn);(3)对j从n1到1,计算(vj)=(vn)(vj,vn)=(vn)maxvi+(vj)(vi,vn)+w(vj,vi)=minvi+(vj)(vn)(vi,vn)w(vj,vi)=minvi+(vj)(vi)w(vj,vi).工序i的允许延误时间t(vi)
22、=(vi)(vi).,Lu Chaojun,SJTU,37,PERT图,PERT(Program Evaluation and Review Technique):是一种项目管理模型,用来表示和分析项目涉及的任务.由通用动力公司(GD)和美国海军于1950s开发.有向边表示工序,边权值表示该工序所需时间.结点表示工序的开始和结束.如果工序ei完成后ej才能开始,则令vk是ei的终点和ej的始点.,Lu Chaojun,SJTU,38,PERT图的分析,关键路径:从v1到vn的最长路径.其长度就是最早完工时间.ek=(vi,vj)的最早开始时间是(vi).用算法1.ek的最晚开始时间是(vi,v
23、j)=(vn)(vj,vn)w(vi,vj)=(vj)w(vi,vj);用算法2计算(vj).工序ek的允许延误时间是t(vi,vj)=(vi,vj)(vi)=(vj)(vi)w(vi,vj);,Lu Chaojun,SJTU,39,中国邮递员问题,Chinese Postman Problem(CPP):邮递员从邮局出发,走遍所管区域的每条街道(允许重复),并返回邮局.要求路径总长度最短.我国管梅谷教授于1960s首先研究.问题特点:不一定存在欧拉回路,这时某些街道必须重复经过.关键要使重复路段最短.,Lu Chaojun,SJTU,40,无向图的CPP,图G所有结点的度都是偶数:则存在欧拉
24、回路,且任一欧拉回路都是解.图G只有两个度为奇数的结点vi和vj:则存在vi到vj的欧拉道路Eij.再找一条vj到vi的最短道路Pji,欧拉回路Eij+Pji是解.图G有两个以上(2k个)度为奇数的结点:定理:图G有最佳邮路L iff(1)L中的任一边最多重复一次;(2)对G的任一回路C,L中处在C上的重复边长度之和不超过C长度的一半.,Lu Chaojun,SJTU,41,最佳邮路的构造,奇偶点图上作业法(1)找出度为奇数的结点(2k个);(2)奇数度结点任意分成k对,每一对用添加的重复边(道路)相连;(3)删除重复添加的边(每次删除两条),使得每条边最多重复一次;(4)检查所有回路C:若在C上的重复边长度和超过C长度的一半,则将原重复边删去,为原来没有重复的边添加重复边.(5)对最终的图求欧拉回路.,Lu Chaojun,SJTU,42,End,43,Lu Chaojun,SJTU,
