第一章-图的基本概念2-图论及其应用.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Email:,图论及其应用,任课教师：杨春,1,第一章 图的基本概念,本次课主要内容,子图、图运算、路与连通性,(,一,),、子图的相关概念,(,三,),、路与连通性,(,二,),、图运算,2,1,、子图,简单地说，图,G,的任意一部分,(,包括本身,),都称为是图,G,的,的一个子图。,定义,1,如果,(,一,),、子图的相关概念,且,H,中边的重数不超过,G,中对应边的条数，则称,H,为,G,的子图，记为,当 时，称,H,是,G,的真子图，记为,3,2,、点与边的导出子图,(1),图,G,的顶点导出子图,定义,2,如果 ，则以 为顶点集，,以两个端点均在 中的边集组成的图，称为,图,G,的点导出子图。记为：,例,1,如图所示，求 。其中,1,2,3,4,5,图,G,4,解：由边导出子图的定义得：,1,2,3,4,5,图,G,1,2,3,4,5,6,3,、图的生成子图,定义,3,如果图,G,的一个子图包含,G,的所有顶点，称,该子图为,G,的一个生成子图,例,2,如图所示，求,G,的所有生成子图,1,2,3,图,G,解：按边数分别求出,7,定理：简单图,G=(n,m),的所有生成子图个数为,2,m,(,二,),、图运算,在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。,1,、图的删点、删边运算,(1),、图的删点运算,设 ，在,G,中删去 中的顶点和,G,中与之关联的所有边的操作，称为删点运算。记为,特别地，如果只删去一个点,v,，则记为,G-v.,8,2,、图的交运算,设,G,1,G,2,是,G,的两个子图，,G,1,与,G,2,交是指由 为顶点集，以 为边集组成的子图。记为：,设,G,1,G,2,是两个图，,G,1,与,G,2,的差是指从,G,1,中删去,G,2,中的边得到的新图。记为,G,1,-G,2,.,3,、图的差运算,4,、图的对称差运算,(,或环和运算,),设,G,1,G,2,是两个图，,G,1,与,G,2,的对称差定义为：,10,例,3,已知,G,1,与,G,2,，求,1,2,3,4,a,b,c,d,e,f,G,1,h,2,3,5,4,c,d,e,g,i,j,G,2,解：由相应运算定义得下面结果：,1,2,3,4,a,b,c,d,e,f,5,h,g,i,j,2,3,4,c,d,e,11,5,、图的联运算,设,G,1,G,2,是两个不相交的图，作,G,1,+G,2,，并且将,G,1,中每个顶点和,G,2,中的每个顶点连接，这样得到的新图称为,G,1,与,G,2,的联图。记为：,例,4,已知,G,1,与,G,2,，求,2,1,G,1,3,4,5,G,2,解：由联图的定义得：,2,1,3,4,5,13,6,、图的合成图,设 是两个图。对点集,的任意两个点,u=(u,1,u,2,),与,v=(v,1,v,2,),当,(u,1,adjv,1,),或,(u,1,=v,1,和,u,2,adjv,2,),时，,把,u,与,v,相连。如此得到的新图称为,G,1,与,G,2,的合成图。记为,例,6,已知,G,1,与,G,2,，求,G,1,1,2,G,2,3,4,5,(1,4),(1,3),(1,5),(2,3),(2,4),(2,5),15,图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常采用所谓的“超立方体”结构。采用该结构可使网络具有较好的可靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。,“超立方体”可以采用积图来递归构造。定义如下：,(1)1,方体,(2)n,方体定义为：,Q,1,Q,3,Q,2,“超立方体”常采用下面简单的递归构造方法：,16,(,三,),、路与连通性,对图的路与连通性进行研究，在计算机网络研究中有十分重要的意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠性也是主要问题之一，它与图的连通性问题相对应。,1,、路与连通性的相关概念,(1),、图中的途径,G,的一条途径（或通道或通路）是指一个有限非空序列,w,=,v,0,e,1,v,1,e,2,v,2,e,k,v,k,，,它的项交替地为顶点和边，使得 ，,e,i,的端点是,v,i-1,和,v,i.,途径中边数称为途径的长度；,v,0,v,k,分别称为途径的起点与终点，其余顶点称为途径的内部点。,(2),、图中的迹,边不重复的途径称为图的一条迹。,18,图中顶点,u,与,v,的距离：,u,与,v,间最短路的长度称为,u,与,v,间距离。记为,d(u,v).,如果,u,与,v,间不存在路，定义,d(u,v)=,.,(3),、图中的路,(4),、图中两顶点的距离,注：起点与终点重合的途径、迹、路分别称为图的闭途径、闭迹 与圈。闭迹也称为回路。长度为,k,的圈称为,k,圈，,k,为奇数时称为奇 圈，,k,为偶数时称为偶圈。,顶点不重复的途径称为图的一条路。,(5),、图中两顶点的连通性,图,G,中点,u,与,v,说是连通的，如果,u,与,v,间存在通路。否则称,u,与,v,不连通。点的连通关系是等价关系。,如果图,G,中任意两点是连通的，称,G,是连通图，否则，称,G,是非连通图。非连通图中每一个极大连通部分，称为,G,的连通分支。,G,的连通分支的个数，称为,G,的分支数，记为,19,(6),、图的直径,连通图,G,的直径定义为：,如果,G,不连通，图,G,的直径定义为,例,6,证明：在,n,阶连通图中,(1),至少有,n-1,条边；,(2),如果边数大于,n-1,，则至少有一条闭迹；,(3),如果恰有,n-1,条边，则至少有一个奇度点。,证明,:(1),若,G,中没有,1,度顶点，由握手定理：,20,若,G,中有,1,度顶点,u,，对,G,的顶点数作数学归纳。,当,n=2,时，结论显然；设结论对,n=k,时成立。,当,n=k+1,时，考虑,G-u,它仍然为连通图，所以，边数,k-1.,于是,G,的边数,k.,另证：由于,G,连通，所以，存在如下形式的途径：,显然该途径至少含有,n-1,条边。,(v,1,v,2,v,n,是,G,的,n,个不同顶点,),(2),考虑,G,中途径：,若,W,是路，则长为,n-1;,但由于,G,的边数大于,n-1,因此，存在,v,i,与,v,j,它们相异，但邻接。于是：,为,G,中一闭途径，于是也就存在闭迹。,21,(3),若不然，,G,中顶点度数至少为,2,，于是由握手定理：,这与,G,中恰有,n-1,条边矛盾！,例,7,证明：若,2,，则,G,中必然含有圈。,证明：只就连通图证明即可！,设,W=v,1,v,2,.v,k-1,v,k,是,G,中的一条最长路。由于,2,，所以,v,k,必然有相异于,v,k-1,的邻接顶点。又,W,是,G,中最长路所以，这样的邻接点必然是,v,1,v,2,.,v,k-2,中之一。设该点为,vm,，则,v,m,v,m+1,.v,k,v,m,为,G,中圈。,例,8,设,G,是具有,m,条边的,n,阶单图，证明：若,G,的直径为,2,且,=n-2,则,m2n-4.,证明：设,d(v)=,=n-2,且设,v,的邻接点为,v,1,v,2,v,n-2,.u,是剩下的一个顶点。由于,d(G)=2,且,u,不能和,v,邻接，所以,u,必须和,v,1,v,2,v,n-2,中每个顶点邻接。否则有,d(G)2.,于是得：,m2n-4.,22,如果,u,与,v,在,G,的两个不同分支中，则在,G,的补图中必然邻接，因此，也连通。,所以，若,G,不连通，,G,的补图是连通的。,定理,2,：设图,G,为,n,阶图，若对,G,中任意两个不相邻顶点,u,与,v,，有：,则,G,是连通的,且,d(G),2.,证明：我们证明，对,G,中任意两点,x,与,y,一定存在一条长度至多为,2,的连接,x,与,y,的路。,若,则上面论断成立！若,可以证明，存在点,w,，它与,x,y,同时邻接。,若不然，在,G,的剩下的,n-2,个顶点中，假设有,k,个与,x,邻接，但与,y,不邻接，有,l,个顶点和,y,邻接，但不和,x,邻接，同时假定有,m,个顶点,24,和,x,y,均不邻接。则：,d(x)=k-1,d(y)=,l,-1,。由于,k+,l,+m=n-2,所以，,d(x)+d(y)=k+,l,-2,n-4,矛盾！,推论：设图,G,为,n,阶图，若,(n-1)/2,则,G,连通。,证明：对,G,中任意两个不相邻顶点,u,与,v,，有：,所以，,G,是连通的。,注意：定理,2,的界是紧的,(Sharpness),。即不能再修改！,例如：设,G,由两个分支作成的图，两个分支均为,K,m,则,G,中不相邻顶点度数之和恰为,n-2.(n=2m),3,、偶图的判定定理,25,定理,3,一个图是偶图当且当它不包含奇圈,。,证明：,必要性,：设,G,是具有二分类（,X,Y,）的偶图，并且,C,=,v,0,v,1,v,k,v,0,是,G,的一个圈,不失一般性，可假定 。,一般说来，,。又因为,，所以,由此即得,C,是偶圈,。,充分性,：在,G,中任意选取点,u,定义,V,的分类如下：,X,=,x,|,d,(,u,x,),是偶数，,x,V,(,G,),Y,=,y,|,d,(,u,y,),是奇数，,y,V,(,G,),下面证明：对,X,中任意两点,v,与,w,v,与,w,不邻接！,26,作业,P29P30 13,14,20,22,28,Thank You!,29,