图论课件第三章 图的连通性.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论及其应用,应用数学学院,1,第三章 图的连通性,主要内容,一、割边、割点和块,二、图的连通度与敏格尔定理,三、图的宽直径简介,教学时数,安排,6,学时讲授本章内容,图的连通性刻画,2,本次课主要内容,(,一,),、割边及其性质,(,二,),、割点及其性质,(,三,),、块及其性质,割边、割点和块,3,研究图的连通性的意义,研究图的连通性，主要研究图的连通程度的刻画，其意义是：,图论意义：图的连通程度的高低，是图结构性质的重要表征，图的许多性质都与其相关，例如：连通图中任意两点间不相交路的条数就与图的连通程度有关。,实际意义：图的连通程度的高低，在与之对应的通信网络中，对应于网络“可靠性程度”的高低。,网络可靠性，是指网络运作的好坏程度，即指如计算机网络、通信网络等对某个组成部分崩溃的容忍程度。,网络可靠性，是用可靠性参数来描述的。参数主要分确定性参数与概率性参数。,4,确定性参数主要考虑网络在最坏情况下的可靠性度量，常称为网络拓扑的“容错性度量”，通常用图论概念给出，其中，本章将介绍的图的连通度就是网路确定性参数之一。近年来，人们又提出了“坚韧度”、“核度”、“整度”等描述网络容错性的参数。,概率性参数主要考虑网络中处理器与信关以随机的、彼此独立的按某种确定性概率损坏的情况下，网络的可靠性度量，常称为网络拓扑的“可靠性度量”。,(,一,),、割边及其性质,定义,1,边,e,为图,G,的一条割边，如果 。,红色边为该图的割边,5,注：割边又称为图的“桥”。,图的割边有如下性质：,定理,1,边,e,是图,G,的割边当且仅当,e,不在,G,的任何圈中。,证明：可以假设,G,连通。,若不然。设,e,在图,G,的某圈,C,中，且令,e=u v.,考虑,P=C-e,则,P,是一条,u v,路。下面证明,G-e,连通。,对任意,x,y V(G-e),由于,G,连通，所以存在,x-y,路,Q.,若,Q,不含,e,，则,x,与,y,在,G-e,里连通；若,Q,含有,e,，则可选择路：,x-u P v-y,说明,x,与,y,在,G-e,里也连通。所以,若边,e,在,G,的某圈中，则,G-e,连通。,但这与,e,是,G,的割边矛盾！,“必要性”,6,“充分性”,如果,e,不是,G,的割边，则,G-e,连通，于是在,G-e,中存在一条,u-v,路，显然：该路并上边,e,得到,G,中一个包含边,e,的圈，矛盾。,推论,1 e,为连通图,G,的一条边，如果,e,含于,G,的某圈中，则,G-e,连通。,证明：若不然，,G-e,不连通，于是,e,是割边。由定理,1,，,e,不在,G,的任意圈中，矛盾！,例,1,求证,:(1),若,G,的每个顶点的度数均为偶数，则,G,没有割边,;(2),若,G,为,k,正则二部图,(k,2),，则,G,无割边。,证明,:(1),若不然，设,e=,uv,为,G,的割边。则,G-e,的含有顶点,u,的那个分支中点,u,的度数为奇，而其余点的度数为偶数，与握手定理推论相矛盾！,7,(2),若不然，设,e=,uv,为,G,的割边。取,G-e,的其中一个分支,G,1,显然，,G,1,中只有一个顶点的度数是,k-1,其余点的度数为,k,。并且,G,1,仍然为偶图。,假若,G,1,的两个顶点子集包含的顶点数分别为,m,与,n,，并且包含,m,个顶点的顶点子集包含度为,k-1,的那个点，那么有：,k m-1=k n,。但是因,k,2,，所以等式不能成立！,注：该题可以直接证明,G,中任何一条边均在某一圈中，由定理,1,得出结论。,边割集简介,边割集跟回路、树等概念一样，是图论中重要概念。在应用上，它是电路网络图论的基本概念之一。所以，下面作简单介绍。,8,定义,2,一个具有,n,个顶点的连通图,G,定义,n-1,为该连通图的秩；具有,p,个分支的图的秩定义为,n-p,。记为,R(G),。,(1)R(G-S)=n-2;,定义,3,设,S,是连通图,G,的一个边子集，如果：,(2),对,S,的任一真子集,S,1,有,R(G-S,1,)=n-2,。,称,S,为,G,的一个边割集，简称,G,的一个边割。,例,2,边子集：,S,1,=,a,c,e,S,2,=,a,b,S,3,=,f,是否是下图,G,的边割？,a,g,e,d,c,b,h,f,i,图,G,9,解,:S,1,不是；,S,2,与,S,3,是。,定义,4,在,G,中，与顶点,v,关联的边的集合，称为,v,的关联集，记为：,S(v),。,a,g,e,d,c,b,h,f,i,图,G,例,3,关联集是割集吗？为什么？,答：不一定！如在下图中，关联集,a,c,e,是割集，但是，关联集,d,e,f,不是割集。,10,定义,5,在,G,中，如果,V=V,1,V,2,V,1,V,2,=,E,1,是,G,中端点分属于,V,1,与,V,2,的,G,的边子集，称,E,1,是,G,的一个断集。,a,g,e,d,cb,h,f,i,图,G,在上图,G,中：,d,e,f,e,d,f,等都是,G,的断集。一个图若按断集,S,来画，形式为：,S,11,注：割集、关联集是断集，但逆不一定。断集和关联集之间的关系为：,定理,2,任意一个断集均是若干关联集的环和。,定理,3,连通图,G,的断集的集合作成子图空间的一个子空间，其维数为,n-1,。该空间称为图的断集空间。,(,其基为,n-1,个线性无关的关联集,),例,4,求出下图,G,的所有断集。,e,d,c,b,a,f,1,2,3,4,12,解：容易知道：,S(1),S(2),S(3),是线性无关断集。,c,b,a,1,2,3,4,S(1),d,a,f,1,2,3S(2),e,c,f,1,2,3,4,S(3),d,c,b,f,1,2,3,4,e,b,a,f,1,2,3,4,13,e,d,c,a,1,2,3,4,e,d,b,1,2,3,4,上图形成的断集空间为：,定义,6,设,G,是连通图，,T,是,G,的一棵生成树。如果,G,的一个割集,S,恰好包含,T,的一条树枝，称,S,是,G,的对于,T,的一个基本割集。,14,例如：在图,G,中,f,e,d,c,b,a,图,G,G,的相对于,T,的基本割集为：,a,e,f,c,f,b,e,d.,关于基本割集，有如下重要结论：,定理,4,连通图,G,的断集均可表为,G,的对应于某生成树,T,的基本割集的环和。,15,定理,5,连通图,G,对应于某生成树,T,的基本割集的个数为,n-1,它们作成断集空间的一组基。,注：到目前为止，我们在子图空间基础上，先后引进了图的回路空间和断集空间，它们都是子图空间的子空间，这些概念，均是网路图论的基本概念，当然也是代数图论的基本概念。,(,二,),、割点及其性质,定义,7,在,G,中，如果,E(G),可以划分为两个非空子集,E,1,与,E,2,使,GE,1,和,GE,2,以点,v,为公共顶点，称,v,为,G,的一个割点。,16,在图,G,1,中，点,v,1,v,2,均是割点；在,G,2,中，,v,5,是割点。,v,1,v,2,v,3,v,4,e,3,e,1,e,2e,4,e,5,e,6,图,G,1,v,1,v,3,v,2,v,4,v,5,图,G,2,定理,6 G,无环且非平凡，则,v,是,G,的割点，当且仅当,证明：“必要性”,设,v,是,G,的割点。则,E(G),可划分为两个非空边子集,E,1,与,E,2,使,GE,1,GE,2,恰好以,v,为公共点。由于,G,没有环，所,17,以，,GE,1,GE,2,分别至少包含异于,v,的,G,的点，这样，,G-v,的分支数比,G,的分支数至少多,1,，所以：,“充分性”,由割点定义结论显然。,定理,7 v,是树,T,的顶点，则,v,是割点，当且仅当,v,是树的分支点。,证明：“必要性”,若不然，有,deg(v,)=1,即,v,是树叶，显然不能是割点。,“充分性”,设,v,是分支点，则,deg(v,)1.,于是设,x,与,y,是,v,的邻点，由树的性质，只有唯一路连接,x,与,y,，所以,G-v,分离,x,与,y.,即,v,为割点。,18,定理,8,设,v,是无环连通图,G,的一个顶点，则,v,是,G,的割点，当且仅当,V(G-v),可以划分为两个非空子集,V,1,与,V,2,使得对任意,x,V,1,y V,2,点,v,在每一条,x y,路上。,证明：“必要性”,v,是无环连通图,G,的割点，由定理,6,，,G-v,至少有两个连通分支。设其中一个连通分支顶点集合为,V,1,另外连通分支顶点集合为,V,2,即,V,1,与,V,2,构成,V,的划分。,“充分性”,对于任意的,x,V,1,y V,2,，如果点,v,不在某一条,xy,路上，那么，该路也是连接,G-v,中的,x,与,y,的路，这与,x,y,处于,G-v,的不同分支矛盾。,若,v,不是图,G,的割点，那么,G-v,连通，因此在,G-v,中存在,x,y,路，当然也是,G,中一条没有经过点,v,的,x,y,路。矛盾。,19,例,5,求证：无环非平凡连通图至少有两个非割点。,证明：由于,G,是无环非平凡连通图，所以存在非平凡生成树，而非平凡生成树至少两片树叶，它不能为割点，所以，它也不能为,G,的割点。,证明：设,T,是,G,的一棵生成树。由于,G,有,n-2,个割点，所以，,T,有,n-2,个割点，即,T,只有两片树叶，所以,T,是一条路。这说明，,G,的任意生成树为路。,例,6,求证：恰有两个非割点的连通单图是一条路。,一个单图的任意生成树为路，则该图为圈或路，若为圈，则,G,没有割点，矛盾，所以，,G,为路。,例,7,求证：若,v,是单图,G,的割点，则它不是,G,的补图的割点。,20,证明：,v,是单图,G,的割点，则,G-v,至少两个连通分支。现任取,如果,x,y,在,G-v,的同一分支中，令,u,是与,x,y,处于不同分支的点，那么，通过,u,，可说明，,x,与,y,在,G-v,的补图中连通。若,x,y,在,G-v,的不同分支中，则它们在,G-v,的补图中邻接。所以，若,v,是,G,的割点，则,v,不是其补图的割点。,(,三,),、块及其性质,定义,8,没有割点的连通图称为是一个块图，简称块；,G,的一个子图,B,称为是,G,的一个块，如果,(1),它本身是块；,(2),若没有真包含,B,的,G,的块存在。,例,7,找出下图,G,中的所有块。,21,解：由块的定义得：,图,G,22,定理,9,若,|V(G)|,3,则,G,是块，当且仅当,G,无环且任意两顶点位于同一圈上。,证明：,(,必要性）设,G,是块。因,G,没有割点，所以，它不能有环。对任意,u,v,V(G),下面证明,u,v,位于某一圈上。,对,d(u,v),作数学归纳法证明。,当,d(u,v)=1,时，由于,G,是至少,3,个点的块，所以，边,uv,不能为割边，否则，,u,或,v,为割点，矛盾。由割边性质，,uv,必然在某圈中。,设当,d(u,v)k,时结论成立。,设当,d(u,v)=k,。,设,P,是一条最短,(u,v),路，,w,是,v,前面一点，则,d(u,v)=k-1,23,由归纳假设，,u,与,w,在同一圈,C=P,1,P,2,上。,u,w,v,P,P,2,P,1,考虑,G-w.,由于,G,是块，所以,G-w,连通。设,Q,是一条在,G-w,中的,(u,v),路，并且设它与,C,的最后一个交点为,x,。,u,w,v,QP,2,P,1,x,24,则,uP,1,xvwP,2,为包含,u,v,的圈。,(,充分性,),：若,G,不是块，所以,G,中有割点,v,。由于,G,无环，所以,G-v,至少两个分支。设,x,y,是,G-v,的两个不同分支中的点，则,x,y,在,G,中不能位于同一圈上，矛盾！,定理,10,点,v,是图,G,的割点当且仅当,v,至少属于,G,的两个不同的块。,证明：,(,必要性,),设,v,是,G,的割点。由割点定义：,E(G),可以划分为两个边子集,E,1,与,E,2,。显然,GE,1,与,GE,2,有唯一公共顶点,v,。设,B,1,与,B,2,分别是,GE,1,和,GE,2,中包含,v,的块显然它们也是,G,的块。即证明,v,至少属于,G,的两个不同块。,(,充分性,),如果,v,属于,G,的两个不同块，我们证明：,v,一定是图,G,的割点。,25,如果包含,v,的其中一个块是环，显然,v,是割点；,设包含,v,的两个块是,B,1,与,B,2,。如果包含,v,的两个块不是环，那么两个块分别至少有两个顶点。假如,v,不是割点，在,B,1,与,B,2,中分别找异于,v,的一个点,x,与,y,x,V(B,1,),y V(B,2,),则在,G-v,中有连接,x,与,y,的路,P,。,显然：,B,1,B,2,P,无割点。这与,B,1,B,2,是块矛盾！,注：该定理揭示了图中的块与图中割点的内在联系：不同块的公共点一定是图的割点。也就是说，图的块可以按割点进行寻找。所以，该定理的意义在于：可以得到寻找图中全部块的算法。,为了直观反映图的块和割点之间的联系，引进所谓的块割点树。,26,设,G,是非平凡连通图。,B,1,B,2,B,k,是,G,的全部块，而,v,1,v,2,v,t,是,G,的全部割点。构作,G,的块割点树,bc(G,):,它的顶点是,G,的块和割点，连线只在块割点之间进行，一个块和一个割点连线，当且仅当该割点是该块的一个顶点。,例,8,画下图,G,中的块割点树。,1,2,5,4,3,6,B,3,B,2,B,1,B,5,B,4,B,6,B,7,G,B,7,B,6,B,5,B,4,B,3,B,2,B,1,5,4,3,2,1,6,b,c(G,),27,作业,P65-66,习题,3,：,1,2,3,5,7,8,28,Thank You!,29,