离散数学--6.1图的基本概念.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第6章 图,1,第6章 图,6.1 图的基本概念,6.2 图的连通性,6.3 图的矩阵表示,6.4 几种特殊的图,2,6.1,图的基本概念,6.1.1 无向图与有向图,6.1.2 顶点的度数与握手定理,6.1.3 简单图、完全图、正则图、圈图、,轮图、方体图,6.1.4 子图、补图,6.1.5 图的同构,3,无序对与多重集合,无序对,:2个元素构成的集合,记作(,a,b,),无序积,:,A,B,=(,x,y,)|,x,A,y,B,例如,A,=,a,b,c,B,=1,2,A,B,=,B,A,=(,a,1),(,b,1),(,c,1),(,a,2),(,b,2),(,c,2),A,A,=(,a,a,),(,a,b,),(,a,c,),(,b,b,),(,b,c,),(,c,c,),B,B,=(1,1),(1,2),(2,2),多重集合,:元素可以重复出现的集合,重复度,:元素在多重集合中出现的次数,例如,S,=,a,b,b,c,c,c,a,b,c,的重复度依次为1,2,3,4,无向图,定义6.1 无向图,G,=,其中,V,称为,顶点集,其元素称为,顶点,或,结点,;,E,是,V,V,的多重子集,称为,边集,其元素称为,无向边,，简称,边,.有时用,V,(,G,),和,E,(,G,),分别表示,V,和,E,例如,G,=,如图所示,其中,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,),e,1,e,2,e,3,e,4,e,5,e,6,e,7,v,5,v,1,v,2,v,3,v,4,5,有向图,定义6.2 有向图,D,=,其中,V,称为,顶点集,其元素称为,顶点,或,结点,;,E,是,V,V,的多重子集,称为,边集,其元素称为,有,向边,，简称,边,.有时用,V,(,D,),和,E,(,D,),分别表示,V,和,E,有限图,:,V,E,都是有穷集合的图,n,阶图,:,n,个顶点的图,零图,:,E,=,的图,平凡图,:1 阶零图,e,1,e,2,e,3,e,4,e,5,e,6,e,7,d,a,b,c,6,顶点和边的关联与相邻,设无向图,G,=,e,k,=,(,v,i,v,j,),E,称,v,i,v,j,为,e,k,的,端点,e,k,与,v,i,(,v,j,),关联,.若,v,i,=,v,j,则称,e,k,为,环,.无边关联的顶点称作,孤立,点,.若,v,i,v,j,则称,e,k,与,v,i,(,v,j,),的,关联次数为1,;若,v,i,=,v,j,则称,e,k,与,v,i,的,关联次数为2,;若,v,i,不是边,e,的端点,则称,e,与,v,i,的,关联,次数为0,.,设,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,是,e,k,的,始点,v,j,是,e,k,的,终点,v,i,邻接到,v,j,v,j,邻接于,v,i,7,顶点的度数,设,G,=,为无向图,v,V,v,的度数(度),d,(,v,),:,v,作为边的端点次数之和,悬挂顶点,:度数为1的顶点,悬挂边,:与悬挂顶点关联的边,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,v,4,是悬挂顶点,e,7,是悬挂边,e,1,是环,e,1,e,2,e,3,e,4,e,5,e,6,e,7,v,5,v,1,v,2,v,3,v,4,8,顶点的度数(续),设,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,+,(,a,)=4,d,-,(,a,)=1,d,(,a,)=5,d,+,(,b,)=0,d,-,(,b,)=3,d,(,b,)=3,+,=4,+,=0,=3,=1,=5,=3,e,1,e,2,e,3,e,4,e,5,e,6,e,7,d,a,b,c,9,握手定理,定理6.1,任何图(无向图和有向图)的所有顶点度数之和都,等于边数的2倍.,证 图中每条边(包括环)均有两个端点,所以在计算各顶点,度数之和时,每条边均提供2度,m,条边共提供2,m,度.,推论,任何图(无向图和有向图)都有偶数个奇度顶点,定理6.2,有向图所有顶点的入度之和等于出度之和等于边数,证 每条边恰好提供1个入度和1个出度,10,图的度数列,设无向图,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,e,1,e,2,e,3,e,4,e,5,e,6,e,7,v,5,v,1,v,2,v,3,v,4,e,1,e,2,e,3,e,4,e,5,e,6,e,7,d,a,b,c,11,实例,(2)能,例1,下述2组数能成为无向图的度数列吗?,(1)3,3,3,4;(2)1,2,2,3,解,(1),不可能.有奇数个奇数.,12,实例,例2,已知图,G,有10条边,4个3度顶点,其余顶点的度数均小,于等于2,问,G,至少有多少个顶点?,解,设,G,有,n,个顶点.由握手定理,4,3+2(,n,-4)210,解得,n,8,例3,已知5阶有向图的度数列和出度列分别为3,3,2,3,3和,1,2,1,2,1,求它的入度列,解 2,1,1,1,2,13,实例,例4,证明不存在具有奇数个面且每个面都具有奇数条棱的,多面体.,证 用反证法.假设存在这样的多面体,作无向图,G,=,其中,V,=,v,|,v,为多面体的面,E,=(,u,v,)|,u,v,V,u,与,v,有公共的棱,u,v,.,根据假设,|,V,|,为奇数且,v,V,d,(,v,),为奇数.这与握手定理的推论矛盾.,14,实例,例5,设9阶无向图的每个顶点的度数为5或6,证明它至少有,5个6度顶点或者至少有6个5度顶点.,证 讨论所有可能的情况.设有,a,个5度顶点和,b,个6度顶点,(1),a,=0,b,=9;,(2),a,=2,b,=7;,(3),a,=4,b,=5;,(4),a,=6,b,=3;,(5),a,=8,b,=1,(1)(3),至少,5个6度顶点,(4)和(5)至少6个5度顶点,方法二 假设,b,9-5=4.,由握手定理的推论,a,6,15,简单图,定义6.4,在无向图中,关联同一对顶点的2条或2条以上的,边,称为,平行边,平行边的条数称为,重数,在有向图中,具有相同始点和终点的2条或2条以上的边称,为,有向平行边,简称,平行边,平行边的条数称为,重数,含平行边的图称为,多重图,既无平行边也无环的图称为,简单图,16,实例,e,5,和,e,6,是平行边,重数为2,不是简单图,e,2,和,e,3,是平行边,重数为2,e,6,和,e,7,不是平行边,不是简单图,e,1,e,2,e,3,e,4,e,5,e,6,e,7,v,5,v,1,v,2,v,3,v,4,e,1,e,2,e,3,e,4,e,5,e,6,e,7,d,a,b,c,17,完全图与正则图,无向完全图,:,每对顶点之间都有一条边的无向简单图.,n,阶无向完全图记作,K,n,顶点数,n,边数,m,=,n,(,n,-1)/2,=,=,n,-1,有向完全图,:每对顶点之间均有两条方向相反的边的有向简单图.,顶点数,n,边数,m,=,n,(,n,-1),+,=,+,=,-,=,-,=,n,-1,=,=2(,n,-1),k-,正则图,:每个顶点的度数均为,k,的无向简单图,顶点数,n,边数,m,=,kn,/2,18,实例,K,3,K,5,3,阶有向完全图,2,正则图,4,正则图,3,正则图,彼得松图,19,圈图与轮图,无向圈图,C,n,=,其中,V,=,v,1,v,2,v,n,E,=(,v,1,v,2,),(,v,2,v,3,),(,v,n,-1,v,n,),(,v,n,v,1,),n,3,有向圈图,C,n,=,其中,V,=,v,1,v,2,v,n,E,=,n,3,轮图,W,n,:,无向圈图,C,n,-1,内放一个顶点,且与圈图的每个顶点之间恰有一条边,n,4,20,方体图,n,方体图,Q,n,=,是2,n,阶无向简单图,其中,V,=,v,|,v=a,1,a,2,a,n,a,i,=0,1,i,=1,2,n,E,=(,u,v,)|,u,v,V,u,与,v,恰好有一位数字不同.,0,1,00,01,10,11,000,001,010,011,110,100,111,101,21,子图,定义6.10,设,G,=,G,=,是2个图(同为无向图,或,同为有向图),若,V,V,且,E,E,则称,G,为,G,的,子图,G,为,G,的,母图,记作,G,G,若,G,G,且,V,=,V,则称,G,为,G,的,生成子图,若,V,V,或,E,E,称,G,为,G,的,真子图,设,V,V,且,V,以,V,为顶点集,以两端点都在,V,中的所有,边为边集的,G,的子图称作,V,的导出子图,记作,G,V,设,E,E,且,E,以,E,为边集,以,E,中边关联的所有顶点为,顶点集的,G,的子图称作,E,的导出子图,记作,G,E,22,实例,(1),(2),(3)是(1)的子图,(2),(3)是真子图,(1)是母图.,(1),(3)是(1)的生成子图.,(2)是,d,e,f,的导出子图,也是,e,5,e,6,e,7,导出子图.,(3)是,e,1,e,3,e,5,e,7,的导出子图,a,a,b,b,c,c,d,d,d,e,e,e,f,f,f,e,1,e,1,e,2,e,3,e,3,e,4,e,5,e,5,e,5,e,6,e,6,e,7,e,7,e,7,(1),(2),(3),23,补图,定义6.11,设,G,=,为,n,阶无向简单图,记 =,V,V,-E,称 为,G,的,补图,24,图的同构,定义6.12,设,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,(,v,j,),E,2,(,E,2,),并且(,v,i,v,j,)(),与(,f,(,v,i,),f,(,v,j,)(),的重数相同，,则称,G,1,与,G,2,是,同构,的，记作,G,1,G,2,.,25,实例,26,实例,例6,画出4阶3条边的所有非同构的无向简单图,解 总度数为6,分配给4个顶点,最大度为3,且奇度顶点数,为偶数,有下述3个度数列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.,1,1,1,3,1,1,2,2,0,2,2,2,27,实例,例7,画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图,28,