第二章 道路与回路.ppt

Click to edit Master title style,*,第二章 道路与回路,2.1,道路与回路,有向道路,有向图,G=(V,A),中，一条,有向道路,指的是一个首尾相接的弧的有限非空序列,P,=,a,1,a,2,a,k,(,k,1),其中,v,i,V,(,i,=0.,k,),a,j,A,(,j,=1.,k,),且,a,j,=,(,j,=1.,k,),v,0,和,v,k,分别称为,P,的,起点,和,终点,，,k,称为,P,的,长度,在简单图中，也可记作,P,=,(,v,0,，,v,1,，,v,2,，,，,v,k,),或,v,0,v,1,v,2,v,p,2.1,道路与回路,简单道路,若对任意的,i,j,有,a,i,a,j,，,称之为,简单有向道路,(simple path,没有重复边的路径,),回路,若,v,0,=,v,n,，,称之为,封闭的,简单封闭有向道路（闭迹）称为,有向简单回路,初级道路,若对任意的,i,j,有,v,i,v,j,，,称之为,初级道路,/,基本道路,/,路径,(,elementry,or primary),圈,若对任意的,i,j,有,v,i,v,j,而例外地,v,0,=,v,n,，,称之为,初级回路,/,圈,(cycles),。

无向图具有完全类似的定义,2.1,简单道路与圈,2.1,道路与回路,练习：找出上图结点,1,至结点,9,的简单道路和初级道路，,1,到,1,的有向回路和圈容易证明：,定理,2-1,（,1,）基本道路是简单道路；,（,2,）如果存在,u,到,v,的道路，则存在,u,到,v,的基本道路；,(3)n,阶图的基本道路长度不超过,n-1;,(4)n,阶图的圈的长度不超过,n.,2.1,基本道路,定理,2-2,无向图,G=(V,E),，,u,v,V,且,u,v,若,u,v,之间存在两条不同的路，则,G,中存在一条回路证明,（构造法）,定理,2-3,无向图,G=(V,E),中每个顶点的度均为偶数，且至少有一个顶点不是孤立点，则,G,中存在一条回路证明,（反证法）设,v,不是孤立点，从,v,出发的最长简单路径经过的顶点是,v,0,(=,v,),v,1,v,n,-1,v,n,，则必,存在,0,i,n,使得,v,n,=,v,i,，否则,因为,v,n,的度是偶数，存在与,v,n,邻接另一个顶点,u,从而得到一条更长的简单路径矛盾！,2.1,道路与回路的关系,可达性,对于有向图,G=(V,A),中，若从,v,i,到,v,j,存在一条路，则称,从,v,i,到,v,j,是可达,的，或称,v,i,可达,v,j,。

对无向图,G=(V,E),，,结点间的可达性是对称的连通性,对于无向图,G=(V,E),，任意两点之间可达时，称,G,为连通的（连通图）G,中的一个极大连通子图称为,G,的一个连通分支一个图总是由一些连通分支构成的G,的连通分支数，记为,W,(G),2.2,连通性,强连通性,对于有向图,G=(V,A),，如果任意两点之间相互可达，则称,G,为强连通的,.,弱 连通性,对于有向图,G=(V,A),若不考虑弧的方向后得到的无向图是连通的，则称有向图,G,是弱连通的2.2,有向图的连通性,定理,2-5,G=(V,E),，,n,=|V|,，,若对任意,u,v,V,且,u,v,，,都有：,Deg,(,u,)+,Deg,(,v,),n,1,，,则,G,连通证明,(,反证法,),设,G,可分为不连通的两部分,G,1,=(V,1,E,1,),和,G,2,=(V,2,E,2,),，,选取,u,V,1,v,V,2,则,Deg,(,u,)=|V,1,|-1,，,Deg,(,v,)|V,2,|-1,，,故,Deg,(,u,)+,Deg,(,v,)0,0,其他,可求得,G,的道路矩阵,P,算法复杂度,O(,n,4,),2.2,道路矩阵,道路矩阵可以通过二值矩阵的逻辑运算求得。

定义,二值元素的逻辑运算：,0,0=0,，,0,1=1,0=1,，,1,1=1,0,0=0,，,0,1=1,0=0,，,1,1=1,定义,二值矩阵的逻辑运算设有矩阵,A=(,a,ij,),，,B=(,b,ij,),，,矩阵元素值域为,0,1,，定义运算：,2.2,道路矩阵的计算,定义,A,(,k,),=A,(,k,1),A (,k,2),，,A,(1),=A,注意,A,(,k,),与,A,k,的区别,定理,2-12,设,A,n,n,是图,G,的邻接矩阵，若从,v,i,到,v,j,存在长度为,l,的路，则,A,(,l,),ij,=1,，,否则,A,(,l,),ij,=0,证明,对,l,作归纳；或直接引用,定理,2-11,2.2,道路矩阵的计算,Warshall,算法,设,A,n,n,是图,G,的邻接矩阵，求,G,的道路矩阵,P,P,A,for i=1 to n do,for j=1 to n do,for k=1 to n do,p,jk,p,jk,(,p,ji,p,ik,),计算复杂度,O(n,3,),2.2,道路矩阵及,Warshall,算法,初始：,p,ij,表示有无长度为,1,的直达路径,第,i,次外层循环结束时：,p,jk,表示有中间通过,v,1,v,2,v,i,的路径,。

