图论课件邻接谱与图的邻接代数

《图论课件邻接谱与图的邻接代数》由会员分享，可在线阅读，更多相关《图论课件邻接谱与图的邻接代数（22页珍藏版）》请在装配图网上搜索。

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1 图论及其应用图论及其应用应用数学学院应用数学学院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2第一章第一章 图的基本概念图的基本概念本次课主要内容本次课主要内容邻接谱与图的邻接代数邻接谱与图的邻接代数(一一)、邻接谱、邻接谱(二二)、图的邻接代数、图的邻接代数(三三)、图空间简介、图空间简介 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 312121(,)

2、nnnnnf GE Aaaaa(一一)、邻接谱、邻接谱1、图的特征多项式、图的特征多项式定义定义1：图的邻接矩阵：图的邻接矩阵A(G)的特征多项式：的特征多项式：称为图称为图G的特征多项式。的特征多项式。例例1、设单图、设单图G的特征多项式为：的特征多项式为：12121(,)nnnnnf GE Aaaaa求证求证:(1)a1=0;(2)a2=m(G);(3)a3是是G中含有不同的中含有不同的K3子图的个数子图的个数2倍。倍。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4证明：由矩阵理论：对每个证明：由矩阵理论：对每个1in,(-1

3、)n,(-1)i ia ai i是是A(G)A(G)的的所有所有i i阶主子式之和。阶主子式之和。(1)由于由于A(G)的主对角元全为零，所以所有的主对角元全为零，所以所有1阶主子阶主子式全为零，即：式全为零，即：a1=0;01110 这样的一个这样的一个2阶主子式对应阶主子式对应G中的一条边，反之亦然，中的一条边，反之亦然，所以，有：所以，有：(2)对于单图对于单图G,A(G)中非零的中非零的2阶主子式必为如下形阶主子式必为如下形式：式：22(1)()am G 2()am G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5011

4、1012110这样的一个这样的一个3阶主子式对应阶主子式对应G中的一个中的一个K3，反之亦然，反之亦然.设设G中有中有S个个K3,则：则：(3)对于单图对于单图G,A(G)中非零的中非零的3阶主子式必为如下形阶主子式必为如下形式：式：33(1)2aS事实上，有如下一般性定理：事实上，有如下一般性定理：(见李蔚萱，见李蔚萱，图论图论，湖，湖南科学技术出版社，南科学技术出版社，1980年年4月月)0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6定理定理1：图：图G的特征多项式的系数：的特征多项式的系数：(1)det(,),1,2,iiH

5、aHs G Hin其中，其中，s(G,H)表示表示G的同构于的同构于H的导出子图的数目。的导出子图的数目。右边对所有右边对所有i阶图阶图H求和。求和。2、图的邻接谱、图的邻接谱定义定义2：图的邻接矩阵：图的邻接矩阵A(G)的特征多项式的特征值的特征多项式的特征值及其重数，称为及其重数，称为G的邻接谱。的邻接谱。例例2、求出、求出K n的谱。的谱。解：解：K n的邻接矩阵为：的邻接矩阵为：0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 70111110111()111110nA K于是：于是：11111111()11111nEA K11

6、111111111111nnn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8111111111111111n 1(1)nn 所以：所以：11()11nnSpec Kn例例3，若两个非同构的图具有相同的谱，则称它们是同，若两个非同构的图具有相同的谱，则称它们是同谱图。求证：下面两图是同谱图。谱图。求证：下面两图是同谱图。GH 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9证明：证明：G与与H显然不同构。显然不同构。通过直接计算：通过直接计算：6432(,)(,)747

7、41f Gf H所以所以G与与H是同谱图。是同谱图。例例4，设单图，设单图A(G)的谱为：的谱为：1212()ssSpec Gmmm则：则：212()Siiimm G证明：由矩阵理论：证明：由矩阵理论：2(2)11Sniiiiiima 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10a ii(2)表示点表示点vi的度数，由握手定理：的度数，由握手定理：即：即：2(2)111()2()Snniiiiiiiimad vm G212()Siiimm G例例5，设，设是是单图单图G=(n,m)的任意特征值，则：的任意特征值，则：2(1)m

8、 nn证明：不失一般性，设证明：不失一般性，设=1 1，2 2，,n n是是G G的全体的全体特征值。特征值。G是是单图，有：单图，有：123(1)n 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11又由例又由例4，有：，有：对向量对向量(1,1,1)与与(2 2,3 3,4 4,n n)用柯西不等式用柯西不等式得：得：22223231111nnn22221232(2)nm所以，有：所以，有：222223231nnn由由(1)与与(2)得：得：2(1)m nn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5

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

