资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,河南工业大学离散数学课程组,7-2,路与回路,右图是中国铁路交通图的一部分，如果一个旅客要从成都乘火车到北京，那么他一定会经过其它车站；而旅客不可能从成都乘火车到达台北。这就引出了图的通路与连通的概念。,成都,昆明,重庆,广州,长沙,武汉,上海,兰州,西安,沈阳,北京,天津,郑州,厦门,高雄,台北,1,7-2,路与回路,知识点：,路、回路定义及相关定理,连通图、连通分支,割点、点割集,割边、边割集,点连通度、边连通度,有向图的连通性、各种分图,通路与回路是图论中两个重要的基本概念。本小节所述定义一般来说既适合有向图，也适合无向图，否则，将加以说明或分开定义。,2,一、相关概念,定义,7-2.1,路(,walk),：,结点与边的交替序列,其中,路长度：边的数目。,结点数=边数+1,3,回路(,closed walk),回路：,结点数=边数,4,特殊路：迹、通路、圈的定义,迹：,没有重复,边,的路。,通路：,没有重复,结点,的路。,（当然此时所有边也不相同）,圈：,封闭的,通路。,5,结点重复情况,边重复情况,路,(Walks),允许,允许,迹,(Trails),允许,不允许,通路,(Paths),不允许,不允许,回路,(Circuits),允许,允许,圈,(cycle),不允许（除始点和终点外）,不允许,6,说明,通路一定是迹,，但反之不真。因为没有重复的结点肯定没有重复的边，但没有重复的边不能保证一定没有重复的结点。,路的表示：,结点与边的交替序列，如,v,0,e,1,v,1,e,2,v,2,e,n,v,n,在不会引起误解的情况下，,路也可以用边的序列,e,1,e,2,e,n,表示，这种表示方法对于有向图来说较为方便。,路也可以用结点的序列,v,0,v,1,v,2,v,n,来表示。,混合表示：,当只用结点序列表示不出某些路(回路)时，可在结点序列中加入一些边。,7,v,3,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,v4,v,2,v,1,v,1,e,2,v,3,e,3,v,2,e,6,v,5,e,7,v,3,e,4,v,2,e,3,v,3,e,4,v,2,是从,v,1,到,v,2,的,路,，,v,1,是起点，,v,2,是终点，长度为,7,。,e,2,e,3,e,6,e,7,e,4,e,3,e,4,从,v,1,到,v,2,的,路,特殊路：迹、通路、圈,v,3,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,v4,v,2,v,1,从,v,1,到,v,2,的,迹,v,1,e,2,v,3,e,3,v,2,e,6,v,5,e,7,v,3,e,4,v,2,是从,v,1,到,v,2,的,迹,，,v,1,是起点，,v,2,是终点，长度为,5,。,e,2,e,3,e,6,e,7,e,4,8,v,3,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,v4,v,2,v,1,v,1,e,2,v,3,e,3,v,2,是从,v,1,到,v,2,的,通路,，,v,1,是起点，,v,2,是终点，长度为,2,。,e,2,e,3,从,v,1,到,v,2,的,通路,特殊路：迹、通路、圈,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,从,v,2,到,v,2,的一条,圈,v,2,e,1,v,1,e,2,v,3,e,7,v,5,e,6,v,2,是从,v,2,到,v,2,的一条,圈,，长度为,4,。,e,1,e,2,e,7,e,6,9,C,3,圈(,cycles),C,1,C,2,C,4,C,5,长为1的圈只由,环,生成。,长为2的圈只由,平行边,生成。,在,简单无向图中,，圈的,长度至少为3,。,将长度为奇数的圈称为,奇圈,。,长度为偶数的圈称为,偶圈,。,画出的长度为,n,的圈，若不指定起点和终点，则在同构意义下是唯一的，若指定起点，终点，则是,n,个不同构的圈,。,10,路相关定理,定理,7-2.1,在,n,阶图,G,中，若从不同结点,v,j,到,v,k,存在路，则从,v,j,到,v,k,存在长度小于等于,n-1,的路。,分析：,路的长度等于路中的结点数减,1,，如果结点,不重复,，最多,n,个，因此路长度最多,n-1,；,如果结点有,重复,，则在重复的结点间构成一条回路，删除这条回路，剩下的仍然是从结点,v,i,到结点,v,j,的路。一直删下去，直到无重复结点为止，定理得证。,v,1,v,2,v,5,v,1,v,4,v,3,v,2,v,5,v,1,v,4,v,3,v,2,路：,v,1,v,2,v,3,v,4,v,2,v,5,，长度,5,路：,v,1,v,2,v,5,，长度,2,v,1,v,2,v,3,v,2,v,3,v,4,v,1,v,2,v,3,v,4,11,证明,：设该路,=,v,j,v,i,v,k,为,G,中一条长度为,p,的路，显然该路上的结点数为,p,+1,。,若,p,n-1,，则该路满足要求，,否则必有,p,n-1,，对应的结点数,p,+1n-1+1=n,，即该路上的结点数,p,+1,大于,G,中的结点数,n,，于是必存在结点,v,s,，在该路中重复出现，即必有结点序列,v,j,v,i,v,s,v,s,v,k,，即在该路上存在,v,s,到自身的回路，在路上删除,v,s,到,v,s,的一切边,及,除,v,s,外的一切结点,，,仍为,v,j,到,v,k,的路，且长度减少。重复上述过程，由于,G,是有限图，经过有限步后，必然使该路中所有点均不相同，必得到,v,j,到,v,k,长度小于或等于,n-1,的路。,定理,7-2.1,在,n,阶图,G,中，若从不同结点,v,j,到,v,k,存在路，则从,v,j,到,v,k,存在长度小于等于,n-1,的路。,12,定理,7-2.1,推论,推论,1,：,在,n,阶图,G,中，若从不同结点,v,j,到,v,k,有路，则从,v,j,到,v,k,有长度小于等于,n-1,的通路。,证明：若路不是通路，则路上有重复结点，删除所有重复结点之间的回路，得到的是通路，其长度小于等于,n-1,。,推论,2,：,在一个具有,n,个结点的图中，如果存在经过结点,v,i,回路（圈），则存在一条经过,v,i,的长度不大于,n,的回路（圈）。,13,图的连通性,无向图的连通性,有向图的连通性,14,二、无向图的连通(,connected),定义7-2.2,连通,(,connected),：无向图,G=,中，若结点,u,和,v,间有路，则称,u,和,v,是连通的,。,对于所有,v,V,，规定结点到自身是连通的。,说明：,1、由定义不难看出，无向图中结点之间的连通关系是自反的，对称的，传递的，因而结点间的连通关系是,V,上的等价关系。,15,说明,2,：由连通性是等价关系可以划分等价类,设无向图,G=,，结点之间连通关系,R,是结点集,V,上的等价关系，在此等价关系下，集合,V(G),必分成一些等价类，由每个,等价类,导出的子图,都称为,G,的一个,连通分支,，用,W(G),表示,G,中的连通分支个数。,G,W(G)=3,每一个连通分支中任何两个结点是连通的，而位于不同连通分支中的任何两个结点是不连通的。每个结点和边仅能位于一个连通分支中。,16,定义,7-2.3,若图,G,只有一个连通分支，则称,G,为,连通图,，否则称,G,是非连通图或分离图。,实质：若无向图,G,是,平凡图,或,G,中任何两个结点都是,连通,的，则称,G,为,连通图,，否则称,G,是,非连通图,或,分离图,。,易知，,G,为连通图充要条件,W(G)=1,，,G,为非连通图充要条件,W(G)2,，,平凡图是连通图,，完全图,Kn(n1),都是连通图，,而,零图,Nn(n2),都是分离图。,在所有的,n,阶无向图中，,n,阶零图是连通分支最多的，,W(Nn,)=n,。,连通图定义,17,判断下图中图,G,1,和,G,2,的连通性，并求其连通分支个数。,分析,本题中图很简单，并且给出了图形，很容易看出,G,1,是连通图，,G,2,是非连通图。容易看出，,G,2,中可达关系的等价类为,v,1,v,2,，,v,3,v,4,，它们导出的子图即为,G,2,的,2,个连通分支。,解,在上图中，,G,1,是连通图，所以,W(G,1,)=1,。,G,2,是非连通图，且,W(G,2,)=2,。,v,1,v,2,v,3,v,4,e1,e,2,e3,v,2,v,3,v,4,e1,e,2,v,1,G,1,G,2,18,割集,例如：一份地图记载了,n,座城市的分布图和联络图，某些城市之间修筑了公路，任意两个城市都可以通过公路直接或间接到达，发现有些公路被损坏之后会造成某些城市之间无法通过公路相互达到，只要破坏这样的公路，就可以破坏整个城市之间的交通。,例如：城市间的通信问题，破坏某些城市就会造成通信的瘫痪。,u,e,割集在图论中是个重要概念,在图论的理论和应用中,都具有重要地位。割集就是使得原来连通的图,变成不连通，需要删去的结点集合或边的集合。,点割集,边割集,19,（一）点割集和割点,定义7-2.4,设无向图,G=,为连通图，若存在,（,1,）结点集,V,的,非空结点真子集,V,1，,即,V,1,V,，且,V,1,，,（,2,）使得图,G,删除了,V,1,的所有结点,后，得到的子图是非连通图，,（,3,）而,删除,了,V,1,的,任何真子集,后，所得到的子图仍为,连通图,，则称,V,1,是,G,的,点割集。,若,V,1,是单元素集，即,V,1,=v,，则称,v,为,割点,。,20,点割集：,v,3,v,5,v,2,，,v,4,割点：,v,3,，,v,5,点割集举例,v,1,v,2,v,3,v,4,v,5,v,6,e,1,e2,e,3,e,5,e,4,e,6,点割集和割点,21,点连通度(,vertex-connectivity,),为了破坏连通性，,至少,需要删除多少个结点,?,点连通度：,G,是无向连通非完全图,(,G)=min|V|V,是,G,的点割集,即,产生一个不连通图需删去的结点的最小数目,。,规定：,(,K,n,)=n-1,非连通图,G,：(,G)=0,(,G),|V(G)|-1,22,点连通度例,G,H,F,(,G)=1,(,H)=2,(,F)=3,(,K,5,)=4,由图知：点连通度越大，点连通程度越高。,23,（二）边割集和割边,定义7-2.5,设无向图,G=,为连通图，,（,1,）若存在边集,E,的,非空边真子集,E,1，,即边集,E,1,E,，且,E,1,，,（,2,）使得图,G,删除了,E,1,的所有边后，得到的子图是不连通图,，,（,3,）而删除了,E,1,的任何真子集后，所得到的子图仍为连通图,，则称,E,1,是,G,的,边割集,。,若,E,1,是单元素集，即,E,1,=e,，则称,e,为,割边,（或,桥,）。,24,边割集举例,e,6,e,5,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,6,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,25,边连通度(,edge-connectivity),为了破坏连通性，至少需要删除多少条边,?,边连通度：,G,是无向连通图,(,G)=min|E|E,是,G,的边割集,即,产生一个不连通图需删去的边的最小数目,。,规定：,G,非连通：(,G)=0,(,K,n,)=n-1,26,边连通度例,(,G)=1,(,H)=2,(,F)=3,(,K,5,)=4,G,H,F,边连通度越大，边连通程度越高。,27,下图,的无向连通图中，,最小度,(G)=3,点连通度,(G,)=1,边连通度,(G)=2,k(,G,),(,G,),(,G,),。,Whitney,定
展开阅读全文