图论邻接谱与图的邻接代数精.ppt

《图论邻接谱与图的邻接代数精.ppt》由会员分享，可在线阅读，更多相关《图论邻接谱与图的邻接代数精.ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、图论课件邻接谱与图的邻接代数1 1第1页，本讲稿共22页第一章第一章 图的基本概念图的基本概念本次课主要内容本次课主要内容邻接谱与图的邻接代数邻接谱与图的邻接代数(一一)、邻接谱、邻接谱(二二)、图的邻接代数、图的邻接代数(三三)、图空间简介、图空间简介2第2页，本讲稿共22页(一一)、邻接谱、邻接谱1、图的特征多项式、图的特征多项式定义定义1：图的邻接矩阵：图的邻接矩阵A(G)的特征多项式：的特征多项式：称为图称为图G的特征多项式。的特征多项式。例例1、设单图、设单图G的特征多项式为：的特征多项式为：求证求证:(1)a1=0;(2)a2=m(G);(3)a3是是G中含有不同的中含有不同的K3

2、子图的个数子图的个数2倍。倍。3第3页，本讲稿共22页证明：由矩阵理论：对每个证明：由矩阵理论：对每个1in,(-1)n,(-1)i ia ai i是是A(G)A(G)的所有的所有i i阶阶主子式之和。主子式之和。(1)由于由于A(G)的主对角元全为零，所以所有的主对角元全为零，所以所有1阶主子式阶主子式全为零，即：全为零，即：a1=0;这样的一个这样的一个2阶主子式对应阶主子式对应G中的一条边，反之亦然，所以，中的一条边，反之亦然，所以，有：有：(2)对于单图对于单图G,A(G)中非零的中非零的2阶主子式必为如下形式：阶主子式必为如下形式：4第4页，本讲稿共22页这样的一个这样的一个3阶主子

3、式对应阶主子式对应G中的一个中的一个K3，反之亦然，反之亦然.设设G中有中有S个个K3,则：则：(3)对于单图对于单图G,A(G)中非零的中非零的3阶主子式必为如下形式：阶主子式必为如下形式：事实上，有如下一般性定理：事实上，有如下一般性定理：(见李蔚萱，图论，湖南见李蔚萱，图论，湖南科学技术出版社，科学技术出版社，1980年年4月月)5第5页，本讲稿共22页定理定理1：图：图G的特征多项式的系数：的特征多项式的系数：其中，其中，s(G,H)表示表示G的同构于的同构于H的导出子图的数目。的导出子图的数目。右边对所有右边对所有i阶图阶图H求和。求和。2、图的邻接谱、图的邻接谱定义定义2：图的邻接

4、矩阵：图的邻接矩阵A(G)的特征多项式的特征值及其重的特征多项式的特征值及其重数，称为数，称为G的邻接谱。的邻接谱。例例2、求出、求出K n的谱。的谱。解：解：K n的邻接矩阵为：的邻接矩阵为：6第6页，本讲稿共22页于是：于是：7第7页，本讲稿共22页所以：所以：例例3，若两个非同构的图具有相同的谱，则称它们是同谱，若两个非同构的图具有相同的谱，则称它们是同谱图。求证：下面两图是同谱图。图。求证：下面两图是同谱图。GH8第8页，本讲稿共22页证明：证明：G与与H显然不同构。显然不同构。通过直接计算：通过直接计算：所以所以G与与H是同谱图。是同谱图。例例4，设单图，设单图A(G)的谱为：的谱为

5、：则：则：证明：由矩阵理论：证明：由矩阵理论：9第9页，本讲稿共22页a ii(2)表示点表示点vi的度数，由握手定理：的度数，由握手定理：即：即：例例5，设，设是是单图单图G=(n,m)的任意特征值，则：的任意特征值，则：证明：不失一般性，设证明：不失一般性，设=1 1，2 2，,n n是是G G的全体特征的全体特征值。值。G是是单图，有：单图，有：10第10页，本讲稿共22页又由例又由例4，有：，有：对向量对向量(1,1,1)与与(2 2,3 3,4 4,n n)用柯西不等式得：用柯西不等式得：所以，有：所以，有：由由(1)与与(2)得：得：11第11页，本讲稿共22页注：对于图谱的研究，

6、开始于二十世纪注：对于图谱的研究，开始于二十世纪60年代。形成了代年代。形成了代数图论的主要研究方向之一。图谱研究在流体力学，量子数图论的主要研究方向之一。图谱研究在流体力学，量子化学里有重要的应用。国内，中国科技大学数学系是最早化学里有重要的应用。国内，中国科技大学数学系是最早展开该课题研究的单位展开该课题研究的单位(1978年就有很好的研究成果年就有很好的研究成果)。他。他们对图论的研究主要有两个方面：一是图谱问题，二是组们对图论的研究主要有两个方面：一是图谱问题，二是组合网络研究，也有达到国际水平的研究成果合网络研究，也有达到国际水平的研究成果(1994年开始年开始).关于组合网络问题，

