离散数学--回路与图的连通性PPT参考课件.ppt

,单击此处编辑母版标题样式,2,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,离 散 数 学,1,2025/9/5 周五,2,7.2,通路、回路与图的连通性,简单通,(,回,),路,初级通,(,回,),路,复杂通,(,回,),路,连通图,连通分支,弱连通图,单向连通图,强连通图,点割集与割点,边割集与割边,(,桥,),2025/9/5 周五,3,在图中，一条通路是顶点和边的交替序列，以顶点,开始，以顶点结束。其中，第一条边的终点与第二,条边的始点重合,.,。第一条边的始点称为通路的,始点，最后一条边的终点称为通路的终点。,当通路的终点和始点重合时，称为回路。,通路或回路中所含边数称为该通路或回路的长度。,一、通路和回路,2025/9/5 周五,4,1,、简单通路：如果通路中各边都不相同。,如简单通路：,v,1,v,2,v,5,v,6,v,2,v,3,v,4,长度为,6,如简单回路：,v,1,v,2,v,3,v,5,v,2,v,6,v,1,长度为,6,2,、简单回路：如果回路中各边都不相同。,2025/9/5 周五,5,3,、基本通路：如果通路中各个顶点和边都不相同。,4,、基本回路,(,圈,),：如果回路中各个顶点和边都不相同。,如基本通路：,v,1,v,6,v,3,v,4,长度为,3,如基本回路：,v,1,v,6,v,3,v,2,v,1,显然，基本通路（回路）一定是简单通路（回路）。,反之不然。,2025/9/5 周五,6,若通路,(,回路,),中有边重复出现,则称为,复杂通路,(,回路,),.,2025/9/5 周五,7,关于通路与回路的几点说明,表示方法,用顶点和边的交替序列,(,定义,),如,=,v,0,e,1,v,1,e,2,e,l,v,l,用边的序列,如,=,e,1,e,2,e,l,简单图中,用顶点的序列,如,=,v,0,v,1,v,l,非简单图中,可用混合表示法,如,=,v,0,v,1,e,2,v,2,e,5,v,3,v,4,v,5,环是长度为,1,的圈,两条平行边构成长度为,2,的圈,.,2025/9/5 周五,8,在图,G,中，如果,A,到,B,存在一条通路，则称,A,到,B,是可达的。,1,、无向图的连通性,如果无向图中，任意两点是可达的，图为连通图。否则为,不连通图。,当图是不连通时，定是由几个连通子图构成。称这样的连,通图是连通分支。,二、图的连通性：,2025/9/5 周五,9,无向图的连通性,设无向图,G,=,u,与,v,连通,:,若,u,与,v,之间有通路,.,规定,u,与自身总连通,.,连通关系,R,=|,u,v,V,且,u,v,是,V,上的等价关系,连通图,:,平凡图,任意两点都连通的图,连通分支,:,V,关于,R,的等价类的导出子图,设,V,/,R,=,V,1,V,2,V,k,G,V,1,G,V,2,G,V,k,是,G,的连通分支,其个数记作,p,(,G,)=,k.,G,是连通图,p,(,G,)=1,若,G,为非连通图，则,P(G)2,在所有的,n,阶无向图中，,n,阶零图是连通分支最多的其分支数为,n.,2025/9/5 周五,10,设,A,=1,2,8,R,=|,x,y,A,x,y,(mod 3),即,:A,上模,3,等价关系的关系图为,:,上述关系图被分成三个互不连通的部分，每部,分中的数两两都有关系，不同部分的图无关系。,2025/9/5 周五,11,【,例,】,求证：若图中只有两个奇度数顶点，则二顶点必连通。,证明 用反证法来证明。,设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为,G,的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。,2025/9/5 周五,12,【,例,】,在一次国际会议中，由七人组成的小组,a,b,c,d,e,f,g,中，,a,会英语、阿拉伯语；,b,会英语、西班牙语；,c,会汉语、俄语；,d,会日语、西班牙语；,e,会德语、汉语和法语；,f,会日语、俄语；,g,会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？,2025/9/5 周五,13,解 用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到下图。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于下图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。,2025/9/5 周五,14,定理,在,n,阶简单图,G,如果对,G,的,每对顶点,u,和,v,deg(u)+deg(v),n,1,则,G,是连通图。,证明,假设,G,不连通,则,G,至少有两个分图,。,设其中一个分图含有,q,个顶点,而其余各分图共含有,n q,个顶点。,在这两部分中各取一个顶点,u,和,v,则,0,deg(u)q 1,0deg(v)n q 1,因此,deg(u)+deg(v)n 2,这与题设,deg(u)+deg(v)n 1,矛盾。,2025/9/5 周五,15,无向图的短程线与距离,u,与,v,之间的短程线,:,u,与,v,之间长度最短的通路,(,u,与,v,连通,),u,与,v,之间的距离,d,(,u,v,),:,u,与,v,之间短程线的长度,若,u,与,v,不连通,规定,d,(,u,v,),=,.,性质：,d,(,u,v,),0,且,d,(,u,v,),=,0,u=v,d,(,u,v,)=,d,(,v,u,),d,(,u,v,)+,d,(,v,w,),d,(,u,w,),2025/9/5 周五,16,在实际问题中,除了考察一个图是否连通外,往往还要研究一个图,连通的程度,作为某些系统的,可靠性度量,。,图的连通性在计算机网、通信网和电力网等方面有着重要的应用。,图的连通性的应用,2025/9/5 周五,17,2,、有向图的连通性,对于有向图，“图中任意两点都有通路相连”，,这个要求很高，因为有向图虽然是连在一起的，,但受到边的方向的限制，任意两点不一定有通路。,以下分三种情况讨论：,2025/9/5 周五,18,1,）强连通图：有向图中，任意,A,、,B,是互为可达的。如图,(a),2,）单向连通图：在有向图中，任意两点,A,、,B,存在着,A,到,B,的通路,或存在着,B,到,A,的通路。如图,(b),3,）弱连通图：在有向图中，如果其底图是无向连通图。如图,(c),显然：在有向图中，如果有一条通过图中所有点的回路，,则此图是强连通的。如果有一条通过图中所有点的通路，,则此图是单向连通图。,(a)(b)(c),2025/9/5 周五,19,单向连通图都是弱连通图，但弱连通图,却不一定是单向连通图。,在弱连通图中，存在这样的顶点,A,、,B,，,从,A,到,B,不可达，且从,B,到,A,也不可达。,强连通图既是单向连通图，又是弱连通图。,即,强连通,单向连通,弱连通,2025/9/5 周五,20,有向图的连通性,(,续,),定理,(,强连通判别法,),D,强连通当且仅当,D,中存在经过每个顶点至少一次的回路,定理,(,单向连通判别法,),D,单向连通当且仅当,D,中存在经过每个顶点至少一次的通路,(1),(2),(3),例 下图,(1),强连通,(2),单连通,(3),弱连通,2025/9/5 周五,21,思考：判断下列图中哪些是强连通图，哪些是单向连通图，哪些 是弱连通图。,(a),(b),(d),(c),答案,:,(a),(d),是强连通图,(b),是单向连通图,(c),是弱连通图,.,2025/9/5 周五,22,有向图的,短程线与距离,u,到,v,的短程线,:,u,到,v,长度最短的通路,(,u,可达,v,),u,与,v,之间的距离,d,:,u,到,v,的短程线的长度,若,u,不可达,v,规定,d,=,.,性质：,d,0,且,d,=,0,u=v,d,+,d,d,注意,:,没有对称性,2025/9/5 周五,23,7.7,设,n,阶无向简单图,G,中 ，,问 应为多少？,解：由于 ，说明,G,中任何顶点,v,的度数,而由于,G,为简单图，于是,则有 ，因此,说明,G,中每个顶点的度数都为,n-1,于是有,说明,G,为,n-1,阶正则图，即,G,为,n,阶完全图。,2025/9/5 周五,24,7.8,一个,n,(,n,2),阶无向简单图,G,中，,n,为奇数，,已知,G,中的,r,个奇数度顶点，问,G,的补图 有几个,奇数度顶点？,解：由于,而,n,为奇数，于是,K,n,中各顶点的度数,n,-1,为偶数，,对于,，应有 ，且,由于,n,-1,为偶数，所以 同为奇数或,同为偶数。,因此,G,中的,r,个奇数度顶点，则 也有,r,个,奇数度顶点。,2025/9/5 周五,25,7.9,设,D,是,n,阶有向简单图，是,D,的子图，已知,的边数为 ，问,D,的边数,m,为多少？,解：由于,所以,而,n,阶有向简单图中，边数,于是,说明,D,为,n,阶有向完全图，且,2025/9/5 周五,