第7章_图的基本概念.ppt

单击此处编辑母版标题样式,*,图论,本部分主要内容,图的基本概念,欧拉图、哈密顿图,树,平面图,支配集、覆盖集、独立集、匹配与着色,1,2,图的基本概念,主要内容,图,通路与回路,图的连通性,图的矩阵表示,图的运算,预备知识,多重集合,元素可以重复出现的集合,无序集,A,B,=(,x,y,)|,x,A,y,B,3,无序对,:,两个元素组成的二元组（没有顺序），即,无论,a,b,是否相同，（,a,b,）（,b,a,）,无序积,:,A,与,B,为,两个集合，,A,B,=(,x,y,)|,x,A,y,B,例,A,=,a,1,a,2,B,=,b,1,b,2,A,B,=(,a,1,b,1,),(,a,1,b,2,),(,a,2,b,1,),(,a,2,b,2,),A,A,=(,a,1,a,1,),(,a,1,a,2,),(,a,2,a,2,),多重集合,:,元素可以重复出现的集合,图,4,图,定义,无向图,G,=,其中,(1),V,为顶点集，元素称为,顶点,(2),E,为,V,V,的多重集，其元素称为无向边，简称,边,实例,设,V,=,v,1,v,2,v,5,E,=(,v,1,v,1,),(,v,1,v,2,),(,v,2,v,3,),(,v,2,v,3,),(,v,2,v,5,),(,v,1,v,5,),(,v,4,v,5,),则,G,=,为一无向图,5,有向图,定义,有向图,D,=,只需注意,E,是,V,V,的多重子集,图,2,表示的是一个有向图，试写出它的,V,和,E,注意：图的数学定义与图形表示，在同构（待叙）的意义下,是一一对应的,6,顶点和边的关联与相邻,定义,设,e,k,=(,v,i,v,j,),是无向图,G,=,的一条边,称,v,i,v,j,为,e,k,的,端点,e,k,与,v,i,(,v,j,),关联,.,若,v,i,v,j,则称,e,k,与,v,i,(,v,j,),的,关联次数为,1,;,若,v,i,=,v,j,则称,e,k,为,环,此时称,e,k,与,v,i,的,关联次数为,2,;,若,v,i,不是,e,k,端点,则称,e,k,与,v,i,的,关联次数为,0,.,无边关联的顶点称作,孤立点,.,7,无向图与有向图,(,续,),通常用,G,表示无向图,D,表示有向图,也常用,G,泛指无向图和有向图,用,e,k,表示无向边或有向边,.,V,(,G,),E,(,G,),V,(,D,),E,(,D,):,G,和,D,的顶点集,边集,.,n,阶图,:,n,个顶点的图,有限图,:,V,E,都是有穷集合的图,零图,:,E,=,平凡图,:1,阶零图,8,定义,设无向图,G,=,v,i,v,j,V,e,k,e,l,E,若,(,v,i,v,j,),E,则称,v,i,v,j,相邻,;,若,e,k,e,l,至少有一个公共端点,则称,e,k,e,l,相邻,.,对有向图有类似定义,.,设,e,k,=,v,i,v,j,是有向图的一条边,v,i,v,j,是,e,k,端点,又,称,v,i,是,e,k,的,始点,v,j,是,e,k,的,终点,v,i,邻接到,v,j,v,j,邻接于,v,i,.,9,顶点的度数,设,G,=,为无向图,v,V,v,的度数,(,度,),d,(,v,),:,v,作为边的端点的次数之和,G,的最大度,(,G,),=max,d,(,v,)|,v,V,G,的最小度,(,G,),=min,d,(,v,)|,v,V,例如,d,(,v,5,)=3,d,(,v,2,)=4,d,(,v,1,)=4,(,G,)=4,(,G,)=1,10,顶点的度数,(,续,),设,D,=,为有向图,v,V,v,的出度,d,+,(,v,),:,v,作为边的始点的次数之和,v,的入度,d,(,v,),:,v,作为边的终点的次数之和,v,的度数,(,度,),d,(,v,),:,v,作为边的端点次数之和,d,(,v,)=,d,+,(,v,)+,d,-,(,v,),D,的最大出度,+,(,D,),最小出度,+,(,D,),最大入度,(,D,),最小入度,(,D,),最大度,(,D,),最小度,(,D,),例如,d,+,(,a,)=4,d,-,(,a,)=1,d,(,a,)=5,d,+,(,b,)=0,d,-,(,b,)=3,d,(,b,)=3,+,(,D,)=4,+,(,D,)=0,(,D,)=3,(,D,)=1,(,D,)=5,(,D,)=3.,11,定理,设,G,=,为任意无向图，,V,=,v,1,v,2,v,n,|,E,|=,m,则,证,G,中每条边,(,包括环,),均有两个端点，所以在计算,G,中各顶点度数之和时，每条边均提供,2,度，,m,条边共提供,2,m,度,.,握手定理,定理,设,D,=,为任意有向图，,V,=,v,1,v,2,v,n,|,E,|=,m,则,12,握手定理推论,推论,任何图,(,无向或有向,),中，奇度顶点的个数是偶数,.,证,设,G,=,为任意图，令,V,1,=,v,|,v,V,d,(,v,),为奇数,V,2,=,v,|,v,V,d,(,v,),为偶数,则,V,1,V,2,=,V,V,1,V,2,=,，由握手定理可知,由于,2,m,均为偶数，所以 为偶数，但因为,V,1,中,顶点度数为奇数，所以,|,V,1,|,必为偶数,.,13,例,1,无向图,G,有,16,条边，,3,个,4,度顶点，,4,个,3,度顶点，其余顶点度数均小于,3,，问,G,的阶数,n,至少为几？,解 本题的关键是应用握手定理,.,设除,3,度与,4,度顶点外，还有,x,个顶点,v,1,v,2,v,x,，则,d,(,v,i,),2,，,i,=1,2,x,，,于是得不等式,32,24+2,x,得,x,4,阶数,n,4+4+3=11.,握手定理应用,14,图的度数列,设,无向图,G,的顶点集,V,=,v,1,v,2,v,n,G,的度数序列,:,d,(,v,1,),d,(,v,2,),d,(,v,n,),如右图度数序列,:4,4,2,1,3,设有向图,D,的顶点集,V,=,v,1,v,2,v,n,D,的度数序列,:,d,(,v,1,),d,(,v,2,),d,(,v,n,),D,的出度序列,:,d,+,(,v,1,),d,+,(,v,2,),d,+,(,v,n,),D,的入度序列,:,d,(,v,1,),d,(,v,2,),d,(,v,n,),如右图度数序列,:5,3,3,3,出度序列,:4,0,2,1,入度序列,:1,3,1,2,15,握手定理的应用,例,(3,3,3,4),(2,3,4,6,8),能成为图的度数序列吗,?,解 不可能,.,它们都有奇数个奇数,.,例,已知图,G,有,10,条边,4,个,3,度顶点,其余顶点的度数均小于等于,2,问,G,至少有多少个顶点,?,解,设,G,有,n,个顶点,.,由握手定理,4,3+2(,n,-4)210,解得,n,8,16,握手定理的应用,(,续,),例,给定下列各序列,哪组可以构成无向图的度数序列,(2,2,2,2,2),(1,1,2,2,3),(1,1,2,2,2),(1,3,4,4,5),17,图的同构,定义,设,G,1,=,G,2,=,为两个无向图,(,两个有向,图,),，若存在双射函数,f,:,V,1,V,2,对于,v,i,v,j,V,1,(,v,i,v,j,),E,1,当且仅当,(,f,(,v,i,),f,(,v,j,),E,2,（,E,1,当且仅当,E,2,),并且,(,v,i,v,j,),（,）与,(,f,(,v,i,),f,(,v,j,),（,）的重数相,同，则称,G,1,与,G,2,是,同构,的，记作,G,1,G,2,.,图之间的同构关系具有自反性、对称性和传递性,.,能找到多条同构的必要条件，但它们全不是充分条件：,边数相同，顶点数相同,;,度数列相同,;,对应顶点的关联集及邻域的元素个数相同，等等,若破坏必要条件，则两图不同构,判断两个图同构是个难题,18,图同构的实例,图中,(1),与,(2),的度数列相同，它们同构吗？为什么？,(1)(2)(3)(4),图中，,(1),与,(2),不同构（度数列不同），,(3),与,(4),也不同构,.,(1)(2),19,20,多重图与简单图,定义,(1),在无向图中,如果有,2,条或,2,条以上的边关联同一对顶点,则称这些边为,平行边,平行边的条数称为,重数,.,(,2),在,有向图中,如果有,2,条或,2,条以上的边具有相同的始点和终点,则称这些边为,有向平行边,简称,平行边,平行边的条数称为,重数,.,(,3),含平行边的图称为,多重图,.,(4),既无平行边也无环的图称为,简单图,.,21,多重图与简单图,(,续,),例如,e,5,和,e,6,是平行边,重数为,2,不是简单图,e,2,和,e,3,是平行边,重数为,2,e,6,和,e,7,不是平行边,不是简单图,22,给定下列各序列,哪组可以构成简单无向图的度数序列,(2,2,2,2,2),(1,1,2,2,3),(1,1,2,2,2),(2,3,4,4,5),23,n,阶完全图,定义,(1),n,(,n,1),阶无向完全图,每个顶点与其余顶点均相邻的无向简单图，记作,K,n,.,简单性质：边数,(2),n,(,n,1),阶,有向完全图,每对顶点之间均有两条方向相反的有向边的有向简单图,.,简单性质：,24,子图,定义,设,G,=,G,=,是,2,个图,(1),若,V,V,且,E,E,则称,G,为,G,的,子图,G,为,G,的,母图,记作,G,G,(2),若,G,G,且,G,G,（即,V,V,或,E,E,），称,G,为,G,的,真子图,(3),若,G,G,且,V,=,V,，,则称,G,为,G,的,生成子图,(4),设,V,V,且,V,以,V,为顶点集,以两端点都在,V,中的所有边为边集的,G,的,子图称作,V,的导,出子图,，记作,G,V,(5),设,E,E,且,E,以,E,为边集,以,E,中边关联的,所有顶点为顶点集的,G,的,子图称作,E,的导出子,图,记作,G,E,25,例,画出,K,4,的所有非同构的生成子图,实例,26,补图,定义,设,G,=,为,n,阶无向简单图，以,V,为顶点集，以所有使,G,成为完全图,K,n,的添加边组成的集合为边集的图，称为,G,的,补图,，记作,.,若,G,则称,G,是,自补图,.,27,指出下图中哪些是自补图,.,28,1,：互为自补图的两个图的边数有何关系？,2:,如果一个简单图有,15,条边而它的补图有,13,条边,则这个图有多少个顶点,?,答：,8,个,29,通路与回路,定义,给定图,G,=,（无向或有向的），,G,中,顶点与,边的交替序列,=,v,0,e,1,v,1,e,2,e,l,v,l,，,v,i,1,v,i,是,e,i,的端点,.,(1),通路与回路：,为,通路,；若,v,0,=,v,l,，,为,回路,，,l,为,回路长,度,.,(2),简单通路与回路：所有边各异，,为,简单通路,，又若,v,0,=,v,l,，,为,简单回路,(3),初级通路,(,路径,),与初级回路,(,圈,),：,中所有顶点各异，则称,为,初级通路,(,路径,),，又若除,v,0,=,v,l,，所有的顶点各不相同且所有的边各异，则称,为,初级回路,(,圈,),(4),复杂通路与回路：有边重复出现,30,通路与回路,(,续,),说明,:,在无向图中，环是长度为,1,的圈,两条平行边构成长度为,2,的圈,.,在有向图中，环是长度为,1,的圈,两条方向相反边构成长度为,2,的圈,.,在无向简单图中,所有圈的长度,3;,在有向简单图中,所有圈的长度,2.,31,通路与回路的长度,定理,在,n,阶图,G,中，若从顶点,v,i,到,v,j,（,v,i,v,j,）存在通路，,则从,v,i,到,v,j,存在长度小于或等于,n,1,的通路,.,推论,在,n,阶图,G,中，若从顶点,v,i,到,v,j,（,v,i,v,j,）存在通路，则,从,v,i,到,v,j,存在长度小于或等于,n,1,的初级通路（路径）,.,定理,在一个,n,阶图,G,中，若存在,v,i,到自身的回路，则一,定存在,v,i,到自身长度小于或等于,n,的回路,.,推论,在一个,n,阶图,G,中，若存在,v,i,到自身的简单回路，则一,定存在长度小于或等于,n,的初级回路,.,32,无向图的连通性,设,无向图,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,33,短程线与距离,短程线与距离,u,与,v,之间的,短程线,：,u,v,，,u,与,v,之间长度最短的通路,u,与,v,之间的,距离,：,d,(,u,v,),短程线的长度,d,(,u,v,),的性质：,d,(,u,v,),0,u,v,时,d,(,u,v,)=,d,(,u,v,)=,d,(,v,u,),d,(,u,v,)+,d,(,v,w,),d,(,u,w,),34,有向图的连通性及分类,定义,D,=,为有向图,D,弱连通,(,连通,),基图为无向连通图,D,单向连通,v,i,v,j,V,，,v,i,v,j,或,v,j,v,i,D,强连通,v,i,v,j,V,，,v,i,v,j,易知，强连通,单向连通,弱连通,35,有向图的连通性,(,续,),(1),(2),(3),例 下图,(1),强连通,(2),单连通,(3),弱连通,36,熟人关系图的连通性（六度分离理论）,网络图的连通性,利用回路的长度判断同构,连通性的应用,37,(1)(2),38,图的矩阵表示,无向图的关联矩阵（对图无限制）,定义,无向图,G,=,，,|,V,|=,n,，,|,E,|=,m,，令,m,ij,为,v,i,与,e,j,的关联次数，称,(,m,ij,),n,m,为,G,的,关联矩阵,，记为,M,(,G,).,性质,39,v,1,v,2,v,4,v,3,e,1,e,2,e,3,e,4,e,5,关联次数为可能取值为,0,，,1,，,2,40,有向图的关联矩阵（无环有向图）,定义,有向图,D,=,，令,则称,(,m,ij,),n,m,为,D,的,关联矩阵,，记为,M,(,D,).,(4),平行边对应的列相同,性质,有向图的关联矩阵,41,m=0,6,m=1,5,三阶有向完全图的生成子图,42,三阶有向完全图的生成子图,43,三阶有向完全图的子图,两个顶点的子图,一个顶点的子图,44,v,4,v,1,v,2,v,3,e,1,e,2,e,3,e,4,e,5,性质,:,(4),平行边对应的列相同,45,有向图的邻接矩阵（无限制）,定义,设有向图,D,=,V,=,v,1,v,2,v,n,E,=,e,1,e,2,e,m,令为顶点,v,i,邻接到顶点,v,j,边的条数，称为,D,的,邻接矩,阵,，记作,A,(,D,),，或简记为,A,.,性质,46,v,2,v,1,v,4,v,3,47,为,D,中长度为,l,的通路总数，,定理,设,A,为有向图,D,的邻接矩阵，,V,=,v,1,v,2,v,n,为顶点集，则,A,的,l,次幂,A,l,（,l,1,）中元素,为,D,中,v,i,到,v,j,长度为,l,的通路数，其中,为,v,i,到自身长度为,l,的回路数，而,邻接矩阵的应用,为,D,中长度为,l,的回路总数,.,48,D,中的通路及回路数,(,续,),例 有向图,D,如图所示,求,A,A,2,A,3,A,4,并回答问题：,(1),D,中长度为,1,2,3,4,的通路各有多,少条？其中回路分别为多少条？,(2),D,中长度小于或等于,4,的通路为多,少条？其中有多少条回路？,推论,设,B,l,=,A,+,A,2,+,A,l,(,l,1),则,B,l,中元素,为,D,中长度小于或等于,l,的通路数，,为,D,中长度小于或等于,l,的回路数,.,49,例,(续),长度 通路 回路,合计,50 8,1,8 1,2,11 3,3,14 1,4,17 3,50,定义,设,D,=,为有向图,.,V,=,v,1,v,2,v,n,令,有向图的可达矩阵（无限制）,称,(,p,ij,),n,n,为,D,的可达矩阵，记作,P,(,D,),，简记为,P,.,由于,v,i,V,，,v,i,v,i,，所以,P,(,D,),主对角线上的元素全为,1.,由定义不难看出,D,强连通当且仅当,P,(,D,),为全,1,矩阵,.,下图所示有向图,D,的可达矩阵为,51,二部图,定义,设,G,=,为一个无向图，若能将,V,分成,V,1,和,V,2,(,V,1,V,2,=,V,，,V,1,V,2,=,),，使得,G,中的每条边的两个端点都是,一个属于,V,1,，另一个属于,V,2,，则称,G,为,二部图,(,或称,二分,图,、,偶图,等,),，称,V,1,和,V,2,为,互补顶点子集,，常将二部图,G,记为,.,又若,G,是简单二部图，,V,1,中每个顶点均与,V,2,中所有的顶点相,邻，则称,G,为,完全二部图,，记为,K,r,s,，其中,r,=|,V,1,|,，,s,=|,V,2,|.,注意，,n,阶零图为二部图,.,52,二部图的判别法,定理,无向图,G,=,是,二部图,当且仅当,G,中无奇圈,由定理可知图中各图都是二部图，哪些是完全二部,图？哪些图是同构的？,53,配偶问题,男生,认识的女生,b,1,g,1,g,4,g,5,b,2,g,1,b,3,g,2,g,3,g,4,b,4,g,2,g,4,b,1,b,2,g,1,b,4,g,5,b,3,g,4,g,2,g,3,配偶问题：,可否为每个男生找到他认识的女生做配偶？,54,配偶问题,配偶问题,假定有一个男生有穷集合，其中每个男生认识一些女生，在什么条件下每个男生都可以和他认识的女生结婚？,类似的工作分配问题：现有,n,个人，,m,份工作，每个人有其擅长的工作。在什么条件下每个人都可以得到一份他擅长的工作？如何分配？,55,匹配,设,G,=,为无向图,E,*,E,匹配,(,边独立集,),:,任,2,条边均不相邻的边子集,极大匹配,:,添加任一条边后都不再是匹配的匹配,最大匹配,:,边数最多的极大匹配,匹配数,:,最大匹配中的边数,记为,1,例,3,个图的匹配数 依次为,3,3,4.,56,匹配,(,续,),设,M,为,G,中一个匹配，,v,V,(,G),v,为,M,饱和点,:,M,中有边与,v,关联,v,为,M,非饱和点,:,M,中没有边与,v,关联,M,为完美匹配,:,G,的每个顶点都是,M,饱和点,例,关于,M,1,a,b,e,d,是饱和点,f,c,是非饱和点,M,1,不是完美匹配,M,2,是完美匹配,M,1,M,2,57,二部图中的匹配,定义,设,G,=,为二部图,|,V,1,|,|,V,2,|,M,是,G,中最,大匹配,若,V,1,中顶点全是,M,饱和点,则称,M,为,G,中,V,1,到,V,2,的,完备匹配,.,当,|,V,1,|=|,V,2,|,时,完备匹配变成完美,匹配,.,(1),(2),(3),例 图中红边组成各图的一个匹配，,(1),为完备的,但不是完,美的,;(2),不是完备的,其实,(2),中无完备匹配,;(3),是完美的,.,58,Hall,定理,(,配偶定理,),定理,(Hall,定理,),设二部图,G,=,中，,|,V,1,|,|,V,2,|.,G,中存,在从,V,1,到,V,2,的完备匹配当且仅当,V,1,中任意,k,个顶点至少与,V,2,中的,k,个顶点相邻,(,k,=1,2,|,V,1,|).,由,Hall,定理不难证明,上一页图,(2),没有完备匹配,.,定理,设二部图,G,=,中,V,1,中每个顶点至少关联,t,条边,(,t,1),而,V,2,中每个顶点至多关联,t,条边，则,G,中存在,V,1,到,V,2,的完备匹配,.,Hall,定理中的条件称为“,相异性条件,”,第二个定理中的条件,称为,t,条件,.,满足,t,条件的二部图一定满足相异性条件,.,59,一个应用实例,例 某公司要从,a,b,c,d,e,5,人中派,3,人分别到上海、广州、香港去开会,.,已知,a,只想去上海，,b,只想去广州，,c,d,e,都表示想去广州或香港,.,问该公司在满足个人要求的条件下，共有几种派遣方案？,解 令,G,=,其中,V,1,=,s,g,x,V,2,=,a,b,c,d,e,E,=(,u,v,)|,u,V,1,v,V,2,v,想去,u,其中,s,g,x,分别表示上海、广州和香港,.,G,如图所示,.,G,满足相异性条件，因而可给,出派遣方案，共有,9,种派遣方案,(,请给出这,9,种方案,).,60,(1),D,中有几种非同构的圈？,(2),D,中有几种非圈非同构的简单回路？,(3),D,是哪类连通图,?,(4),D,中,v,1,到,v,4,长度为,1,2,3,4,的通路各多少,条？其中几条是非初级的简单通路？,(5),D,中,v,1,到,v,1,长度为,1,2,3,4,的回路各多少,条？讨论它们的类型,.,(6),D,中长度为,4,的通路（不含回路）有多少条？,(7),D,中长度为,4,的回路有多少条？,(8),D,中长度,4,的通路有多少条？其中有几条是回路？,(9),写出,D,的可达矩阵,.,有向图,D,如图所示，,回答下列诸问：,练习,61,解答,(1),D,中有,3,种非同构的圈，长度分别为,1,2,3,，请画出它们的图形,.,(2),D,中有,3,种非圈的非同构的简单回路，它们的长度分别为,4,5,6.,请画出它们的图形来,.,(3),D,是强连通的（为什么？）,为解,(4)(8),，只需先求,D,的邻接矩阵的前,4,次幂,.,62,(4),v,1,到,v,4,长度为,1,2,3,4,的通路数分别为,0,0,2,2.,其中只有长度为,4,的两条是非初级的简单通路（定义意义下），见下图所示,.,解答,63,解答,(5),v,1,到,v,1,长度为,1,2,3,4,的回路数分别为,1,1,3,5.,其中长度为,1,的是初级的,(,环,),；长度为,2,的是复杂的；长度为,3,的中有,1,条是复杂的，,2,条是初级的；长度为,4,的有,1,条是复杂的，有,4,条是非初级的简单回路,.,请在图中行遍以上各回路,.,(6),长度为,4,的通路,(,不含回路,),为,33,条,.,(7),长度为,4,的回路为,11,条,.,(8),长度,4,的通路,88,条，其中,22,条为回路,.,(9)4,4,的全,1,矩阵,.,64,