电子科越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /956 证明：不失一般性，设入=入1’入2’…，入n是G的全体 特征值。 G是单图，有：1=-(2+3+…+元n）…(① 又由定理1，有：32=2m-(22+22+…+元2）…(2) 对向量(1,1，，1)与（入2，入3，入4y…,入）用柯西不等式得： 21+元l+…+元l≤V,2+22+.+2,2m-1 该不等式结合(1)与(2)，容易得到： 2(n-1)
证明：不失一般性，设λ=λ1，λ2，…,λn是G的全体 特征值。 G是单图，有： 又由定理1，有： 对向量(1,1,…,1)与(λ2,λ3,λ4,…,λn)用柯西不等式得： 该不等式结合(1)与(2)，容易得到：
S 电子科越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /956 图的邻接谱起源于化学分子图结构研究(20世纪30年代)，1969 年由萨克斯正式提出。到目前，理论内容宏大。在此仅作一点点 介绍。有兴趣的同学可以参看： 【1】《Spectra of Graphs-Theory and Application》, D.M.Cvetkovic M.Doob H.Sachs. 【2】《Algebraic Graph Theory》.N.Biggs. (二)、图的邻接代数 图的邻接代数是与图的邻接矩阵相关联的一类代数。它是以邻接 矩阵的多项式为元素构成的复数域上的向量空间
图的邻接谱起源于化学分子图结构研究(20世纪30年代)，1969 年由萨克斯正式提出。到目前，理论内容宏大。在此仅作一点点 介绍。有兴趣的同学可以参看： 【1】《Spectra of Graphs —Theory and Application》. D.M.Cvetkovic M.Doob H.Sachs. 【2】《Algebraic Graph Theory 》. N.Biggs. ( 二 )、图的邻接代数 图的邻接代数是与图的邻接矩阵相关联的一类代数。它是以邻接 矩阵的多项式为元素构成的复数域上的向量空间
电子科越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /956 1、图的邻接代数的定义 定义3：设A是无环图G的邻接矩阵，则： A(G)=aoE+aA+..+ax4*a,C,k' 对于矩阵的加法和数与矩阵的乘法来说作成数域C上的 向量空间，称该空间为图G的邻接代数。 注：向量空间的定义可简单地记为非空”、“两闭”、“八 条” 2、图的邻接代数的维数特征 定理3：G为n阶连通无环图，则： d(G)+1≤dim(G)≤n
1、图的邻接代数的定义 定义3：设A是无环图G的邻接矩阵，则： 对于矩阵的加法和数与矩阵的乘法来说作成数域C上的 向量空间，称该空间为图G的邻接代数。 注：向量空间的定义可简单地记为“非空”、“两闭”、“八 条” . 2、图的邻接代数的维数特征 定理3：G为n阶连通无环图，则：
电子摊越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /956 证明：由哈密尔顿一凯莱定理（见北大数学力学系《高 等代数》)：f(A)=a,E+aA+a2A2+.+anA”=0 所以：dimA(G)≤n 下面证明：E,A,A2,.,Ad(G线性无关！ 若不然，则存在不全为零的数，41，，0aG,使： doE+a4+a42+..+ad()44(0)=0 设am-10,但当k≥m时，有ak=0.于是有： aE+a1A+a2A2+…+am-1Am-1=0,(am-1≠ 0
证明：由哈密尔顿—凯莱定理(见北大数学力学系《高 等代数》)： 所以： . 下面证明：E, A, A2, … , A d (G) 线性无关！ 若不然，则存在不全为零的数a0 ,a1 , … , a d (G) ,使： 设a m-1≠0 , 但当k ≥ m 时，有a k =0. 于是有：