7、将在第三章作一些介绍。关于组合网络问题，将在第三章作一些介绍。12第12页，本讲稿共22页(二二)、图的邻接代数、图的邻接代数1、图的邻接代数的定义、图的邻接代数的定义定义定义3：设：设A是无环图是无环图G的邻接矩阵，称：的邻接矩阵，称：对于矩阵的加法和数与矩阵的乘法来说作成数域对于矩阵的加法和数与矩阵的乘法来说作成数域C上的向量上的向量空间，称该空间为图空间，称该空间为图G的邻接代数。的邻接代数。注：注：向量空间的定义可简单地记为向量空间的定义可简单地记为“非空非空”、“两闭两闭”、“八条八条”2、图的邻接代数的维数特征、图的邻接代数的维数特征13第13页，本讲稿共22页定理定理1：G为为n

8、阶连通图，则：阶连通图，则：证明：由哈密尔顿证明：由哈密尔顿凯莱定理凯莱定理(见北大数学力学系高等代数见北大数学力学系高等代数)：所以：所以：下面证明：下面证明：E,A,A2,A d(G)线性无关！线性无关！若不然，则存在不全为零的数若不然，则存在不全为零的数a0,a1,a d(G),使：使：14第14页，本讲稿共22页设设a m-10,但当但当k m 时时，有，有a k=0.于是有：于是有：假定：假定：v1 v2 v d(G)+1 是是G中一条最短的中一条最短的(v1,v d(G)+1)路，易知：路，易知：d(G)n.于是，于是，d(v1,v m)=m-1,(m=1,2,d(G)+1)注意到

9、：注意到：A k的元素的元素a1m(k)在在 k 0所以，所以，的一行的一行m列元为列元为am-1a1m(m-1)0，这样有：15第15页，本讲稿共22页产生矛盾！产生矛盾！定理结果分析：不等式右端的界是紧的！定理结果分析：不等式右端的界是紧的！因为：因为：n点路的直径为点路的直径为n-1,所以，此时该路的邻接代数的维数所以，此时该路的邻接代数的维数正好为正好为n。此外：当此外：当G为为K n时，有：时，有：例例6，设，设G 为为n阶连通图，则阶连通图，则G的不同特征值的个数的不同特征值的个数S满足：满足：16第16页，本讲稿共22页证明：证明：S nn是显然的！是显然的！由矩阵理论知：对称矩

10、阵的不同特征值的个数等于其最小多项由矩阵理论知：对称矩阵的不同特征值的个数等于其最小多项式的次数，而最小多项式的次数等于式的次数，而最小多项式的次数等于G的邻接代数的维数，所的邻接代数的维数，所以：以：注注:(1)n点路的不同特征值有点路的不同特征值有n个；个；(2)K n的不同特征值有的不同特征值有2个。个。17第17页，本讲稿共22页定理定理2：集合：集合：对于图的对称差运算和数乘运算：对于图的对称差运算和数乘运算：(三三)、图空间简介、图空间简介来说作成数域来说作成数域 F=0,1 上的上的m维维向量空向量空间间。注：图空间概念是网络图论中的一个基本概念。研究通信注：图空间概念是网络图论

11、中的一个基本概念。研究通信网络，如果要用图论方法，建议参看陈树柏的网络图论网络，如果要用图论方法，建议参看陈树柏的网络图论及其应用，科学出版社，及其应用，科学出版社，1982年。学习网络图论的主要年。学习网络图论的主要基础是电工学与矩阵理论知识。基础是电工学与矩阵理论知识。18第18页，本讲稿共22页证明证明:(1)证明证明M是是F上的向量空间，只需要验证上的向量空间，只需要验证“两闭两闭”与与“八八条条”即可。即可。(2)M(2)M的的维维数数为为m m令令又令：又令：可以可以证证明：明：g g1 1,g,g2 2,g,gm m为为M M的一的一组组基！基！事事实实上：上：对对若若E(GE(Gi i)=e)=ei1i1,e,ei2i2,e,eikik,则则：19第19页，本讲稿共22页另一方面：若另一方面：若则则：c c1 1=c=c2 2=c=cm m=0=0所以：所以：20第20页，本讲稿共22页作业作业设设G是一个是一个r度正则图，证明：度正则图，证明：(1)r是是G的的一个特征值；的的一个特征值；(2)特征值特征值r的重数等于的重数等于G的连通分支数；的连通分支数；(3)G的任意特征值的任意特征值满足：满足：21第21页，本讲稿共22页Thank You!22第22页，本讲稿共22页