离散数学课件第八章-(第2讲).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,8.2,路与图的连通性,1,、路的定义,：在图,G=,中，设,v,0,，,v,1,，,v,n,V,e,1,e,2,e,n,E,，其中,e,i,是关联于结点,v,i-1,v,i,的边，结点与边的交替序列,v,0,e,1,v,1,e,n,v,n,称为联结,v,0,到,v,n,的,路,。,v,1,v,4,v,5,v,2,v,3,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,v,1,v,4,v,5,v,2,v,3,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,v,0,v,3,v,4,v,1,v,2,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,路的其它概念,（,1,）在路,v,0,e,1,v,1,e,n,v,n,中，,v,0,和,v,n,分别称作,路的起点与终点,。,（,2,）一条路中所有的边的数目称作,路的长度,。,（,3,）一条路中所有的边均不相同，则此路称作,迹,。,（,4,）一条路中所有的结点均不相同，则此路称作,通路,。,显然：通路必为迹，而迹不一定是通路。,v,0,v,3,v,4,v,1,v,2,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,路的其它概念,（,5,）在路,v,0,e,1,v,1,e,n,v,n,中,，,若,v,0,=,v,n,则路称作,回路,。,（,6,）除,v,0,=v,n,外，其余结点和所有边均不相同的回路，称作,圈,(,基本回路,),。,（,7,）,所有边均不相同的回路，称作,简单回路,。,显然：基本回路必为简单回路，反之，则不然。,v,0,v,3,v,4,v,1,v,2,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,路的表示方法：,(a),结点表示法：,(b),边表示法：,例：给出有向图，求起始于，终止于,4,的路。,在下图中，,ADEBCF,；,ADEBCEF,这两条路，哪个是通路，哪个是迹？,练习：,在下图中，求,v,1,到,v,4,长度分别为,1,，,2,，,3,的路分别有哪些？,练习：,解：,v,1,到,v,4,长度分别为,1,和,2,的路：没有。,v,1,到,v,4,长度为,3,的路一条：,v,1,v,2,v,3,v,4,。,定理,1,：,在一个,n,阶图中，如果从结点,u,到结点,v,存在一条路，则从从结点,u,到结点,v,必存在一条长度小于等于,n-1,条边的通路。,定理,2,：,在一个,n,阶图中，若存在,v,到自身的简单回路，则必存在,v,到自身长度小于等于,n,的基本回路。,无向图的结点连通性,定义：设图为无向图，且,u,vV,，若从,u,到,v,存在任何一条路径，则称,u,到,v,是连通的。,有向图的结点可达性,定义：设图为简单有向图，且,u,vV,若从,u,到,v,存在任何一条路径，则称,u,到,v,是可达的,。,图的连通性：,（,1,）,连通性与非连通性：,若无向图,G,是平凡图，或,G,中任意两结点间都是连通的，则称图,G,是连通图，否则称,G,是是非连通图。,一个有向图，忽略边的方向后得到的无向图若是连通的，则称该有向图为连通图，否则称非连通图。,（,a,）,a,b,c,d,（,b,）,a,b,c,d,练习：已知关于人员,A,B,C,D,E,的下述事实：,A,说英语；,B,说英语和西班牙语；,C,说英语，意大利语和俄语；,D,说日语和西班牙语；,E,说法语，日语和俄语。,试问，上述五个人中是否任意两人都能交谈。,（如果必要，可由其余,3,人所组成的译员链帮忙）,（,2,）,连通分支,若无向图,G,的每个子图都是连通图，称为,G,的连通分支。,G,的分支数记作,p(G),。,（,3,）,强连通，单向连通，弱连通,简单有向图,G,：,如果,G,的任何两结点间均是互相可达的，则称图,G,是,强连通,的。,如果,G,的任何两结点间至少有一个结点到另一结点是可达的。则称,G,是,单向连通,的。,如果忽略边的方向，将它看成无向图后，图是连通的，则称该图为,弱连通,的。,若,G,是强连通的，则,G,是单向连通的。若,G,是单向连通的，则,G,是弱连通的。反之，不成立。,(b),A,B,C,(c),A,B,C,A,B,C,(a),练习：,下列各有向图是强连通图的是（）,.,定理,：一个有向图是强连通的充要条件是：它包含一个回路，该回路至少包含每个结点一次。,A,B,C,D,定义：设，为一简单有向图，且是的子图。,具有强连通性质的极大子图称为强分图；,具有单侧连通性质的极大子图称为单侧图；,具有弱连通性质的极大子图称为弱分图。,例,：,G,的强分图为：,1,2,3,，,4,，,5,，,6,G,的单侧图为：,1,2,3,4,5,，,5,6,G,的弱分图为：,1,2,3,4,5,6,定理：在任一简单有向图，中，有向 图的每一个结点位于且只位于一个强分图之中。,1,4,2,3,5,定义,设无向图,G=,是连通无向图,V,1,V,若,G,V,1,不连通或是平凡图,而对于,V,1,的任何一个非空真子集,V,2,，,G,V,2,是连通的，则称,V,1,是,G,的点割集。,在下图中,v,2,v,4,v,3,和,v,5,都是点割集,v,3,和,v,5,都是割点。,若某一个结点构成一个点割集，则称该结点为割点。,练习：,设图,G=,的结点集为,V=v,1,v,2,v,3,边集为,E=,则,G,的割点是,(),A.v,1,B.v,2,C.v,3,D.v,2,v,3,定义：,设,G,为无向连通图且为非完全图,则称,(G)=min|V,1,|V,1,为,G,的点割集,为,G,的点连通度,简称连通度。,(G),简记为,。,完全图,K,n,(n,1),的点连通度为,n-1,；规定非连通图和平凡图的点连通度为,0,；,定义,设无向图,G=,是连通无向图,E,1,E,若,G,E,1,不连通，而对于,E,1,的任何一个非空真子集,E,2,，,G,E,2,是连通的，则称,E,1,是,G,的边割集。,在下图中,e,5,e,6,e,2,e,3,e,1,e,2,e,3,e,4,e,1,e,4,e,1,e,3,e,2,e,4,都是边割集,其中,e,5,和,e,6,是桥。,若某一条边构成一个边割集，则称该条边为割边或桥。,定义,设,G,为无向连通图且为非平凡图,则称,(G)=min|E,1,|E,1,为,G,的边割集,为,G,的边连通度。,规定,:,非连通图和平凡图的边连通度为,(G)=0,；完全图,K,n,(n,1),的边连通度,(K,n,)=n-1.,练习：,下图的点连通度为,，边连通度为,_,.,练习：,分别求出,n,阶完全无向图,K,n,的点连通度和边连通度。,解：,定理：,对于任何无向图,G,有,:,(G),(G),(G),。,例,(1),给出一些无向简单图,使得,:,=,=,；,无向完全图,K,n,和零图,N,n,都满足要求。,(a),(b),(2),给出一些无向简单图,使得,:,在两个,K,n,(n,4),之间放置一个顶点,v,使,v,与两个,K,n,中任意两个不同的顶点相邻,所得简单图满足要求。,(a),(b),