第9章 图论.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,引 言,图论是离散数学的重要组成部分，是近代应用数学的重要分支。人们常称,1736,年是图论历史元年，因为在这一年瑞士数学家欧拉（,Euler,）发表了图论的首篇论文,哥尼斯堡七桥问题无解,，所以人们普遍认为欧拉是图论的创始人。,1936,年，匈牙利数学家寇尼格（,Konig,）出版了图论的第一部专著,有限图与无限图理论,，这是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。,近,40,年来，随着计算机科学的发展，图论更以惊人的速度向前发展，有人形容说：真是异军突起，活跃非凡。其主要原因有二：其一，计算机科学的发展为图论的发展提供了计算工具；其二，现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系，从而推动科学技术不断地攀登新的高峰。,作为描述事务之间关系的手段或称工具，目前，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。,本部分主要包括图的基本概念（第九章）、欧拉图与哈密顿图（第十一章）、树（第十章,9.1,图,一无向图与有向图,1,无序积与多重集,设,A,，,B,为任意的两个集合，称,a,b|aAbB,为,A,与,B,的,无序积,，记作,A&B.,为方便起见，将无序积中的无序对,a,b,记为,(,a,b,),并且允许,a=b.,需要指出的是，无论,a,b,是否相等，均有,(,a,b,)=(,b,a,),因而,A&B=B&A.,元素可以重复出现的集合称为,多重集合,或者,多重集,，某元素重复出现的次数称为该元素的,重复度,。例如，在多重集合,a,a,b,b,b,c,d,中，,a,b,c,d,的重复度分别为,2,3,1,1.,2,无向图与有向图的定义及表示法,定义,9.1,一个,无向图,是一个有序的二元组,记作,G,，其中（,1,）,V,称为顶点集，其元素称为顶点或结点。（,2,）,E,称为边集，它是无序积,V&V,的多重子集，其元素称为无向边，简称边。,定义,9.2,一个,有向图,是一个有序的二元组,，记作,D,，其中（,1,）,V,同无向图。（,2,）,E,为边集，它是笛卡儿积,VV,的多重子集，其元素称为有向边，简称边。,上面给出了无向图和有向图的集合定义，但人们总是用图形来表示它们，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。,例,9.1,(1),给定无向图,G=,，其中，,V=v1,v2,v3,v4,v5,，,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).,(2),给定有向图,D=,，其中，,V=,a,b,c,d,，,E=,.,画出,G,与,D,的图形。,解,图,9.1,中,(1),(2),分别给出了无向图,G,和有向图,D,的图形。（板书画图）,与定义,9.1,和定义,9.2,有关的还有下面一些概念和规定。,1,n,阶图,在图的定义中，用,G,表示无向图，,D,表示有向图，但有时用,G,泛指图,(,无向的或有向的,),，可是,D,只能表示有向图。另外，为方便起见，有时用,V(G),，,E(G),分别表示,G,的顶点集和边集，若,|V(G)|=n,则称,G,为,n,阶图,，对有向图可做类似规定。,2,有限图,若,|V(G)|,与,|E(G)|,均为有限数，则称,G,为,有限图,，本课件中只讨论有限图。,3,n,阶零图与平凡图,在图,G,中，若边集,E(G)=,则称,G,为零图，此时，又若,G,为,n,阶图，则称,G,为,n,阶零图，记作,N,n,，特别地，称,N,1,为平凡图。,4,空图,在图的定义中规定顶点集,V,为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定定点集为空集的图为空图，并将空图记为,。,5,标定图与非标定图、基图,将图的集合定义转化成图形表示之后，常用,e,k,表示无向边（,v i,，,v j,）（或有向边,）,并称顶点或边用字母标定的图为标定图，否则称为非标定图。另外将有向图各有向边均改成无向边后的无向图称为原来图的基图。易知标定图与非标定图是可以相互转化的，任何无向图,G,的各边均加上箭头就可以得到以,G,为基图的有向图。,6,关联与关联次数、环、孤立点,设,G=,为无向图，,e,k,=(v,i,，,v j)E,，则称,v,i,，,v j,为,e,k,的端点，,e,k,与,vi,或,ek,与,vj,是彼此相,关联,的。若,vivj,，则称,ek,与,vi,或,ek,与,vj,的,关联次数,为,1,，若,vi=,vj,，则称,ek,与,vi,的关联次数为,2,，并称,ek,为,环,。任意的,vlV,，若,vlvi,且,vlvj,，则称,ek,与,vl,的关联次数为,0,。,设,D=,为有向图，,ek,=E,，称,vi,，,v j,为,ek,的端点，若,vi=,vj,，则称,ek,为,D,中的环。无论在无向图中还是在有向图中，无边关联的顶点均称,孤立点,。,7,相邻与邻接,设无向图,G=,，,vi,，,v,jV,，,e k,，,e,lE,.,若,etE,，使得,et=,（,vi,，,v j,），则称,vi,与,vj,是,相邻,的。若,ek,与,el,至少有一个公共端点，则称,ek,与,el,是相邻的。,设有向图,D=,，,vi,，,vjV,，,ek,，,elE,.,若,etE,，使得,et=,，则称,vi,为,et,的始点，,vj,为,et,的终点，并称,vi,邻接到,vj,，,vj,邻接于,vi,。若,ek,的终点为,el,的始点，则称,ek,与,el,相邻。,8,邻域与闭邻域、先驱元集与后继元集、关联集,设无向图,G=,，,vV,，称,u|uV,(,u,v)E,uv,为,v,的邻域，记做,N,G,(v).,并称,N,G,(v)v,为,v,的闭邻域，记做,G(v).,称,e|e E e,与,v,相关联,为,v,的关联集，记做,I,G,(v).,设有向图,D=,，,vV,，称,u|uV,E,uv,为,v,的后继元集，记做,(v).,称,u|uV,E,uv,为,v,的先驱元集，记做,(v).,称,(v)(v),为,v,的邻域，记做,N,D,(v).,称,N,D,(v)v,为,v,的闭邻域，记做,D(v).,在图,9.1,的,(1),图中，,NG(v1)=v2,，,v5,，,G(v1)=v1,，,v2,，,v5,，,I,G,(v1)=e1,，,e2,，,e3.,在,(2),图中，,(d)=c,，,(d)=a,，,c,，,N,D,(d)=a,，,c,，,D(d)=a,，,c,，,d.,9,图的数学定义与表示法,给定图,G,的数学定义，按定义的规定，一定能画出它的图形与之对应，但由于顶点放置的位置可以不同，边的曲直可以不同，所以不同的人画出的图形形状可能不同，但顶点与边之间的关联关系是绝对相同的。反之给定某图,G,的图形，若非标定图，先将顶点与边标定，则能唯一地写出,G,的数学定义形式。,二简单图与多重图,定义,9.3,:,在无向图中，关联一对顶点的无向边如果多于,1,条，则称这些边为,平行边,，平行边的条数称为,重数,。在有向图中，关联一对顶点的有向边如果多于,1,条，并且这些边的始点和终点相同,(,也就是它们的方向相同,),，则称这些边为,平行边,。含平行边的图称为,多重图,，既不含平行边也不含环的图称为,简单图,。,在图,9.1,中，,(1),中,e5,与,e6,是平行边，在,(2),中，,e2,与,e3,是平行边，注意，,e6,与,e7,不是平行边。,(1),，,(2),两个图都不是简单图。,三顶点的度数与握手定理,1,顶点的度数,定义,9.4,设,G=,为一无向图,v V,，称,v,作为边的端点次数之和为,v,的,度数,，简称为度，记做,d,G,(v),，在不发生混淆时，简记为,d(v,).,设,D=,为有向图，,vV,，称,v,作为边的始点次数之和为,v,的,出度,，记做,d,-,D,(v),，简记作,d,-,(v,).,称,v,作为边的终点次数之和为,v,的,入度,，记做,d,+,D,(v),，简记作,d,+,(v),，称,d,-,(v)+d,+,(v),为,v,的度数，记做,d(v,).,2,握手定理,定理,9.1(,握手定理,),设,G=,为任意无向图，,V=v1,v2,vn,，,|E|=m,，则,=2m,定理,9.2(,握手定理,),设,D=,为任意有向图，,V=v1,v2,vn,，,|E|=m,，则,=2m,，且,=m.,握手定理的推论,任何图,(,无向的或有向的,),中，奇度顶点的个数是偶数。,下面给出与顶点度数有关的概念。,1,无向图,G,中的最大度和最小度,在无向图,G,中，令,(G)=max d(v)|v V(G),(G,)=min d(v)|v V(G),称,(G),，,(G,),分别为,G,的,最大度,和,最小度,。在不引起混淆的情况下，将,(G),，,(G,),分别简记为和,.,2,有向图,D,中的最大度、最大出度、最大入度与最小度、最小出度、最小入度,在有向图,D,中，类似无向图，可以定义最大度,(D),，最小度,(D,),，另外，令,+,(D)=,maxd,+,(v)|vV(D,),+,(D,)=,mind,+,(v)|vV(D,),-,(D)=,maxd,-,(v)|vV(D,),-,(D)=,mind,-,(v)|vV(D,),分别称为,D,的,最大出度,，,最小出度,，,最大入度,，,最小入度,。以上记号可分别简记为，,，,+,，,+,，,-,，,-.,3,悬挂顶点与悬挂边；奇度顶点与偶度顶点,称度数为,1,的顶点为,悬挂顶点,，与它关联的边称为,悬挂边,。度为偶数,(,奇数,),的顶点称为,偶度,(,奇度,),顶点,。,在图,9.1,中，,(1),的,d(v1)=4(,注意，环提供,2,度,),，,=4,，,=1,，,v4,是悬挂顶点，,e7,是悬挂边。,(2),的,d,+,(a,)=4,，,d,-,(a)=1(,环,e1,提供出度,1,，提供入度,1),，,d(a,)=4+1=5,。,=5,，,=3,，,+=4(,在,a,点达到,),，,+=0(,在,b,点达到,),，,-=3(,在,b,点达到,),，,-=1(,在,a,和,c,点达到,),。,4,度数列,设,G=,为一个,n,阶无向图,V=v1,v2,vn,称,d(v1),d(v2),d(vn,),为,G,的,度数列,，对于顶点标定的无向图，它的度数列是唯一的。,设,D=,为一个,n,阶有向图，,V=v1,v2,vn,，称,d(v1),d(v2),d(vn,),为,D,的度数列，另外称,d+(v1),d+(v2),d+(vn,),与,d-(v1),d-(v2),d-(vn,),分别为,D,的,出度列,和,入度列,。,在图,9.1(1),中，按顶点的标定顺序，度数列为,4,4,2,1,3.,在,(2),中，按字母顺序，度数列，出度列，入度列分别为,5,3,3,3,；,4,0,2,1,；,1,3,1,2.,5,可图化的与可简单图化的非负整数列,对于给定的非负整数列,d=(d1,d2,dn,),，若存在以,V=v1,v2,vn,为顶点集的,n,阶无向图,G,，使得,d(vi,)=,di,，则称,d,是,可图化的,。特别地，若所得图是简单图，则称,d,是,可简单图化的,。,d=(d1,d2,dn,),是否为可图化的，可由下面定理判别。,定理,9.3,设非负整数列,d=(d1,，,d2,，,，,dn,),，则,d,是可图化的当且仅当,=0(mod 2).,由定理,9.3,立即可知，,(3,，,3,，,2,，,1),，,(3,，,2,，,2,，,1,，,1),等是不可图化的，而,(3,，,3,，,2,，,2),，,(3,，,2,，,2,，,2,，,1),等是可图化的。,定理,9.4,设,G,为任意,n,阶无向简单图，则,(G)n-1.,例,9,2,判断下列各非负整数列哪些是,可图化的,？哪些是,可简单图化的,？,(1)(5,5,4,4,2,1)(2)(5,4,3,2,2)(3)(3,3,3,1),(4)(d1,d2,dn,),，,d1d2dn1,且 为偶,(5)(4,4,3,3,2,2),解,:,除,(1),中序列不可图化外，其余各序列都可图化。但除了,(5),中序列外，其余的都是不可简单图化的。,(2),中序列有,5,个数，若它可简单图化，设所得图为,G,，则,(G)=max5,4,3,2,2=5,，这与定理,14.4,矛盾。所以,(2),中序列不可简单图化。类似可证,(4),中序列不可简单图化。,假设,(3),中序列可以简单图化，设,G=,以,(3),中序列为度数列。不妨设,V=v1,，,v2,，,v3,，,v4,且,d(v1)=d(v2)=d(v3)=3,d(v4)=1,，由于,d(v4),1,，因而,v4,只能与,v1,，,v2,，,v3,之一相邻，于是,v1,，,v2,，,v3,不可能都是,3,度顶点，这是矛盾的，因而,(3),中序列也不可简单图化。,(5),中序列是可简单图化的，图,14.2,中两个,6,阶无向简单图都以,(5),中序列为度数列。,四图的同构,1,两图同构的定义,定义,9.5,设,G,1,=,，,G,2,=,为两个无向图,(,两个有向图,),，若存在,双射函数,f,：,V,1,V,2,，对于,v,i,，,v,j,V,1,，,(v,i,，,v,j,)E,1,(E,1,),当且仅当,(,f(v,i,),，,f(vj,),E,2,(E,2,),，并且,(v,i,，,v,j,)(),与,(,f(v,i,),，,f(v,j,)(),的重数相同，则称,G,1,与,G,2,是,同构,的，记做,G,1,G,2,.,2,图之间的同构关系是等价关系,图之间的同构关系 可看成全体图集合上的二元关系，这个二元关系 具有自反性，对称性和传递性，因而它是等价关系。在这个等价关系的每一等价类中均取一个非标定图作为一个代表，凡与它同构的图，在同构的意义之下都可以看成一个图，在图,9.3,中，,(1),，,(2),，,(3),可以看成一个图，它们都是彼得松图，其中的,(1),可看成这类图的代表。提到,彼得松图,，一般是指,(1),中图。,至此，可以这样说，在图同构的意义下，图的数学定义与图形表示是一一对应的。,关于图之间的同构问题还应该指出以下两点：,a,到目前为止，人们还没有找到判断两个图是否同构的好的算法，还只能根据定义看是否能找到满足条件的双射函数，显然这是困难的。,b,需要注意的是，不要将两个图同构的必要条件当成充分条件。若,G1,G2,，则它们的阶数相同，边数相同，度数列相同，等等。破坏这些必要条件的任何一个，两个图就不会同构，但以上列出的条件都满足，两个图也不一定同构，在图,9.2,中的两个图，有相同的度数列，但它们不同构。,五完全图与正则图,定义,9.6,设,G,为,n,阶无向,简单图,，若,G,中每个顶点均与其余的,n-1,个顶点相邻，则称,G,为,n,阶无向完全图,，简称,n,阶完全图，记做,Kn,(n1),。,设,D,为,n,阶有向简单图，若,D,中每个顶点都邻接到其余的,n-1,个顶点，又邻接于其余的,n-1,个顶点，则称,D,是,n,阶有向完全图,。,设,D,为,n,阶有向简单图，若,D,的基图为,n,阶无向完全图,Kn,，则称,D,是,n,阶竞赛图,。,在图,9.4,中，,(1),为,K5,，,(2),为,3,阶有向完全图，,(3),为,4,阶竞赛图。,图,14.4,易知，,n,阶无向完全图，,n,阶有向完全图，,n,阶竞赛图的边数分别为,n(n-1)/2,，,n(n,1),，,n(n-1)/2.,。,2,正则图,定义,9.7,设,G,为,n,阶无向简单图，若,v V(G),，均有,d(v,)=k,，则称,G,为,k-,正则图,。,由定义可知，,n,阶零图是,0-,正则图，,n,阶无向完全图,是,(n-1),正则图，彼得松图是,3-,正则图。由,握手定理,可知，,n,阶,k-,正则图中，边数,m=kn/2,，因而当,k,为奇数时，,n,必为偶数。,六子图与补图,定义,9.8,设,G=,，,G=,为两个图,(,同为无向图或同为有向图,),，若,V,V,且,E,E,，则称,G,是,G,的,子图,，,G,为,G,的,母图,，记作,G,G.,又若,V V,或,E E,，则称,G,为,G,的真子图。若,V=V,，则称,G,为,G,的,生成子图,。,设,G=,为一图，,V1,V,且,V1,，称以,V1,为顶点集，以,G,中两个端点都在,V1,中的边组成边集,E1,的图为,G,的,V1,导出的子图,，记作,GV1.,又设,E1 E,且,E1,，称以,E1,为边集，以,E1,中边关联的顶点为顶点集,V1,的图为,G,的,E1,导出的子图，记作,GE1.,例,9,3,(1),画出,4,阶,3,条边的所有非同构的无向,简单图,。,(2),画出,3,阶,2,条边的所有非同构的有向简单图。,解,(1),由,握手定理,可知，所画的无向简单图各顶点度数之和为,23=6,，最大度小于或等于,3,。于是所求无向简单图的度数列应满足的条件是，将,6,分成,4,个非负整数，每个整数均大于或等于,0,且小于或等于,3,，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况：,(a)3,，,1,，,1,，,1(b)2,，,2,，,1,，,1(c)2,，,2,，,2,，,0,将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图，见图,14.6,中,(1),，,(2),，,(3).,(2),由握手定理可知，所画有向简单图各顶点度数之和为,4,，最大出度和最大入度均小于或等于,2.,度数列及入度出度列为,(a)1,，,2,，,1 (b)2,，,2,，,0,四个所要求的有向简单图见图,14.6,中,(d),，,(e),，,(f),，,(g).,2,补图与自补图,定义,9.9,设,G=,为,n,阶无向简单图，以,V,为顶点集，以所有使,G,成为,完全图,Kn,的添加边组成的集合为边集的图，称为,G,的补图，记做,.,若图,G,，则称,G,是自补图。,定义,9.10,设,G=,为无向图。,(1),设,eE,，从,G,中去掉边,e,，称为,删除,e,，并用,G-e,表示从,G,中删除,e,所得子图。又设,E E,，从,G,中删除,E,中所有的边，称为,删除,E,，并用,G-E,表示删除,E,后所得子图。,(2),设,vV,，从,G,中去掉,v,及所关联地一切边称为,删除顶点,v,，并用,G-v,表示删除,v,后所得子图。又设,V V,，称从,G,中删除,V,中所有顶点为,删除,V,，并用,G-V,表示所得子图。,(3),设边,e=(u,，,v)E,，先从,G,中删除,e,，然后将,e,的两个端点,u,，,v,用一个新的顶点,w(,或用,u,或,v,充当,w),代替，使,w,关联除,e,外,u,，,v,关联的一切边，称为,收缩边,e,，并用,Ge,表示所得新图。,(4),设,u,，,vV(u,，,v,可能相邻，也可能不相邻，且,uv,),，在,u,，,v,之间加新边,(u,，,v),，称为,加新边,，并用,G(u,，,v)(,或,G,(u,，,v),表示所得新图。,9.2,通路与回路,一通路与回路的定义,定义,9.11,设,G,为无向标定图，,G,中顶点与边的交替序列,=,称为 到 的,通路,，其中 ，,为,的端点，,r=1,，,2,，,，,l,，分别称为,的始点与终点，,中边的条数称为它的长度。若 ，则称通路为,回路,。若,的所有边各异，则称,为,简单通路,，又若 ，则称,为,简单回路,。若,的所有顶点,(,除 与 可能相同外,),各异，所有边也各异，则称,为,初级通路,或,路径,，此时又若 ，则称,为,初级回路,或,圈,。将长度为奇数的圈称为,奇圈,，长度为偶数的圈称为,偶圈,。,，,注意，在初级通路与初级回路的定义中，仍将初级回路看成初级通路,(,路径,),的特殊情况，只是在应用中初级通路,(,路径,),都是始点与终点不相同的，长为,1,的圈只能由环生成，长为,2,的圈只能由平行边生成，因而在简单无向图中，圈的长度至少为,3.,另外，若,中有边重复出现，则称,为,复杂通路,，又若 ，则称,为,复杂回路。,在有向图中，通路、回路及分类的定义与无向图中非常相似，只是要注意有向边方向的一致性。,在以上的定义中，将回路定义成通路的特殊情况，即回路也是通路，又初级通路,(,回路,),是简单通路,(,回路,),，但反之不真。,用顶点与边的交替序列定义了通路与回路，但还可以用更简单的表示法表示通路与回路。,只用边的序列表示通路,(,回路,),。定义,14.11,中的,可以表示成,(2),在简单图中也可以只用顶点序列表示通路,(,回路,),。定义中的,也可以表示成,.(3),为了写出非标定图中的通路,(,回路,),，可以先将非标定图标成标定图，再写出通路与回路。,(4),在非简单标定图中，当只用顶点序列表示不出某些通路,(,回路,),时，可在顶点序列中加入一些边,(,这些边是平行边或环,),，可称这种表示法为,混合表示法,。,二,.n,阶图中通路与回路的性质,定理,9.5,在,n,阶图,G,中，若从顶点,vi,到,vj,（,vivj,）存在通路，则从,vi,到,vj,存在长度小于或等于（,n-1,）的通路。,推论,在,n,阶图,G,中，若从顶点,vi,到,vj,（,vivj,）存在通路，则,vi,到,vj,一定存在长度小于或等于,n-1,的初级通路（路径）。,定理,9.6,在一个,n,阶图,G,中，若存在,vi,到自身的回路，则一定存在,vi,到自身长度小于或等于,n,的回路。,推论,在一个,n,阶图,G,中，若存在,vi,到自身的简单回路，则一定存在,vi,到自身长度小于或等于,n,的初级回路。,例,9.5,(1),无向完全图,Kn,（,n3,）中有几种非同构的圈？,(2),无向完全图,K3,的顶点依次标定为,a,b,c,.,在定义意义下,K3,中有多少个不同的圈？,解,(1),长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的，易知,Kn,（,n3,）中含长度为,3,，,4,，,，,n,的圈，所以,Kn,（,n3,）中有,n-2,种非同构的圈。,(2),在同构意义下，,K3,中只有一个长度为,3,的圈。但在定义意义下，不同起点（终点）的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，因而,K3,中有,6,个不同的长为,3,的圈：,abca,acba,bacb,bcab,cabc,cbac,。如果只考虑起点（终点）的差异，而不考虑顺时针逆时针的差异，应有,3,种不同的圈，当然它们都是同构的，画出图来只有一个。,9.3,图的连通性,一、无向图的连通性,定义,9.12,设无向图,G=,u,vV,，若,u,v,之,间存在通路，则称,u,v,是连通的,，记作,u,v,.,vV,，规定,v,v.,由定义不难看出，无向图中顶点之间的连通关系,=,（,u,v,）,|,u,vV,且,u,与,v,之间有通路,是自反的，对称的，传递的，因而是,V,上的等价关系。,定义,9.13,若无向图,G,是平凡图或,G,中任何两个顶点都是连通的，则称,G,为,连通图,，否则称,G,是,非连通图,或,分离图,。,易知，完全图,Kn(n1),都是连通图，而,零图,Nn(n2),都是分离图。,定义,9.14,设无向图,G=,，,V,关于顶点之间的连通关系的,商集,V/,=V1,V2,Vk,，,Vi,为,等价类,，称,导出子图,GVi(i,=1,2,k),为,G,的,连通分支,，连通分支数,k,常记为,p(G,).,由定义可知，若,G,为连通图，则,p(G,)=1,，若,G,为非连通图，则,p(G)2,，在所有的,n,阶无向图中，,n,阶零图是连通分支最多的，,p(Nn,)=n.,二、无向图中顶点之间的线程线及距离,定义,9.15,设,u,v,为无向图,G,中任意两个顶点，若,u,v,，称,u,v,之间长度最短的通路为,u,v,之间的,短程线,，短程线的长度称为,u,v,之间的,距离,，记作,d(u,v).,当,u,v,不连通时，规定,d(u,v)=.,距离有以下性质：,1,d(u,v)0,，,u=v,时，等号成立。,2,具有对称性，,d(u,v,)=,d(v,u,).3,满足三角不等式：,u,v,wV(G,),，则,d(u,v)+d(v,w)d(u,w,),在完全图,Kn(n2),中，任何两个顶点之间的距离都是,1,，而在,n,阶零图,Nn(n2),中，任何两个顶点之间的距离都为,.,三、无向图的连通度,定义,9.16,设无向图,G=,，若存在,V V,，且,V,，使得,p(G,-V),p(G,),，而对于任意的,V V,，均有,p(G,-V)=,p(G,),，则称,V,是,G,的,点割集,，若,V,是单元集，即,V=v,，则称,v,为,割点,。,见教材,P159,，在图,9.8,中，,v2,v4,，,v3,，,v5,都是点割集，而,v3,v5,都是割点。注意，,v1,与,悬挂顶点,v6,不在任何割集中。,定义,9.17,设无向图,G=,，若存在,E E,，且,E,，使得,p(G,-E),p(G,),，而对于任意的,E E,，均有,p(G,-E)=,p(G,),，则称,E,是,G,的,边割集,，或简称为割集。若,E,是单元集，即,E=e,，则称,e,为,割边,或,桥,。,在图,9.8,中，,e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4,都是割集，其中,e6,e5,是桥。,定义,9.18,设,G,为无向连通图且为非完全图，则称,(G,)=,min|V|V,为,G,的点割集,为,G,的,点连通度,，简称,连通度,。规定完全图,Kn(n1),的点连通度为,n-1,，又规定非连通图的点连通度为,0.,又若,(G)k,，则称,G,是,k-,连通图,，,k,为非负整数。,(G,),有时简记为,.,图,14.8,中图的点连通度为,1,，此图为,1-,连通图。,K5,的点连通度,=4,，所以,K5,是,1-,连通图，,2-,连通图，,3-,连通图，,4-,连通图。图,9.7,中，（,1,）图的点连通度,=2,，所以它是,1-,连通图，也是,2-,连通图。若,G,是,k-,连通图（,k1,）则在,G,中删除任何,k-1,个顶点后，所得图一定还是连通的。,定义,9.19,设,G,是无向连通图，称,(G,)=,min|E,|E,是,G,的点割集,为,G,的,边连通度,。规定非连通图的边连通度为,0.,又若,(G)r,，则称,G,是,r,边,-,连通图,。若,G,是,r,边,-,连通图，则在,G,中任意删除,r-1,条边后，所得图依然是连通的。完全图,Kn,的边连通度为,n-1,，因而,Kn,是,r,边,-,连通图，,0rn-1.,图,14.8,中图的边连通度,=1,，它只能是,1,边,-,连通图。,(G,),也可以简记为,.,设,G1,G2,都是,n,阶无向简单图，若,(G1)(G2),，则称,G1,比,G2,的点连通程度高。若,(G1)(G2),，则称,G1,比,G2,的边连通程度高。,定义,9.20,设,D=,为一个有向图。,vi,vjV,，若从,vi,到,vj,存在通路，则称,vi,可达,vj,，记作,vivj,，规定,vi,总是可达自身的，即,vivi,.,若,vivj,且,vjvi,，则称,vi,与,vj,是,相互可达,的，记作,vi,vj,.,规定,vi,vi,.,与 都是,V,上的二元关系，并且不难看出 是,V,上的等价关系。,定义,9.21,设,D=,为有向图，,vi,vjV,，若,vivj,，称,vi,到,vj,长度最短的通路为,vi,到,vj,的,短程线,，短程线的长度为,vi,到,vj,的距离，记作,d.,与无向图中顶点,vi,与,vj,之间的距离,d(vi,vj,),相比，,d,除无对称性外，具有,d(vi,vj,),所具有的一切性质。,定义,9.22,设,D=,为一个有向图。若,D,的,基图,是连通图，则称,D,是,弱连通图,，简称为,连通图,。若,vi,vjV,，,vivj,与,vjvi,至少成立其一，则称,D,是,单向连通图,。若均有,vi,vj,，则称,D,是,强连通图,。,见教材,P161,，在图,9.11,中，（,1,）为强连通图，（,2,）为单连通图，（,3,）是弱连通图。由定义可知，强连通图一定是单向连通图，单向连通图一定是弱连通图。,定理,9.8,设有向图,D=,，,D=v1,v2,vn.D,是强连通图当且仅当,D,中存在经过每个顶点至少一次的回路。,定理,9.9,设,D,是,n,阶有向图，,D,是单向连通图当且仅当,D,中存在经过每个顶点至少一次的通路。,五、扩大路径法及极大路径,设,G=,为,n,阶无向图，,E,，设,I,为,G,中一条路径，若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来，继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止，设最后得到的通路的两个端点不与通路外的顶点相邻为止，设最后得到的路径为,l+k,（长度为,l,的路径扩大成了长度为,l,+k,的路径），称,l+k,为“,极大路径,”，称使用此种方法证明问题的方法为“,扩大路径法,”。（,演示,）,六、二部图及判别定理,定义,14.23,设,G=,为一个无向图，若能将,V,分成,V1,和,V2,（,V1V2=V,V1V2=,），使得,G,中的每条边的两个端点都是一个属于,V1,，另一个属于,V2,，则称,G,为,二部图,（或称二分图，偶图等），称,V1,和,V2,为互补顶点子集，常将二部图,G,记为,.,又若,G,是简单二部图，,V1,中每个顶点均与,V2,中所有顶点相邻，则称,G,为,完全二部图,，记为,Kr,s,，其中,r=|V1|,s=|V2|.,注意，,n,阶零图为二部图。,在图,14.13,中所示各图都是二部图，其中，,(1),，,(2),，,(3),为,K6,的子图，,(3),为完全二部图,K,3,3,，常将,K,3,3,画成与其同构的,(5),的形式，,K,3,3,是下文中经常遇到的图。,(4),是,K5,的子图，它是完全二部图,K,2,3,，,K,2,3,常画成,(6),的形式。,习题课,主要内容：,1,、通路与回路的定义。,2,、,n,阶图中通路与回路的性质。,学习要求：,1.,深刻理解通路与回路的定义及其分类。,2.,能正确地使用不同的表示法表示通路与回路。,3.,理解同构意义下与定义意义下通路与回路的区别与联系。,4.,深刻理解无向图中两个顶点之间的连通关系、短程线、距离、图的连通性等概念。,5.,深刻理解点割集、边割集、点连通度、边连通度等概念。,6.,理解有向图中，顶点之间的可达、相互可达关系、短程线、距离等概念。,7.,深刻理解有向图的连通性及分类，以及判别定理。,1,、设无向图,G,中只有两个奇度顶点,u,与,v,，试证明,u,与,v,必连通。,用反证法。假设,u,与,v,不连通，即,u,与,v,之间无通路，则,u,与,v,处于,G,的不同连通分支中。不妨设,u,在,G1,，,v,在,G2,中。于是，,G1,与,G2,作为,G,的子图，他们中均只含有一个奇度顶点，这与握手定理的推论矛盾。,2.,设,n,阶无向简单图,G,有,m,条边，已知,m (n-1)(n-2)+1,，证明,G,必连通。,证明：,（,1,）任何,n,阶简单图的 边数,m,均小于等于完全图,Kn,的边数,n(n-1),。,（,2,）若,G,中无孤立点，则,(G)1,。用归纳法。,n=1,时，,G,为平凡图，显然,G,连通。,n=2,时，,m (n-1)(n-2)+1=1,，此时,G,为,K2,，当然连通。设,n=k(k2),，,m (k-1)(k-2)+1,时结论成立，要证明当,n=k+1,m k(k-1)+1,时结 论也成立。,(i),若,G,为,K,k+1,，,G,当然连通。,(ii),若,G,中含孤立点，一定推出矛盾。删去,G,中的孤立点，记作,G1,。则,G1,的边数,m k(k-1)+1,，这与,G1,为阶数小于等于,k,的简单图矛盾，故,G,中不可能含孤立点。,(iii),由,(i),、,(ii),可知，只需对,G,不为完全图、又不含孤立点的情况加以证明。,G,中存在,v,0,，使,1d(v,0,)k-1,（,G,中无孤立点，又不是,k+1,阶完全图），令,G=G-v,0,，则,G,为,k,阶简单图，且,G,的边数,m k(k-1)+1-(k-1)=(k(k-1)-(k-1)+1=(k-1)(k-2)+1,由归纳假设可知，,G,是连通图，而,G,为,G,的子图，故,G,也连通。,3,、设,G,为,n,阶无向简单图，证明以下题目：,（,1,）当,(G,),时，证明,G,连通。,证明（,1,）要用到,n,阶简单图的,最大度,n-1,。用反证法。假设,G,至少有两个连通分支，设,G1,G2,为其中的两个，并设,G1,G2,的阶 数分别为,n1,和,n2,，则,n1+n2n,，,minn1,n2,。于是，对任意的,vV(G1),，,dG1(V)=,dG(V,)-1,，这与,(G,),矛盾，所以,G,连通。,（,2,）当,(G,)(n+k-1),时，证明,G,是,k-,连通图。,利用（,1,）的结果。要证明,G,是,k-,连通图，只需证明从,G,中删除任意（,k-1,）个顶点后，所得图依然连通。,证明：设,V,为,V(G),的任意子集，且,|V|=k-1,。令,G=G-V,，则,G,为,n-(k-1)=n-k+1=n,阶无向简单图，而,(G)(G)-(k-1),(n+k-1)-(k-1),=(n+k-1-2k+2),=(n-k+1),=n,由当,(G,),时，,G,连通可知，,G,连通，故,G,为,k-,连通图。,9.4,图的矩阵表示,一、无向图与有向图的关联矩阵,图可以用集合来定义，但多半用图形来表示，此外，还可以用矩阵来表示图。用矩阵表示图，便于用代数方法研究图的性质，也便于计算机处理图。用矩阵表示图之前，必须将图的顶点或边标定顺序，使其成为标定图。本节中主要讨论无向图及有向图的关联矩阵及有向图的邻接矩阵和可达矩阵。,定义,14.24,设无向图,G=,，,V=v,1,v,2,v,n,，,E=e,1,e,2,e,m,，令,m,ij,为顶点,v,i,与边,e,j,的关联次数，则称,(,m,ij,),nm,为,G,的,关联矩阵,，记作,M(G).,图,14.14,所示无向图的,关联矩阵为,M(G)=,不难看出，关联矩阵,M(G),有以下性质：,1,M,ij,=2(j=1,2,m),即,M(G),每列元素之和均为,2,，这正说明每条边关联两个顶点（环所关联的两个端点重合）。,2,M,ij,=d(v,i,),，即,M(G),第,i,行元素之和为,v,i,的度数，,i=1,2,n.,3,d(v,i,)=,m,ij,=,m,ij,=2=2m,这个结果正是,握手定理,的内容，即各顶点的度数之和等于边数的,2,倍。,4,第,j,列与第,k,行相同，当且仅当边,e,j,与,e,k,是,平行边,。,5,M,ij,=0,当且仅当,v,i,是,孤立点,。,定义,14.25,设有向图,D=,中无环，,V=v,1,v,2,v,n,，,E=e,1,e,2,e,m,令,m,ij,=,则称,(,m,ij,),nm,为,D,的,关联矩阵,，记作,M(D).,图,14.15,所示图,D,的关联矩阵为,M(D)=,图,14.15,M(D),有如下各条性质：,1,m,ij,=0,，,j=1,2,m,，从而,m,ij,=0,，这说明,M(D),