离散数学--6.2-3图的连通性.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,6.2,图的连通性,6.2.1 通路与回路,初级通路(回路)与简单通路(回路),6.2.2 无向图的连通性与连通度,连通图、连通分支,短程线与距离,点割集、割点、边割集、割边(桥),点连通度与边连通度,1,6.2,图的连通性(续),6.2.3 有向图的连通性及其分类,可达性,弱连通、单向连通、强连通,短程线与距离,2,通路与回路,定义6.13,给定图,G,=(,无向或有向的),G,中顶点与边,的交替序列,=,v,0,e,1,v,1,e,2,e,l,v,l,.,若,i,(1,i,l,),e,i,=,(,v,i,1,v,i,)(对于有向图,e,i,=,),则称,为,v,0,到,v,l,的,通路,v,0,和,v,l,分别为通路的,起点,和,终点,l,为,通路的,长度,.又若,v,0,=,v,l,则称,为,回路,.,若通路(回路)中所有顶点(对于回路,除,v,0,=,v,l,),各异,则称为,初级通路,或,路径(初级回路,或,圈),.长度为奇数的圈称作,奇,圈,长度为偶数的圈称作,偶圈,若通路(回路)中所有边各异,则称为,简单通路(简单回路),否则称为,复杂通路(复杂回路),3,说明,(1)表示方法,按定义用顶点和边的交替序列,=,v,0,e,1,v,1,e,2,e,l,v,l,用边序列,=,e,1,e,2,e,l,简单图中,用顶点序列,=,v,0,v,1,v,l,(2)在无向图中,长度为1的圈由环构成,.,长度为2的圈由两,条平行边构成.在无向简单图中,所有圈的长度,3.,在有向图中,长度为1的圈由环构成.在有向简单图中,所,有圈的长度,2.,4,说明(续),(3)初级通路(回路)是简单通路(回路),但反之不真,初级通路,非初级的简单通路,初级回路,非初级的,简单回路,5,通路与回路(续),定理6.3,在,n,阶图中,若从顶点,u,到,v,(,u,v,),存在通路,则从,u,到,v,存在长度小于等于,n,1,的初级通路.,证 若通路中没有相同的顶点(即初级通路),长度必,n,1.,若有相同的顶点,删去这两个顶点之间的这一段,仍是,u,到,v,的通路.重复进行,直到没有相同的顶点为止.,定理6.4,在,n,阶图中,若存在,v,到自身的简单回路,则一定存,在,v,到自身长度小于等于,n,的初级回路.,6,无向图的连通性与连通分支,设无向图,G,=,u,v,V,u,与,v,连通,:若,u,与,v,之间有通路.规定,u,与自身总是连通的.,连通图,:任意两点都连通的图.平凡图是连通图,连通关系,R,=|,u,v,V,且,u,与,v,连通.,R,是等价关系,连通分支,:,V,关于,R,的等价类的导出子图,设,V,/,R,=,V,1,V,2,V,k,G,的连通分支为,G,V,1,G,V,2,G,V,k,连通分支数,p,(,G,)=,k,G,是连通图,p,(,G,)=1,7,短程线与距离,u,与,v,之间的短程线,:,u,与,v,之间长度最短的通路(设,u,与,v,连通),u,与,v,之间的距离,d,(,u,v,),:,u,与,v,之间短程线的长度,若,u,与,v,不连通,规定,d,(,u,v,),=,.,性质：,(1),d,(,u,v,),0,且,d,(,u,v,),=,0,u=v,(2),d,(,u,v,)=,d,(,v,u,),(3),d,(,u,v,)+,d,(,v,w,),d,(,u,w,),例如,a,与,e,之间的短程线:,ace,afe,.,d,(,a,e,)=2,d,(,a,h,)=,a,b,c,d,e,f,g,h,i,8,点割集与边割集,设无向图,G,=,v,V,e,E,V,V,E,E.,记,G,v,:,从,G,中删除,v,及关联的边,G,V,:,从,G,中删除,V,中所有的顶点及关联的边,G,e,:,从,G,中删除,e,G,E,:,从,G,中删除,E,中所有边,定义6.15,设无向图,G,=,V,V,若,p,(,G,V,),p,(,G,),且,V,V,p,(,G,V,)=,p,(,G,),则称,V,为,G,的,点割集,.若,v,为点割,集,则称,v,为,割点,.,设,E,E,若,p,(,G,E,),p,(,G,),且,E,E,p,(,G,E,)=,p,(,G,),则称,E,为,G,的,边割集,.若,e,为边割集,则称,e,为,割边,或,桥,.,9,实例,说明：,K,n,无点割集,n,阶零图既无点割集，也无边割集.,若,G,连通，,E,为边割集，则,p,(,G,E,)=2,若,G,连通，,V,为点割集，则,p,(,G,V,),2,a,b,c,d,e,f,g,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,e,9,e,f,点割集:,e,f,割点:,c,d,桥:,e,8,e,9,边割集:,e,8,e,9,e,1,e,2,e,1,e,3,e,6,e,1,e,3,e,4,e,7,10,点连通度与边连通度,定义6.16,设无向连通图,G,=,(,G,)=,min|,V,|,V,是,G,的点割集或使,G,-,V,成为平凡图,称为,G,的,点连通度,(,G,)=,min|,E,|,E,是,G,的边割集,称为,G,的,边连通度,例如,3,(,G,)=,3,(,G,),=,11,点连通度与边连通度(续),说明:,(1)若,G,是平凡图,则,(,G,)=0,(,G,)=0.,(2)若,G,是完全图,K,n,则,(,G,),=,n,-1,(,G,)=,n,-1,(3)若,G,中存在割点,则,(,G,),=1;若,G,中存在割边,则,(,G,)=1,(4)规定非连通图的点连通度和边连通度均为0,定理6.5,对任何无向图,G,有,(,G,),(,G,),(,G,),12,有向图的连通性及其分类,设有向图,D,=,u,v,V,u,可达,v,:,u,到,v,有通路.规定,u,到自身总是可达的.,u,与,v,相互可达,:,u,可达,v,且,v,可达,u,D,弱连通(连通),:略去各边的方向所得无向图为连通图,D,单向连通,:,u,v,V,，,u,可达,v,或,v,可达,u,D,强连通,:,u,v,V,，,u,与,v,相互可达,D,是强连通的当且仅当,D,中存在经过所有顶点的回路,D,是单向连通的当且仅当,D,中存在经过所有顶点的通路,13,实例,强连通,单连通,弱连通,14,有向图中的短程线与距离,u,到,v,的短程线,:,u,到,v,长度最短的通路(设,u,可达,v,),距离,d,:,u,到,v,的短程线的长度,若,u,不可达,v,规定,d,=,.,性质：,d,0,且,d,=,0,u=v,d,+,d,d,注意:没有对称性,15,6.3,图的矩阵表示,6.3.1 无向图的关联矩阵,6.3.2 有向无环图的关联矩阵,6.3.3 有向图的邻接矩阵,有向图中的通路数与回路数,6.3.4 有向图的可达矩阵,16,无向图的关联矩阵,设无向图,G,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,.,令,m,ij,为,v,i,与,e,j,的关联次数,称(,m,ij,),n,m,为,G,的关联矩阵,记为,M,(,G,).,m,ij,的可能取值为:0,1,2,例如,e,1,e,2,e,3,e,4,e,5,e,6,v,5,v,1,v,2,v,3,v,4,M,(,G,)=,2 1 1 0 0 0,0 1 0 1 1 1,0 0 0 0 1 1,0 0 0 0 0 0,0 0 1 1 0 0,17,关联矩阵的性质,(6),e,j,是环,第,j,列的一个元素为2,其余为0,(5),v,i,是孤立点,第,i,行全为0,18,无环有向图的关联矩阵,则称(,m,ij,),n,m,为,D,的关联矩阵,记为,M,(,D,).,设无环有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,.,令,(3),e,j,与,e,k,是平行边,第,j,列与第,k,列相同,(2)第,i,行1的个数等于,d,+,(,v,),第,i,行-1的个数等于,d,-,(,v,),性质:,(1),每列恰好有一个,1,和一个,-1,19,实例,v,1,v,2,v,3,v,4,e,2,e,1,e,3,e,4,e,5,e,6,e,7,M,(,D,)=,-1 1 0 0 0 1 1,0 -1 1 0 0 0 0,0 0 -1 -1 -1 1 -1,1 0 0 1 1 0 0,20,有向图的邻接矩阵,设有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,令,为顶点,v,i,邻接到顶点,v,j,边的条数，称(),m,n,为,D,的邻接矩阵,记作,A,(,D,),简记作,A.,21,实例,A,=,1 1 0 0,0 0 1 0,1 0 0 0,1 0 2 0,v,1,v,2,v,3,v,4,22,有向图中的通路数与回路数,定理6.6,设,A,为,n,阶有向图,D,的邻接矩阵,则,A,l,(,l,1),中元素,等于,D,中,v,i,到,v,j,长度为,l,的通路(含回路)数,等于,v,i,到自身长,度为,l,的回路数,等于,D,中长度为,l,的通路(含回路),总数,等于,D,中长度为,l,的回路总数.,23,有向图中的通路数与回路数(续),推论,设,B,l,=,A,+,A,2,+,A,l,(,l,1),则,B,l,中元素 等于,D,中,v,i,到,v,j,长度小于等于,l,的通路(含回路)数,等于,D,中,v,i,到,v,i,长度,小于等于,l,的回路数,等于,D,中长度小于等于,l,的,通路(含回路)数,为,D,中长度小于等于,l,的回路数.,24,实例(续),说明:在这里,通路和回路数是定义意义下的,A,=,1 1 0 0,0 0 1 0,1 0 0 0,1 0 2 0,A,2,=,1 1 1 0,1 0 0 0,1 1 0 0,3 1 0 0,A,3,=,2 1 1 0,1 1 0 0,1 1 0 0,3 3 1 0,A,4,=,3 2 1 0,1 1 0 0,2 1 1 0,4 3 1 0,v,1,到,v,2,长为3的通路有1条,v,1,到,v,3,长为3的通路有1条,v,1,到,自身长为3的回路有2条,D,中长为3的通路共有15条,其中回路3条,v,1,v,2,v,3,v,4,25,有向图的可达矩阵,性质:,P,(,D,),主对角线上的元素全为1.,D,强连通当且仅当,P,(,D,),的元素全为1.,设有向图,D,=,V,=,v,1,v,2,v,n,令,称(,p,ij,),n,n,为,D,的可达矩阵,记作,P,(,D,),简记为,P,.,26,实例,例1,(1),v,1,到,v,4,v,4,到,v,1,长为3的通路各有多少条?,(2),v,1,到自身长为1,2,3,4的回路各有多少条?,(3)长为4的通路共有多少条?其中有多少条回路?,(4)长度小于等于4的回路共有多少条?,(5)写出,D,的可达矩阵,并问,D,是强连通的吗?,解,v,1,v,2,v,3,v,4,A,=,1 2 1 0,0 0 1 0,0 0 0 1,0 0 1 0,27,实例(续),v,1,到,v,4,长为3的通路有 条,A,2,=,1 2 3 1,0 0 0 1,0 0 1 0,0 0 0 1,A,3,=,1 2 4 3,0 0 1 0,0 0 0 1,0 0 1 0,A,4,=,1 2 6 4,0 0 0 1,0 0 1 0,0 0 0 1,3,v,4,到,v,1,长为3的通路有 条,0,v,1,到自身长为1,2,3,4的回路各有 条,1,长为4的通路共有 条,其中有 条回路,16,3,长度小于等于4的回路共有 条,8,可达矩阵,非强连通,单连通,P,=,1 1 1 1,0 1 1 1,0 0 1 1,0 0 1 1,28,