图论邻接谱与图的邻接代数.pptVIP

**图论课件邻接谱与图的邻接代数*第1页，共22页，星期日，2025年，2月5日第一章图的基本概念本次课主要内容邻接谱与图的邻接代数(一)、邻接谱(二)、图的邻接代数(三)、图空间简介*第2页，共22页，星期日，2025年，2月5日(一)、邻接谱1、图的特征多项式定义1：图的邻接矩阵A(G)的特征多项式：称为图G的特征多项式。例1、设单图G的特征多项式为：求证:(1)a1=0;(2)–a2=m(G);(3)–a3是G中含有不同的K3子图的个数2倍。*第3页，共22页，星期日，2025年，2月5日证明：由矩阵理论：对每个1≦i≦n,(-1)iai是A(G)的所有i阶主子式之和。(1)由于A(G)的主对角元全为零，所以所有1阶主子式全为零，即：a1=0;这样的一个2阶主子式对应G中的一条边，反之亦然，所以，有：(2)对于单图G,A(G)中非零的2阶主子式必为如下形式：*第4页，共22页，星期日，2025年，2月5日这样的一个3阶主子式对应G中的一个K3，反之亦然.设G中有S个K3,则：(3)对于单图G,A(G)中非零的3阶主子式必为如下形式：事实上，有如下一般性定理：(见李蔚萱，《图论》，湖南科学技术出版社，1980年4月)*第5页，共22页，星期日，2025年，2月5日定理1：图G的特征多项式的系数：其中，s(G,H)表示G的同构于H的导出子图的数目。右边对所有i阶图H求和。2、图的邻接谱定义2：图的邻接矩阵A(G)的特征多项式的特征值及其重数，称为G的邻接谱。例2、求出Kn的谱。解：Kn的邻接矩阵为：*第6页，共22页，星期日，2025年，2月5日于是：*第7页，共22页，星期日，2025年，2月5日所以：例3，若两个非同构的图具有相同的谱，则称它们是同谱图。求证：下面两图是同谱图。GH*第8页，共22页，星期日，2025年，2月5日证明：G与H显然不同构。通过直接计算：所以G与H是同谱图。例4，设单图A(G)的谱为：则：证明：由矩阵理论：*第9页，共22页，星期日，2025年，2月5日aii(2)表示点vi的度数，由握手定理：即：例5，设λ是单图G=(n,m)的任意特征值，则：证明：不失一般性，设λ=λ1，λ2，…,λn是G的全体特征值。G是单图，有：*第10页，共22页，星期日，2025年，2月5日又由例4，有：对向量(1,1,…,1)与(λ2,λ3,λ4,…,λn)用柯西不等式得：所以，有：由(1)与(2)得：*第11页，共22页，星期日，2025年，2月5日注：对于图谱的研究，开始于二十世纪60年代。形成了代数图论的主要研究方向之一。图谱研究在流体力学，量子化学里有重要的应用。国内，中国科技大学数学系是最早展开该课题研究的单位(1978年就有很好的研究成果)。他们对图论的研究主要有两个方面：一是图谱问题，二是组合网络研究，也有达到国际水平的研究成果(1994年开始).关于组合网络问题，将在第三章作一些介绍。*第12页，共22页，星期日，2025年，2月5日(二)、图的邻接代数1、图的邻接代数的定义定义3：设A是无环图G的邻接矩阵，称：对于矩阵的加法和数与矩阵的乘法来说作成数域C上的向量空间，称该空间为图G的邻接代数。注：向量空间的定义可简单地记为“非空”、“两闭”、“八条”2、图的邻接代数的维数特征*第13页，共22页，星期日，2025年，2月5日定理1：G为n阶连通图，则：证明：由哈密尔顿—凯莱定理(见北大数学力学系《高等代数》)：所以：下面证明：E,A,A2,…,Ad(G)线性无关！若不然，则存在不全为零的数a0,a1,…,ad(G),使：*第14页，共22页，星期日，2025年，2月5日设am-1≠0,但当k≥m时，有ak=0.于是有：假定：v1v2…vd(G)+1是G中一条最短的(v1,vd(G)+1)路，易知：d(G)n.于是，d(v1,vm)=m-1,(m=1,2,…,d(G)+1)注意到：Ak的元素a1m(k)在km-1时为零，而a1m(m-1)0所以，的一行m列元为am-1a1m(m-1)≠0，这样有：*第15页，共22页，星期日，2025年，2月5日产生矛盾！定理结果分析：不等式右端的界是紧的！因为：n点