电子科越女学 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)的任意特征值，则： 注：在图谱研究中(包括邻接谱，拉普拉斯谱，拟拉普拉斯谱等)，一 个重要关注点之一是特征值模的上界估计。有趣的是，用不同的矩阵 理论方法，可以获得不同的上界估计