《道路与回路》ppt课件

《《道路与回路》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、道路与回路1LuChaojun,SJTU有向道路与有向回路定义:有向图G中边序列P=(ei1,ei2,…,eiq),其中eij=(vk,vl)满足:vk是eij1的终点,vl是eij+1的始点,就称P是G的一条有向道路.如果eiq的终点也是ei1的始点,则称P是G的一条有向回路.简单有向道路/回路:P中边不重复出现.初级有向道路/回路:P中结点不重复出现.LuChaojun,SJTU2LuChaojun,SJTU3道路与回路定义:无向图G中,若点边交替序列P=(vi1,ei1,vi2,ei2,…,eiq1,viq)满足:vij和vij+1是eij的两个端点,则称P

2、是G中的一条链或道路(path).如果viq=vi1,则称P是G中的一个圈或回路(circuit).简单道路/回路:P中没有重复出现的边.初级道路/回路:P中没有重复出现的结点.LuChaojun,SJTU4连通性若无向图G的任意两个结点之间都存在道路,就称G是连通的(connected).对有向图G,若不考虑边的方向时是连通的,则称G是(弱)连通的.若G的连通子图H不是G的任何连通子图的真子图,则称H是G的极大连通子图,或称连通支(connectedcomponent).显然G的每个连通支都是它的导出子图.任何非连通图都是2个以上连通支的并.道路与回路的判定判断图中

3、两个结点之间是否存在道路,或说是否连通.方法:邻接矩阵法Warshall算法搜索法广探法(广度优先搜索)深探法(深度优先搜索)LuChaojun,SJTU5邻接矩阵法利用G的邻接矩阵A=(aij)nn判断两点间是否可经一条边连通,因为aij=1iff(vi,vj)E(G)利用A2=(aij(2))nn判断两点间是否可经两条边连通,因为aij(2)=nk=1aikakj0iffk使aik=akj=1iffvk使(vi,vk),(vk,vj)E(G)一般地,利用As判断两点可经s条边连通.LuChaojun,SJTU6邻接矩阵法(续)令P=A+A2+…+A

4、n=(pij)nn若pij=t,则从vi到vj有t条道路;若pij=0,则n步之内从vi不能到达vj,从而vi和vj之间没有道路.LuChaojun,SJTU7Warshall算法若只关心两点间道路的存在性,不关心道路的长度和数量,则前面的方法中可改用逻辑运算:aij(s)=nk=1(aik(s1)akj(s1))P=AA2…AnP称为图G的道路矩阵:pij=1iffvi与vj之间有道路.计算道路矩阵P的Warshall算法PA;fori=1tondoforj=1tondofork=1tondopjkpjk(pjipik)LuChaojun,S

5、JTU8Warshall算法(续)算法思想第i次循环:对当前(第i1次循环的结果)不直接连通的顶点vj和vk(即没有边(vj,vk)),看它们是否可以通过vi间接连通(即存在边(vj,vi)和(vi,vk)).如果是,则在原图中增加边(vj,vk).最后得到道路矩阵定理:Warshall算法的结果确是图G的道路矩阵.广探法广度优先搜索(breadthfirstsearch,BFS)判断从v0到vi是否存在道路:(1)令A0={v0}.(2)对Ak中的每个结点v,求+(v),令Ak+1=vAk+(v)(3)若viAk+1,则存在从v0到vi的道路;否则,若还

6、有未搜索过的结点,令AkAk+1,返回(2)继续.可通过做记号,避免重复搜索同一个结点.LuChaojun,SJTU10深探法深度优先搜索(depthfirstsearch,DFS)判断从v0到vi是否存在道路:(1)令vk=v0;(2)求vk的一个未搜索过的直接后继v;(2)若v=vi则道路存在;(3)若vvi且v有直接后继,则令vk=v并返回(2);若vvi且v没有直接后继,则返回(2)回溯.可通过把经过的结点压入堆栈,来记住回溯点.可通过做记号,避免重复搜索同一个结点.LuChaojun,SJTU11哥尼斯堡七桥问题1736年,Euler发表论文“哥尼斯堡

7、的七座桥”,解决了下图中是否存在经过每条边一次且仅一次的回路的问题.12LuChaojun,SJTU欧拉道路与回路定义:无向连通图G=(V,E)中包含所有边的简单回路(道路)称为G的欧拉回路(道路).定理:无向连通图G中存在欧拉回路的充要条件是G中各结点的度都是偶数.:对任一v,回路沿ei进入v必然有ej从v出来.:从任一v0出发必能构造一简单回路C(否则终点不是偶数度).令G=GC,对G的各连通支继续此过程.最后合并所有回路即所求.例:七桥问题无欧拉回路.13LuChaojun,SJTU欧拉道路与回路(续)推论1:无向连通图G中存在欧拉道