图论课件--邻接谱与图的邻接代数.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,图论及其应用,应用数学学院,1,第一章 图的基本概念,本次课主要内容,邻接谱与图的邻接代数,(,一,),、邻接谱,(,二,),、图的邻接代数,(,三,),、图空间简介,2,(,一,),、邻接谱,1,、图的特征多项式,定义,1,：图的邻接矩阵,A(G),的特征多项式：,称为图,G,的特征多项式。,例,1,、设单图,G,的特征多项式为：,求证,:(,1)a,1,=0;(2)a,2,=m(G);,(,3)a,3,是,G,中含有不同的,K,3,子图的个数,2,倍。,3,证明：由矩阵理论：对每个,1,i,n,(-1),i,a,i,是,A(G),的所有,i,阶主子式之和。,(1),由于,A(G),的主对角元全为零，所以所有,1,阶主子式全为零，即：,a,1,=0;,这样的一个,2,阶主子式对应,G,中的一条边，反之亦然，所以，有：,(2),对于单图,G,A(G),中非零的,2,阶主子式必为如下形式：,4,这样的一个,3,阶主子式对应,G,中的一个,K,3,，反之亦然,.,设,G,中有,S,个,K,3,则：,(3),对于单图,G,A(G),中非零的,3,阶主子式必为如下形式：,事实上，有如下一般性定理：,(,见李蔚萱，,图论,，湖南科学技术出版社，,1980,年,4,月,),5,定理,1,：图,G,的特征多项式的系数：,其中，,s(G,H),表示,G,的同构于,H,的导出子图的数目。,右边对所有,i,阶图,H,求和。,2,、图的邻接谱,定义,2,：图的邻接矩阵,A(G),的特征多项式的特征值及其重数，称为,G,的邻接谱。,例,2,、求出,K,n,的谱。,解：,K,n,的邻接矩阵为：,6,于是：,7,所以：,例,3,，若两个非同构的图具有相同的谱，则称它们是同谱图。求证：下面两图是同谱图。,G,H,8,证明：,G,与,H,显然不同构。,通过直接计算：,所以,G,与,H,是同谱图。,例,4,，设单图,A(G),的谱为：,则：,证明：由矩阵理论：,9,a,ii,(2),表示点,v,i,的度数，由握手定理：,即：,例,5,，设,是,单图,G=(n,m),的任意特征值，则：,证明：不失一般性，设,=,1,，,2,，,n,是,G,的全体特征值。,G,是,单图，有：,10,又由例,4,，有：,对向量,(1,1,1),与,(,2,3,4,n,),用柯西不等式得：,所以，有：,由,(1),与,(2),得：,11,注：对于图谱的研究，开始于二十世纪,60,年代。形成了代数图论的主要研究方向之一。图谱研究在流体力学，量子化学里有重要的应用。国内，中国科技大学数学系是最早展开该课题研究的单位,(1978,年就有很好的研究成果,),。他们对图论的研究主要有两个方面：一是图谱问题，二是组合网络研究，也有达到国际水平的研究成果,(1994,年开始,).,关于组合网络问题，将在第三章作一些介绍。,12,(,二,),、图的邻接代数,1,、图的邻接代数的定义,定义,3,：设,A,是无环图,G,的邻接矩阵，称：,对于矩阵的加法和数与矩阵的乘法来说作成数域,C,上的向量空间，称该空间为图,G,的邻接代数。,注：向量空间的定义可简单地记为“非空”、“两闭”、,“八条”,2,、图的邻接代数的维数特征,13,定理,1,：,G,为,n,阶连通图，则：,证明：由哈密尔顿,凯莱定理,(,见北大数学力学系,高等代数,),：,所以：,下面证明：,E,A,A,2,A,d(G),线性无关！,若不然，则存在不全为零的数,a,0,a,1,a,d(G),使：,14,设,a,m-1,0,但当,k m,时，有,a,k,=0.,于是有：,假定：,v,1,v,2,v,d(G)+1,是,G,中一条最短的,(v,1,v,d(G)+1,),路，易知：,d(G)n.,于是，,d(v,1,v,m,)=m-1,(m=1,2,d(G)+1),注意到：,A,k,的元素,a,1m,(k),在,k 0,所以，的一行,m,列元为,a,m-1,a,1m,(m-1),0,，这样有：,15,产生矛盾！,定理结果分析：不等式右端的界是紧的！,因为：,n,点路的直径为,n-1,所以，此时该路的邻接代数的维数正好为,n,。,此外：当,G,为,K,n,时，有：,例,6,，设,G,为,n,阶连通图，则,G,的不同特征值的个数,S,满足：,16,证明：,S,n,是显然的！,由矩阵理论知：对称矩阵的不同特征值的个数等于其最小多项式的次数，而最小多项式的次数等于,G,的邻接代数的维数，所以：,注,:(1)n,点路的不同特征值有,n,个；,(2)K,n,的不同特征值有,2,个。,17,定理,2,：集合：,对于图的对称差运算和数乘运算：,(,三,),、图空间简介,来说作成数域,F=,0,1,上的,m,维向量空间。,注：图空间概念是网络图论中的一个基本概念。研究通信网络，如果要用图论方法，建议参看陈树柏的,网络图论及其应用,，科学出版社，,1982,年。学习网络图论的主要基础是电工学与矩阵理论知识。,18,证明,:(1),证明,M,是,F,上的向量空间，只需要验证“两闭”与“八条”即可。,(2)M,的维数为,m,令,又令：,可以证明：,g,1,g,2,g,m,为,M,的一组基！,事实上：对,若,E(G,i,)=e,i1,e,i2,e,ik,则：,19,另一方面：若,则：,c,1,=c,2,=,=c,m,=0,所以：,20,作业,设,G,是一个,r,度正则图，证明：,r,是,G,的的一个特征值；,(2),特征值,r,的重数等于,G,的连通分支数；,(3)G,的任意特征值,满足：,21,Thank You!,22,