离散数学图论-图的基本概念

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,图 论,图的基本概念,七座桥所有的走法一共,有,7,！,=5040,种。,1736,年，在经过一年的研究之后，,29,岁的欧拉提交了,哥尼斯堡七桥,的论文，圆满解决了这一问题，同时开创了数学,新分支,-,图论,。,图 论,在,许多应用领域中,：地图导航、,网络技术研究及程序流程分析都会,遇到由,“结点”和“边”组成的,图,在,计算机许多学科中如：数据结构、操作系统、网络理论、信息的组织与检索均离不开由这种“,结点”和“边”组成的图,以及图的特殊形式-树,。,图,与树是建立和处理离散对象及其,关系重要,工具。,如地图导航、,周游问题,、图像分割等等,。,一、图的,概念,1,、,无序积,定义：设,A,，,B,为任意的两个集合，,称 ,a,，,b,aAbB,为,A,与,B,的无序积，记作,A&B,其元素,a,，,b,可简记为,（,a,，,b,）,2,、图的定义,1,）定义,1,一个,无向图,是一个有序的二元组,，记作,G,，其中,(1),V,称为顶点集，其元素称为,顶点,或,结点,(2),E,称为边集,，它是,无序积,V,V,的,多重子集,，其元素称为,无向边,，,简称为,边,例：,无向图,G=,其中 顶点集合,V,v1,v2,v3,v4,边集合,E,(v1,v2),(v2,v3),(v3,v2),(v3,v1),(v2,v2),(v2,v2),(v1,v2),园括号表示无向边,有平行边,2,）定义,2,一个,有向图,是一个有序的二元组,，记作,D,，其中,(1)V,称为顶点集，其元素称为顶点或结点,(2)E,为边集，,它是笛卡儿积,V,V,的有穷多重子集,，其元素称为,有向边,，简称,边,(,弧,),有向图,D=,其中,V,v1,v2,v3,边集合,E,（与前面的关系的图表示相当）,3,、有关图的术语,1,）用,G,表示无向图，,D,表示有向图。,有时,用,V(G),，,E(G),分别表示,G,的顶点集和边集。,2,）用,|V(G)|,，,|E(G)|,分别表示,G,的顶点数和边,数,若,V(G),n,，则称,G,为,n,阶图,。对,有向图有相同定义。,3,）在图,G,中，若,边集,E(G),，则称,G,为,零图,若,G,为,n,阶图，则称,G,为,n,阶零图,，记作,N,n,，特别是称,N,1,为,平凡图,4,）在用图形表示一个图时，若给每个结点和每一条边均指定一个符号（字母或数字），则称这样的图为,标定,图。,5),常用,e,k,表示边,(v,i,，,v,j,)(,或,),设,G,为无向图，,e,k,=(v,i,，,v,j,)E,，,则,称,v,i,，,v,j,为,e,k,的端点,，,e,k,与,v,i,、,v,j,是彼此,相关联的,起、终点,相同的边称为,环,不,与任何边关联的结点称为,孤立点,（包括有向图,),6,）邻接：,边的相邻,：,e,k,，,e,l,E,若,e,k,与,e,l,至少有一个公共端点，,则称,e,k,与,e,l,是相邻的,顶点的相邻,：若,e,t,E,，使得,e,t,=,，,则称,v,i,为,e,t,的始点，,v,j,为,e,t,的终点，,并称,v,i,邻接到,v,j,，,v,j,邻接于,v,i,两个结点为一条边的端点，则称两个结点,互为邻接点,，,也称,边关联于这两个结点,，或称两个结点邻接于此边,。,7,）平行边：,在无向图中，关联一对顶点的无向边如果多于,1,条，则称这些边为,平行边,，平行边的条数称为,重数,在,有向图中，关联一对顶点的有向边如果多于,1,条，,并且它们,的,方向,相同,，,则称这些边为,平行边,8,）多重图和简单图：,含平行边的图称为多重图,既,不含平行边也不含环的图称为,简单图,（主要讨论简单图,）,4,、结点的度,1,),定义,4,设,G,为无向图，,v V,，称,v,作为边的端点的次数之和,为,v,的,度数,，简称为,度,，记作,d,G,(v),，,简记为,d(v),，,即为：结点,v,所关联的边的总条数,关于有向图,D,有：,vV,，称,v,作为边的,始点的次数之和,为,v,的,出度,，记作,d,+,(v),，,称,v,作为边的,终点,的次数之和为,v,的,入度,，记作,d,-,(v),称,d,+,(v)+d,-,(v),为,v,的度数，记作,d,D,(v).,2),称度数为,1,的顶点为,悬挂顶点,，与它关联的边称为,悬挂边,根据结点的度数可将结点分为：,度为偶数,(,奇数,),的顶点称为,偶度,顶点,(,奇度顶点,).,一个环提供的度为,2,（有向图的环提供入度,1,和出度,1,）,3,）定义：,(G)=maxd(v)|vV(G),为图,G,中结点最大的度,(G)=mind(v)|vV(G),为图,G,中结点最小的度,简记为,、,定义：,(D)=maxd,(v)|vV(D),为图,D,中结点最大,的,入,度,(D)=maxd,(v)|vV(D),为图,D,中结点最大的,出,度,-,(D)=mind,(v)|vV(D),为图,D,中结点最小,的,入,度,(D)=mind,(v)|vV(D),为图,D,中结点最小的,出,度,5,、握手定理（欧拉）,1),定理,1,设,G,为任意无向图,V,v,1,，,v,2,，,，,v,n,E,=m,，,则,d(v,i,),2m,(,所有结点的度数值和为边数的,2,倍,),证,:G,中每条边,(,包括环,),均有两个端点，所以在计算,G,中各顶点度数之和时，每条边均提供,2,度，当然，,m,条边共提供,2m,度,2),定理,2,设,D,为任意有向图,V,v,1,，,v,2,，,，,v,n,|E|=m,，,则,d,+,(v,i,)=,d,-,(v,i,)=m,且,d(v,i,),2m,3),推论 任何图,(,无向的或有向的,),中，,奇度顶点,的,个数,是,偶数个,4),结点的度数序列,(1),设,G,为一个,n,阶无向图，,V,v,1,，,v,2,，,，,v,n,称,d(v,1,),，,d(v,2,),，,，,d(v,n,),为,G,的,度数列,注：由推论可知，不是任何一个非负整数序列均可作为一个图的度数列。,条件：,奇度数,的结点个数应该是,偶数个,（,2,）序列的可图化,：对一个整数,序列,d=(d,1,d,2,d,n,),若存在以,n,个顶点的,n,阶无向图,G,，有,d(v,i,)=d,i,，称该序列是,可图化的。,特别的，如果得到的是简单图，称该序列是,可简单图化的。,（,3,）定理,设非负整数列,d,(d1,，,d2,，,，,dn),，则,d,是可图化的,当且仅当,d,i,是偶数,(,序列之和必须是偶数,),（,4,）由于简单图中没有平行边及环,定理：设,G,为任意,n,阶无向,简单图,，则,(G,)d,2,d,n,=1,且,d,i,=,偶数,d4=,（,3,3,3,1,）,分析,d5=,（,4,4,3,3,2,2,）,二、图的同构,定义：设,G1,，,G2=,为两个无向图,(,有向图,),，,若存在双射函数,f,：,V1 V2,对于,vi,，,vj,V1,，,(vi,，,vj),E1,当且仅当,(f(vi),f(vj),E2,并且,(vi,，,vj),与,(f(vi),f(vj,),的重数相同，则称,G1,与,G2,是,同构,的，记作,Gl G2,。,对有向图有相同的定义。,定义说明了,:,两个图的各结点之间，如果存在着一一对应关系,f,这种对应关系又保持了,结点间的邻接关系,，,那么这两个图就是同构的,在有向图的情况下，,f,不但应该保持结点间的邻接关系，还应该,保持边的方向。,结点数相同边数相同,结点的度相同,但是两个图,不同构,注,：,1,),两个图同构的必要条件,阶数相同,（顶点）,边数相同,度数相同的顶点数相同,同构,的,必要条件，并不是充分条件,2,),图之间的,同构关系,可看成全体图集合上的二元,关系。,具有,自反性，对称性和传递性，,是,等价关系。,同构,的图为一个等价类，在,同构的意义之下都可以看成是一个图。,例,(1),画出,4,阶,3,条边的所有非同构的,无向简单图,结点个数,与,边数相同,，只需找出,顶点度数序列不同,的图（,2,3,6,）,如何将度数,6,分配给,4,个结点：,1 1 1 3,相应的图,2 2 1 1,2 2 2 0,例,(2),画出,3,阶,2,条边的所有非同构的,有向简单图,结点个数与边数相同，只需找出,顶点度（出度及入度）数序列不同,的图,结点总度数：,2,2,4,度数分配,1 2 1,按出度与入度分配：,入度列,1 1 0,出度列,0 1,1,入度列,0 2 0,出度列,1 0,1,入度列,1 0 1,出度列,0 2 0,度数分配,2 2 0,按出度与入度分配：,入度列,1 1 0,出度列,1 1 0,这只是对较为简单的情况给出的非同构图，对于一般的情况（,n,m),图到目前为止还没有解决,三、特殊图完全图与正则图,1,),完全图,定义 设,G,为,n,阶无向,简单图,，若,G,中每个顶点均与其余的,n,1,个顶点相邻，则称,G,为,n,阶无向完全图，简称,n,阶完全图,，记作,Kn,(n1),设,D,为,n,阶有向简单图，若,D,中每个顶点都,邻接到,其余的,n,1,个顶点，又,邻接于,其余的,n,1,个顶点，则称,D,是,n,阶,有向完全图,可画图表示（无向图,5,阶、有向图,3,阶和,4,阶）,2),完全图的性质：,n,阶无向完全图,G,的边数与结点的关系,m=,n(n-1)/2,n,阶有向完全图,G,的边数与结点的关系,m=,n(n-1),2,3,),正则图,定义,设,G,为,n,阶无向,简单图,，若,v,V(G),，均有,d(v),k,则,称,G,为,k-,正则图,k-,正则图的边数与结点个数的关系,：,m=k n/2,如,：,3-,正则图,四、子图、生成子图、导出子图,1,、定义 设,G,，,G,为两个图,(,同为无向图或有向图,),若,V,V,且,E,E,，则称,G,是,G,的,子图,，,G,为,G,的母图，记作,G,G,，,又,若,V,V,或,E,E,，则称,G,为,G,的,真子图,若,V,V,（且,E,E,），,则称,G,为,G,的,生成子图,(,全部顶点,),2,、设,G,为图，,V1V,且,V1,，称以,V1,为顶点集，以,G,中,两个端点都在,V1,中的边,组成边集,E1,的图为,G,的,V1,导出的子图,，,记作,GV1,可画图表示,G,及,G,V1,（,P279,图,14.5,）,结点导出的子图,又设,E1 E,且,E1,，称以,E1,为边集，以,E1,中边关联的顶点为顶点集,V1,的图为,G,的,E1,导出的子图,，记作,GE1,