10、研究成果的研究成果(1994年开始年开始).关于组合网络问题，将在第关于组合网络问题，将在第三章作一些介绍。三章作一些介绍。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13(二二)、图的邻接代数、图的邻接代数1、图的邻接代数的定义、图的邻接代数的定义定义定义3：设：设A是无环图是无环图G的邻接矩阵，称：的邻接矩阵，称：01(),kkiGa Ea Aa AaC kZ对于矩阵的加法和数与矩阵的乘法来说作成数域对于矩阵的加法和数与矩阵的乘法来说作成数域C上的上的向量空间，称该空间为图向量空间，称该空间为图G的邻接代数。的邻接代数。注：注

11、：向量空间的定义可简单地记为向量空间的定义可简单地记为“非空非空”、“两闭两闭”、“八条八条”2、图的邻接代数的维数特征、图的邻接代数的维数特征 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14定理定理1：G为为n阶连通图，则：阶连通图，则：()1dim()d GGn证明：由哈密尔顿证明：由哈密尔顿凯莱定理凯莱定理(见北大数学力学系见北大数学力学系高高等代数等代数)：2012()0nnf Aa Ea Aa Aa A所以：所以：dim()Gn下面证明：下面证明：E,A,A2,A d(G)线性无关！线性无关！若不然，则存在不全为零的数

12、若不然，则存在不全为零的数a0,a1,a d(G),使：使：2()012()0d Gd Ga Ea Aa AaA 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15设设a m-10,但当但当k m 时，有时，有a k=0.于是有：于是有：假定：假定：v1 v2 v d(G)+1 是是G中一条最短的中一条最短的(v1,v d(G)+1)路，路，易知：易知：d(G)n.21012110,(0)mmma Ea Aa AaAa于是，于是，d(v1,v m)=m-1,(m=1,2,d(G)+1)注意到：注意到：A k的元素的元素a1m(k)在

13、在 k 0所以，所以，的一行的一行m列元为列元为am-1a1m(m-1)0，这样有：210121mma Ea Aa AaA 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 162101210mma Ea Aa AaA产生矛盾！产生矛盾！定理结果分析：不等式右端的界是紧的！定理结果分析：不等式右端的界是紧的！因为：因为：n点路的直径为点路的直径为n-1,所以，此时该路的邻接代数所以，此时该路的邻接代数的维数正好为的维数正好为n。此外：当此外：当G为为K n时，有：时，有：2dim()nKn例例6，设，设G 为为n阶连通图，则阶连通图，则

14、G的不同特征值的个数的不同特征值的个数S满满足：足：()1d GSn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17证明：证明：S nn是显然的！是显然的！dim()()1SGd G由矩阵理论知：对称矩阵的不同特征值的个数等于其由矩阵理论知：对称矩阵的不同特征值的个数等于其最小多项式的次数，而最小多项式的次数等于最小多项式的次数，而最小多项式的次数等于G的邻接的邻接代数的维数，所以：代数的维数，所以：注注:(1)n点路的不同特征值有点路的不同特征值有n个；个；(2)K n的不同特征值有的不同特征值有2个。个。0.8 1 0.6

15、0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18定理定理2：集合：集合：对于图的对称差运算和数乘运算：对于图的对称差运算和数乘运算：(三三)、图空间简介、图空间简介12,2mNiMG GGGGN为单图 的子图，0,1iiiGGG 来说作成数域来说作成数域 F=0,1 上的上的m维向量空间。维向量空间。注：图空间概念是网络图论中的一个基本概念。研究注：图空间概念是网络图论中的一个基本概念。研究通信网络，如果要用图论方法，建议参看陈树柏的通信网络，如果要用图论方法，建议参看陈树柏的网络图论及其应用网络图论及其应用，科学出版社，科学出版社，1982年。学习

16、年。学习网络图论的主要基础是电工学与矩阵理论知识。网络图论的主要基础是电工学与矩阵理论知识。0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1912(),mE Ge ee证明证明:(1)证明证明M是是F上的向量空间，只需要验证上的向量空间，只需要验证“两闭两闭”与与“八条八条”即可。即可。(2)M(2)M的维数为的维数为m m令令又令：又令：,(1)iigG eim可以证明：可以证明：g g1 1,g,g2 2,g,gm m为为M M的一组基！的一组基！事实上：对事实上：对iGM若若E(GE(Gi i)=e)=ei1i1,e,ei2i

17、2,e,eikik,则：则：12iiiikGggg 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20另一方面：若另一方面：若则：则：c c1 1=c=c2 2=c=cm m=0=01122mmc gc gc g 所以：所以：dim()Mm 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21作业作业设设G是一个是一个r度正则图，证明：度正则图，证明：r是是G的的一个特征值；的的一个特征值；(2)特征值特征值r的重数等于的重数等于G的连通分支数；的连通分支数；(3)G的任意特征值的任意特征值满足：满足：r 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22Thank You!