例,图,G,的,邻接矩阵,A,如右，使用,Warshall,算法求,G,的道路矩阵,P,解,P,A,2.2,道路矩阵及,Warshall,算法,(1),i,=1,j,=1,2,3,4,增量方向,i,=1,矩阵元素处理次序：,p,11,，,p,12,，,p,13,，,p,14,，,p,21,，,p,22,，,p,31,，,p,41,，,，,p,44,，,2.2,道路矩阵及,Warshall,算法,如：,p,11,=,p,11,(p,1i,p,i1,)=p,11,(p,11,p,11,)=0,p,12,=,p,12,(p,1i,p,i2,)=p,12,(p,11,p,12,)=1,p,13,=,p,13,(p,1i,p,i3,)=p,13,(p,11,p,13,)=0,结果为,2.2,道路矩阵及,Warshall,算法,2.3,图上的搜索,可以使用搜索的方法判断从一个顶点,u,到另一个顶点,v,是否有路径深度优先,DFS,从顶点,u,出发检查其后继,u,1,是否，如果不是，则从,u,1,开始进行深度优先搜索；如果没有后继,则回溯，直至找到或者没有可搜索的顶点2.3,图上的搜索,广度优先,BFS,从,u,出发，首先检查其所有的直接后继是否等于；然后依次检查这些后继的直接后继，直到找到或者没有可遍历顶点。

练习：编写一个使用深度优先或者广度优先搜索判定两个点之间是否有道路的程序Euler,回路,若连通图,G=(V,E),中存在一条简单回路（无重复边）经过,G,的所有边，则称该回路为,G,中的一条,Euler,回路存在,Euler,回路的图称为,Euler,图定理,2-6-1,设有连通,图,G=(V,E),，,则下述命题等价：,(1)G,是一个,Euler,图；,(2)G,的每一个顶点的度是偶数；,证明,1:,见课本证明,2:,只证充分性对边数,|E|,进行归纳只有一个边的连通图是,Euler,图假定对于,|E|2,（否则，所有结点为,2,度的图是,Euler,图，），,v,w,是,u,的两个邻接点，则,G=G-,+,是具有,k,条边，所有结点度数是偶数如果,G,是连通图，由归纳假设，此图存在,Euler,回路，那么将此回路的边,用,和,替换后得到图,G,的,Euler,回路如果,G,不连通，至多有两个连通分支构成，由归纳假设，两个连通分支有,Euler,回路，不难由这两个,Euler,回路构造原图的,Euler,回路2.4 Euler,回路,注意定理中对图的连通性的假定；,Euler,回路经过图的所有边一次且仅仅一次。

定理对非简单图也成立；,定理的证明过程给出了为一个,Euler,图构造,Euler,回路的构造算法,定理,2-7,设连通图,G=(V,E),中恰有,2,个顶点度为奇数，则,G,存在,Euler,道路证明,连接两个奇度数结点形成,Euler,图，再删除该边即可2.4 Euler,回路,有向图的,Euler,回路,若有向连通图,G=(V,A),中存在一条简单有向回路经过,G,的所有弧，则称该回路为,G,中的一条,Euler,回路，称该图为,Euler,有向图定理,2-6-2,设连通有向图,G=(V,A),，,则下述命题等价：,(1)G,是一个,Euler,有向图；,(2)G,的每一个顶点的入度等于出度；,证明,（略）,2.4 Euler,回路,Exercises,Prove that if every vertex in a connected graph G has even degree,then the graph G is an Euler graph.(Prove it by induction on the number of edges.),Prove that if every vertex of a graph has even degree,and,degree(v,)=2 for some vertex v,then there exists a simple closed path passing over v.,Hamilton,路,若连通图,G=(V,E),中存在一条初级道路（无重复顶点）经过,G,中每个顶点一次，则称该道路为,G,中的一条,Hamilton,路。

存在,Hamilton,回路（圈）的图称 为,Hamilton,图Hamilton,路经过图的所有顶点一次且仅仅一次存在,Hamilton,回路的例子,:,C,n,K,n,正十二面体,存在,Hamilton,道路的例子,不存在,Hamilton,道路的例子,Hamilton path in Wikipedia,2.5 Hamilton,道路,2.5 Hamilton,道路,2.5 Hamilton,图,构造,Hamilton,圈的简单规则：,Halmilton,圈含,n,条边；,Halmilton,圈正好包含每个结点的两条关联边，其他边可以删除；,左图如有,H,圈，则必包含三个二度结点的邻接边，从而中心结点至少有三个邻接边包含在其中，故不可能有圈定理,2-8,若,G=(V,E),是一个,Hamilton,图，,S,V,且,S,，则,G,的子图,G,S,的,连通分支数,W,(G,S),|,S|,证明,记,G,中,H-,回路为,C,，,C,中包含了,G,中所有顶点考察,C,S,：每从,C,中去除属于,S,的一个顶点，连通分支数至多增加,1,（第一次以及当该顶点处于边缘时操作不会增加连通分支数），故,W,(C,S),|,S|,而,G,可视为向,C,中添加边构成，故,W,(G,S),W,(C,S),所以,W,(G,S),|,S|,2.5 Hamilton,图,引入记号：,G=(V,E),，,S,V,。

从,G,中去除,S,中的顶点及其关联边得到的,G,的子图记为,G,S,例,图,G,1,2,3,4,5,7,8,6,令,S=2,6,，则,W,(G,S)=3,而,|S|=2,，即,W,(G,S)|S|,故图,G,不可能是,Hamilton,图1,3,4,5,7,8,图,G-S,2.5 Hamilton,图,例,Petersen,图V|=10,，,对任何,S,V,，,都有,W,(G,S),S,，,但,Petersen,图,不是,Hamilton,图（留作习题）Peterson,图存在,Hamilton,道路2.5 Hamilton,图,删除一个或者两个顶点仍然连通，删除三个顶点最多得到两个连通分支，,例,下图不存在,Hamilton,圈给图的相邻顶点标以,A,，,B,，则,Hamilton。