电子科越女学 veraitya Bectrole Sclece and TechaologyafChaa 本次课内容 一、邻接谱、邻接代数与图空间 二、托兰定理
本次课内容 一、邻接谱、邻接代数与图空间 二、托兰定理
电子科越女学 elvraity af Beetronle Sclece and Techaelogy af Chaa /936 在图论中，代数图论是其重要分支。所谓代数图论，就是用代数 方法研究图的结构性质，包括矩阵理论方法、群论方法等。代数 图论已经广泛应用到数学、物理、网络技术和计算机科学中。在 本课程中，我们只作一点简单认识。 一、邻接谱、邻接代数与图空间 (一)、图的邻接谱 1、定义1：图的邻接矩阵A(G)的特征值及其重数，称为G 的邻接谱。 例如，我们能够容易求出完全图K的邻接谱为： - Spec(K) n-1
在图论中，代数图论是其重要分支。所谓代数图论，就是用代数 方法研究图的结构性质，包括矩阵理论方法、群论方法等。代数 图论已经广泛应用到数学、物理、网络技术和计算机科学中。在 本课程中，我们只作一点简单认识。 一、邻接谱、邻接代数与图空间 ( 一 )、图的邻接谱 1、定义 1：图的邻接矩阵A(G)的特征值及其重数，称为 G 的邻接谱。 例如，我们能够容易求出完全图 K n的邻接谱为：
电子摊越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /936 在邻接谱问题中，一个有趣的问题是“同谱图”问题。 定义2若两个非同构的阶图具有相同的谱，则称它们 是同谱图。 例如，通过简单计算容易判定如下两图是同谱图。 G H 2、邻接谱的两个性质 对图的邻接谱的研究形成了谱图理论的重要内容，得到了 众多有用且优美的结果，作为简单认识，介绍两个结果
在邻接谱问题中，一个有趣的问题是“同谱图”问题。 定义2 若两个非同构的 n阶图具有相同的谱，则称它们 是同谱图。 例如，通过简单计算容易判定如下两图是同谱图。 G H 2、邻接谱的两个性质 对图的邻接谱的研究形成了谱图理论的重要内容，得到了 众多有用且优美的结果，作为简单认识，介绍两个结果
电子特越女学 elvraity af Beetronle Sclece and Techaelogy af Chaa /956 定理1设单图A(G)的谱为： Spec(G)= 1112 则： m22=2m(G》 i=1 注：定理1给出了单图A(G)的谱与图的边数之间的系。提示我们： 通过研究邻接矩阵可以获取图的结构信息！也就是可以借助于矩阵理 论方法研究图结构！实现图论的代数研究。 证明：由矩阵理论： i1 因为G是单图，所以，a#2表示点y的度数，由握手定理： 地2o9yd2m匹
定理1 设单图A(G)的谱为： 则： 注：定理1 给出了单图A(G)的谱与图的边数之间的关系。提示我们： 通过研究邻接矩阵可以获取图的结构信息！也就是可以借助于矩阵理 论方法研究图结构！实现图论的代数研究。 证明：由矩阵理论： 因为G是单图，所以，a ii (2)表示点vi的度数，由握手定理：
电子特越女学 elvraity af Beetronle Sclece and Techaelogy af Chaa /936 2n-1 例如，根据完全图的谱： Spec(K)= -11 得到： m,22=(n-1(-1)2+(n-1)2×1=(n-)=2m(K.) 借助于矩阵理论方法研究图结构性质，要灵活应用矩阵理论结果！ 定理2设λ是单图G=(n,m)的任意特征值，则： 2(n-1)》 注：在图谱研究中（包括邻接谱，拉普拉斯谱，拟拉普拉斯谱等），一 个重要关注点之一是特征值模的上界估计。有趣的是，用不同的矩阵 理论方法，可以获得不同的上界估计
例如，根据完全图的谱： ， 得到： 2 2 2 1 ( 1)( 1) ( 1) 1 ( 1) 2 ( ) S ii n i m n n nn mK 借助于矩阵理论方法研究图结构性质，要灵活应用矩阵理论结果！ 定理2 设λ是单图G = (n, m)的任意特征值，则： 注：在图谱研究中(包括邻接谱，拉普拉斯谱，拟拉普拉斯谱等)，一 个重要关注点之一是特征值模的上界估计。有趣的是，用不同的矩阵 理论方法，可以获得不同的上界估计
电子科越女学 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. 于是有：
电子摊越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /956 假定：V1V2…VaGH1是G中一条最短的(W1,VdGH1)路。 V2 Vm-1 Vm Vmt1 Vd(e) Vd(@)+1 于是，dy,vm)=m-1,(m=1,2,,d(G)+1) 注意到：Ak的元素a1mW在k→0. 所以，a,E+41A+a2A2+…+am-1Am-的一行m 列元为am-141mm-10,这样有： aE+a1A+a2A2+…+am-1Am-1≠0 从而产生矛盾！证毕
假定：v1 v2… v d(G)+1 是G中一条最短的 (v1, v d(G)+1)路. v1 v2 vm-1 vm vm+1 vd(G) vd(G)+1 于是，d(v1, v m ) = m-1 , (m=1, 2, … , d (G)+1) 注意到：A k的元素a1m (k)在 k 0. 所以， 的一行m 列元为am-1a1m (m-1)≠0，这样有： 从而产生矛盾！证毕