资源描述
单击此处编辑母版标题样式,*,第五部分,图论,本部分主要内容,图的基本概念,欧拉图、哈密顿图,树,1,第十四章,图的基本概念,主要内容,图,通路与回路,图的连通性,图的矩阵表示,图的运算,预备知识,多重集合,元素可以重复出现的集合,无序积,A,B,=,x,y, |,x,A,y,B,2,14.1,图,定义,14.1,无向图,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,= ,为一无向图,3,有向图,定义,14.2,有向图,D,=,只需注意,E,是,V,V,的多重子集,图,2,表示的是一个有向图，试写出它的,V,和,E,注意：图的数学定义与图形表示。,4,相关概念,1.,图, 可用,G,泛指图（无向的或有向的）,V,(,G,),E,(,G,),V,(,D,),E,(,D,),n,阶图,2.,有限图,3.,n,阶零图与平凡图,4.,空图,5.,用,e,k,表示无向边或有向边,6.,顶点与边的关联关系, 关联、关联次数, 环, 孤立点,7.,顶点之间的相邻关系,5,8.,邻域与关联集,v,V,(,G,) (,G,为无向图,),v,的关联集,v,V,(,D,) (,D,为有向图,),9.,标定图与非标定图,10.,基图,相关概念,6,多重图与简单图,定义,14.3,(1),无向图中的平行边及重数,(2),有向图中的平行边及重数（注意方向性）,(3),多重图,(4),简单图,在定义,14.3,中定义的简单图是极其重要的概念,7,顶点的度数,定义,14.4,(1),设,G,=,为无向图,v,V,d,(,v,),v,的度数,简称度,(2),设,D,=,为有向图,v,V,d,+,(,v,),v,的入度,d,(,v,),v,的出度,d,(,v,),v,的度或度数,(3),(,G,),(,G,),(4),+,(,D,),+,(,D,),(,D,),(,D,),(,D,),(,D,),(5),奇顶点度与偶度顶点,8,定理,14.1,设,G,=,为任意无向图，,V,=,v,1,v,2,v,n, |,E,|=,m,则,证,G,中每条边,(,包括环,),均有两个端点，所以在计算,G,中各顶点度数之和时，每条边均提供,2,度，,m,条边共提供,2,m,度,.,本定理的证明类似于定理,14.1,握手定理,定理,14.2,设,D,=,为任意有向图，,V,=,v,1,v,2,v,n, |,E,|=,m,则,9,握手定理推论,推论,任何图,(,无向或有向,),中，奇度顶点的个数是偶数,.,证,设,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,|,必为偶数,.,10,例,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.,握手定理应用,11,图的度数列,1 .,V,=,v,1,v,2, ,v,n,为无向图,G,的顶点集，称,d,(,v,1,),d,(,v,2,), ,d,(,v,n,),为,G,的,度数列,2.,V,=,v,1,v,2, ,v,n,为有向图,D,的顶点集，,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,),3.,非负整数列,d,=(,d,1,d,2, ,d,n,),在什么条件下是,可图化的,，是,可简单图化,的？,定理,14.4 p277,易知：,(2, 4, 6, 8, 10),，,(1, 3, 3, 3, 4),是可图化的，后者又是可,简单图化的，而,(2, 2, 3, 4, 5),，,(3, 3, 3, 4),都不是可简单图化,的，特别是后者也不是可图化的,12,n,阶完全图与竞赛图,定义,14.6,(1),n,(,n,1),阶无向完全图,每个顶点与其余顶点均相邻的,无向简单图,，记作,K,n,.,简单性质：边数,(2),n,(,n,1),阶,有向完全图,每对顶点之间均有两条方向相反的有向边的,有向简单图,.,简单性质：,(3),n,(,n,1),阶,竞赛图,基图为,K,n,的,有向简单图,.,简单性质：边数,13,n,阶,k,正则图,(1),为,K,5,，,(2),为,3,阶有向完全图，,(3),为,4,阶竞赛图,.,(1) (2) (3),定义,14.7,n,阶,k,正则图,=,=,k,的,无向简单图,简单性质：边数（由握手定理得）,n,阶完全图,K,n,是,n,1,正则图，,14,子图,定义,14.8,G,=,G,=,(1),G,G,G,为,G,的,子图,，,G,为,G,的,母图,(2),若,G,G,且,V,=,V,，则称,G,为,G,的,生成子图,(3),若,V,V,或,E,E,，称,G,为,G,的,真子图,(4),V,（,V,V,且,V,）的,导出子图,，记作,G,V,(5),E,（,E,E,且,E,）的,导出子图,，记作,G,E,15,例,2,画出,K,4,的所有非同构的生成子图,实例,16,补图,定义,14.9,设,G,=,为,n,阶无向简单图，以,V,为顶点集，以所有使,G,成为完全图,K,n,的,添加边,组成的集合为边集的图，称为,G,的,补图,，记作,.,若,G,则称,G,是,自补图,.,例：见书,P280,图,14.6,17,14.2,通路与回路,定义,14.11,给定图,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),复杂通路与回路：有边重复出现,18,几点说明,表示法, 定义表示法, 只用边表示法, 只用顶点表示法（在简单图中）, 混合表示法,环,（长为,1,的圈）的长度为,1,，两条平行边构成的圈长度为,2,，无向简单图中，圈长,3,，有向简单图中圈的长度,2.,不同的圈（以长度,3,的为例）,19,通路与回路的长度,定理,14.5,在,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,的初级通路（路径）,.,定理,14.6,在一个,n,阶图,G,中，若存在,v,i,到自身的回路，则一,定存在,v,i,到自身长度小于或等于,n,的回路,.,推论,在一个,n,阶图,G,中，若存在,v,i,到自身的简单回路，则一,定存在长度小于或等于,n,的初级回路,.,20,14.3,图的连通性,无向图的连通性,(1),顶点之间的连通关系：,G,=,为无向图, 若,v,i,与,v,j,之间有通路，则,v,i,v,j,是,V,上的等价关系,R,=|,u,v,V,且,u,v,(2),G,的连通性与连通分支, 若,u,v,V,，,u,v,，则称,G,连通,V,1,V,2,V,k,，称,G,V,1,G,V,2, ,G,V,k,为,连通分,支,，其个数,p,(,G,)=,k,(,k,1),；,k,=1,，,G,连通,21,短程线与距离,(3),短程线与距离,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,),22,无向图的连通度,1.,删除顶点及删除边,G,v,从,G,中将,v,及关联的边去掉,G,V,从,G,中删除,V,中所有的顶点,G,e,将,e,从,G,中去掉,G,E,删除,E,中所有边,2.,点割集与边割集,点割集与割点 书,p283,定义,14.15,G,=,V,V,V,为,点割集,p,(,G,V,),p,(,G,),且有极小性,v,为,割点,v,为点割集,定义,14.16,G,=,E,E,E,是,边割集,p,(,G,E,),p,(,G,),且有极小性,e,是,割边,（桥）,e,为边割集,23,点割集与割点,例,3,v,1,v,4,，,v,6,是点,割集，,v,6,是割点,. ,v,2,v,5,是点割集吗？,e,1,e,2,，,e,1,e,3,e,5,e,6,，,e,8,等是边割集，,e,8,是,桥，,e,7,e,9,e,5,e,6,是边割,集吗？,几点说明：,K,n,中无点割集，,N,n,中既无点割集，也无边割集，其中,N,n,为,n,阶零图,.,若,G,连通，,E,为边割集，则,p,(,G,E,)=2,，,V,为点割集，则,p,(,G,V,),2,24,点连通度与边连通度,定义,14.18,G,为连通非完全图,点连通度,(,G,) = min |,V,|,V,为点割集,规定,(,K,n,) =,n,1,若,G,非连通，,(,G,) = 0,若,(,G,),k,，则称,G,为,k,-,连通图,定义,14.19,设,G,为连通图,边连通度,(,G,) =,min|,E,|,E,为边割集,若,G,非连通，则,(,G,) = 0,若,(,G,),r,，则称,G,是,r,边,-,连通图,图中，,=,=1,，它是,1-,连通图 和,1,边,-,连通图,25,有向图的连通性,定义,14.20,D,=,为有向图,v,i,v,j,（,v,i,可达,v,j,）,v,i,到,v,j,有通路,v,i,v,j,（,v,i,与,v,j,相互可达）,性质,具有自反性,(,v,i,v,i,),、传递性,具有自反性、对称性、传递性,v,i,到,v,j,的短程线与距离,类似于无向图中，只需注意距离表示法的不同,(,无向图中,d,(,v,i,v,j,),，有向图中,d,),及,d,无对称性,26,有向图的连通性及分类,定义,14.22,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,易知，强连通,单向连通,弱连通,判别法,定理,14.8,D,强连通当且仅当,D,中存在经过每个顶点至少一次,的回路,定理,14.9,D,单向连通当且仅当,D,中存在经过每个顶点至少一,次的通路,27,二部图,定义,14.23,设,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,阶零图为二部图,.,28,14.4,图的矩阵表示,无向图的关联矩阵（对图无限制）,P288,定义,14.24,无向图,G,=,，,|,V,|=,n,，,|,E,|=,m,，令,m,ij,为,v,i,与,e,j,的关联次数，称,(,m,ij,),n,m,为,G,的,关联矩阵,，记为,M,(,G,).,性质,29,有向图的关联矩阵（无环有向图）,P288,定义,14.25,有向图,D,=,，令,则称,(,m,ij,),n,m,为,D,的,关联矩阵,，记为,M,(,D,).,(4),平行边对应的列相同,性质,有向图的关联矩阵,30,有向图的邻接矩阵（无限制）,定义,14.26,设有向图,D,=,V,=,v,1,v,2, ,v,n,E,=,e,1,e,2, ,e,m,令为顶点,v,i,邻接到顶点,v,j,边的条数，称为,D,的,邻接矩,阵,，记作,A,(,D,),，或简记为,A,.,性质,31,推论,设,B,l,=,A,+,A,2,+,A,l,（,l,1,），则,B,l,中元素,为,D,中长度为,l,的通路总数，,定理,14.11,设,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,的回路数,为,D,中长度小于或等于,l,的通路数,.,邻接矩阵的应用,为,D,中长度为,l,的回路总数,.,32,例,5,有向图,D,如图所示，求,A,A,2,A,3,A,4,，并回答诸问题：,(1),D,中长度为,1, 2, 3, 4,的通路各有多少条？其中回路分别为多少条？,(2),D,中长度小于或等于,4,的通路为多少条？其中有多少条回路？,实例,33,(1),D,中长度为,1,的通路为,8,条，其中有,1,条是回路,.,D,中长度为,2,的通路为,11,条，其中有,3,条是回路,.,D,中长度为,3,和,4,的通路分别为,14,和,17,条，回路分别,为,1,与,3,条,.,(2),D,中长度小于等于,4,的通路为,50,条，其中有,8,条是回路,.,实例求解,34,定义,14.27,设,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,的可达矩阵为,35,第十四章,习题课,主要内容,无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构,通路与回路及其分类,无向图的连通性与连通度,有向图的连通性及其分类,图的矩阵表示,36,基本要求,深刻理解握手定理及推论的内容并能灵活地应用它们,深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系,记住通路与回路的定义、分类及表示法,深刻理解与无向图连通性、连通度有关的诸多概念,会判别有向图连通性的类型,熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵,37,1,9,阶无向图,G,中，每个顶点的度数不是,5,就是,6.,证明,G,中至少有,5,个,6,度顶点或至少有,6,个,5,度顶点,.,练习,1,证 关键是利用握手定理的推论,.,方法一：穷举法,设,G,中有,x,个,5,度顶点，则必有,(9,x,),个,6,度顶点，由握手定理推论可知，,(,x,9,x,),只有,5,种可能：,(0,9), (2,7), (4,5), (6,3), (8,1,）它们都满足要求,.,方法二：反证法,否则，由握手定理推论可知，“,G,至多有,4,个,5,度顶点并且至多有,4,个,6,度顶点”，这与,G,是,9,阶图矛盾,.,38,2,数组,2, 2, 2, 2, 3, 3,能简单图化吗？若能，画出尽可能多图来,.,练习,2,只要能画出,6,阶无向简单图，就说明它可简单图化,.,下图的,4,个图都以此数列为度数列。,39,( 1),D,中,v,1,到,v,4,长度为,1,2,3,4,的通路各多少,条？其中几条是非初级的简单通路？,(2),D,中,v,1,到,v,1,长度为,1,2,3,4,的回路各多少,条？讨论它们的类型,.,(3),D,中长度为,4,的通路（不含回路）有多少条？,(4),D,中长度为,4,的回路有多少条？,(5),D,中长度,4,的通路有多少条？其中有几条是回路？,(6),写出,D,的可达矩阵,.,4,有向图,D,如图所示，,回答下列诸问：,练习,4,40,解答,为解,(1)(6),，只需先求,D,的邻接矩阵的前,4,次幂,.,41,(1),v,1,到,v,4,长度为,1,2,3,4,的通路数分别为,0,0,2,2.,其中只有长度为,4,的两条是非初级的简单通路（定义意义下），见下图所示,.,解答,42,解答,(2),v,1,到,v,1,长度为,1,2,3,4,的回路数分别为,1,1,3,5.,其中长度为,1,的是初级的,(,环,),；长度为,2,的是复杂的；长度为,3,的中有,1,条是复杂的，,2,条是初级的；长度为,4,的有,1,条是复杂的，有,4,条是非初级的简单回路,.,请在图中行遍以上各回路,.,(3),长度为,4,的通路,(,不含回路,),为,33,条,.,(4),长度为,4,的回路为,11,条,.,(5),长度,4,的通路,88,条，其中,22,条为回路,.,(6) 4,4,的全,1,矩阵,.,43,
展开阅读全文