（计算数学专业论文）图dn和qn的研究.pdf

摘要 摘要 图谱理论主要是使用代数方法来研究图的谱。“w h i c h g r a p h sa r e d e t e r m i n e d b y t h e i rs p e c t r u m s ”在图谱理论中是一个很著名的问题，但是这个问题很难回答。到 目前为止，这个问题还远没有解决。通常，如果任何一个图与图g 同谱，那么这 个图只有与图g 同构，图g 才被称为是由其谱决定的，我们把这样的图简称为d s ( d e t e r m i n e db yt h es p e c t r u m ) 图。一般情形下，无论你是选择邻接矩阵，拉普拉斯 矩阵，或者其他形式的矩阵来描述图，除了一些具有特殊结构的图外，大部分图 都是不能和自己的谱一一对应的。 由于这个问题非常困难，我们主要研究一些结构比较简单的图，比如图晓和 q ，图见是由图c 3 、只的不交并c 3u ，通过一条边连结c 3 中的一度点和只中 的一度点得到的，其中c 3 表示包含3 个点的圈，表示包含n 个点的路径；而图q 是由图e 、p l 的不交并e u 日，通过一条边连结e 中的一度点和只得到的，其中e 表示包含咒个点的圈，曰表示包含1 个点的路径，即孤立点。在这篇论文中，我们 将证明图d 和q 是由其邻接矩阵的谱唯一决定的。进一步，我们定义了图e 和 q 2 ，分别与图q 和q 相似。通过对它们的谱半径的估计，我们同样证明了图巨 和q ，也是由其邻接矩阵的谱唯一决定的。 关键词：图谱，同谱图，谱半径，谱决定 a b s t r a c t s p e c t r a lg r a p ht h e o r yi sc o n c e r n e dw i t ht h eu s eo fa l g e b r a i ct e c h n i q u e si nt h es t u d y o ft h es p e c t r u m so f g r a p h s w h i c hg r a p h sa r ed e t e r m i n e db yt h e i rs p e c t r u m si saf a m o u s q u e s t i o ni nt h et h e o r y , b u ti ti sv e r yd i f f i c u l t t oa n s w e r a sf a ra sw e k n o w , i ti sf a rf r o m r e s o l v e d u s u a l l y , ag r a p hgi sc a l l e ds p e c t r a l l yd e t e r m i n e di fa n yg r a p hw i t ht h e s a m es p e c t r u mi si s o m o r p h i ct og ，w ec a l li td s ( d e t e r m i n e db yt h es p e c t r u m ) m o r e g e n e r a l l y , i ti si m p o s s i b l et oc h a r a c t e r i z eag r a p hb yi t ss p e c t r u m , w h i c hi so b t a i n e d f i ：o mt h es p e c i f i cm a t r i xs u c ha st h ea d j a c e n c ym a t r i x ，t h el a p l a c i a nm a t r i x ，o rt h e i r n o r m a l i z e df o r m s ，e x c e p tf o rs o m eg r a p h sw i t hs p e c i a ls t r u c t u r e s a st h ep r o b l e mi ss oh a r dt os o l v e ，w ec o n c e n t r a t eo i lt h eg r a p h sw i t hs i m p l e s t r u c t u r e ss u c ha sg r a p h s 见a n dq ，ag r a p h 见i st h eg r a p ho b t a i n e df r o m c 3u e b ya d d i n ga ne d g et oc o n n e c tav e r t e xo fga n dav e r t e xo f d e g r e e1i n ， w h e r ec 3d e n o t e st h ec y c l ew i t h3v e r t i c e s ，a n d 只d e n o t e st h ep a t hw i t h 以v e r t i c e s ； ag r a p hqi st h eg r a p ho b t a i n e df r o meu e , b ya d d i n ga ne d g et oc o n n e c tf i tv e r t e x o fea n d 日，w h e r eed e n o t e st h ec y c l ew i t h 刀v e r t i c e s ，a n d 日d e n o t e sa n i s o l a t e dv e r t e x i nt h i st h e s i s ，w ew i l lp r o v et h a tg r a p h s 见a n dqa l ed e t e r m i n e db y l e i ra d j a c e n c ys p e c t r u m s f u r t h e r m o r e ，w ed e f i n et w og r a p h s 巨a n dq 2 ，w h i c ha r e s i m i l a rt og r a p h s 见a n dqr e s p e c t i v e l y b ye s t i m a t i n gt h es p e c t r a lr a d i u so ft h et w o g r a p h s ，w ec a np r o v et h a t 伊a p l l sea n dq 2 a r ea l s od e t e r m i n e db yt h e i ra d j a c e n c y s p e c t r u m s k e y w o r d ：s p e c t r ao fg r a p h s ，c o s p e c t r a l 笋印h s ，s p e c t r a lr a d i u s ，d e t e r m i n e db yt h e s p e c t n t m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人己经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：鲎篮叠日期：2 印苔年乡月2 珀 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名：型堕导师签名：型垄! 堡 日期：删附钆乡日 第一章图谱理论概述 第一章图谱理论概述 随着现代计算机技术的发展和科学技术的进步，矩阵理论的研究越来越受到 数学学者、工程技术人员和科技人员的关注，其应用范围已渗透到许多学科领域， 组合矩阵论就是其中之一。组合矩阵论是近3 0 余年来兴起并发展迅速的一个数学 分支，它用矩阵论和线性代数来证明组合性定理及对组合结构进行描述和分类， 同时，也把组合论的思想和论证方法用于矩阵的精细分析及揭示阵列的内在组合 性质 2 1 。此外，矩阵理论与代数中的一些理论和方法相结合来研究图，或反过来利 用图论来研究一些矩阵和代数问题，这些思想和方法现已被人们所普遍采用，并 得到很多丰富而深刻的结果，并由此逐渐发展出了代数图论这一图论分支【l 】。组合 矩阵论不仅与众多的数学领域( 数论、线性代数、图论和概率论等) 有密切的联 系，而且在信息科学、社会学、经济数学、计算机科学和化学等许多方面都有具 体的应用背景，已经成为计算数学的一个重要分支【z j 。 1 1 引言 正是由于组合矩阵论广泛的应用，最近几年衍生了许多新的研究领域，比如 说矩阵完成问题、图的逆特征值问题、最小秩问题和图谱理论等等，这是一些主 要运用图论的方法来研究矩阵方面的问题，其思想和方法备受关注。其中，矩阵 完成问题是这样一个问题：一个矩阵有若干个元素已经被确定，但还有部分元素 不确定，我们知道这个矩阵整体满足某些条件，比如说：矩阵为m 矩阵，逆m 矩 阵、p 矩阵或p o 矩阵等等，那么这些不确定的元素可以在什么范围内取值，以满 足这些限制条件。其采用的研究方法要涉及有向图，与图论的联系很紧密，目前 这一领域正蓬勃发展，已取得了丰硕的成果；图的逆特征值问题是指任意给出一 组特征值序列，那么是否可以构造一个无向图，使其谱特征值与给出的特征值相 对应；而最小秩问题则是任意给出一个简单无向图，如果两点之间有一条边连结， 在矩阵中，其对应的位置就用一个非零元素表示，对角线元素用零表示，这样一 个简单无向图可以对应若干个矩阵，在这些矩阵中，找一个秩最小的矩阵；反过 来，我们限定秩的大小，来构造一些图，满足这些限制条件，从而可以得到一些 禁止子图。这些新的研究领域大大拓展了组合矩阵论的研究范围，为组合矩阵论 电子科技人学硕十学位论文 的发展奠定了深厚的基础。 图谱理论主要研究简单无向图，并用矩阵描述这些无向图，比如：邻接矩阵、 拉普拉斯矩阵或广义邻接矩阵，然后再计算这些矩阵的谱，并研究这些谱是否与 这些图一一对应，或者说，这些无向图是不是由其某一矩阵的谱唯一决定的。当 前研究主要集中在一些简单图和具有特殊性质的图，如：最大度不超过3 的树、强 正则图，而且随着选取不同的矩阵，这种一一对应关系也会发生相应的变化。研 究图谱采用的方法主要是代数方法，并利用图的一些性质来推断相应的谱的性质。 由于很多图是无法准确计算出其所有特征值的，所以我们通常估算其谱半径，于 是谱半径成为了图谱理论一个很重要的判断依据。另一方面，我们可以构造各种 各样的同谱但不同构的图，与其由谱决定的图做对比。通过计算机的计算，我们 发现一些有趣的性质，例如：随着树的阶数的不断增大，这两类树的数目都趋于 零 3 1 。随着研究的不断深入，在以上问题的研究方法上也有了新的突破，如现在采 用广义拉普拉斯矩阵结合c o l i nd e v e r d i 色r e n u m b e r a ( g ) ，在图谱理论和图的逆特征值 问题的实际应用中就取得了很好的效果 7 1 。 1 2 图的基本定义及其性质 下面介绍图的基本概念及其性质： 定义1 2 1 【i i 一个图g 定义为一个有序对( y ，e ) ，记为g = ( 以e ) ，其中 ( 1 ) 矿( g ) 是一个非空集合，称为顶点集或点集，其元素称为顶点或点，m 表 示顶点数； ( 2 ) e ( g ) 是由y 中的点组成的无序点对构成的集合，称为边集，其元素称为 边，且同一点对在e 中可出现多次； ( 3 ) 既没有环也没有重边的图称为简单图。 图g 的顶点1 ，的度d e g ( v ) 是指g 中与v 关联的边的数目，用万( g ) 和( g ) 分别 表示g 的顶点的最小度和最大度【i 】。 设g = ( v ，d 为简单图，如果对所有，v ，有d e g ( v ) = k ，称图g 为k 正则图。 每两个不同的顶点之间都有一条边相连的简单图称为完全图。在同构意义下，刀个 顶点的完全图只有一个，记为疋【i 】。偶图( 或二部图) 是指具有二分类( x ，y ) 的 图，它的点集可以分解为两个( 非空) 子集x 和y ，使得每一条边的一个端点在x 中，另一个端点在】，中；完全偶图是指具有二分类( x ，】，) 的简单偶图，其中x 的每 个顶点与y 的每个顶点相连。若l x l = m ，吲= 1 ，则这样的完全偶图记为k 。 1 l 。 2 第一章图谱理论概述 定义1 2 2 1 1 1 图g 的一条途径( 或通道或通路) 是指一个有限非空序列 w = v o e l v l e f f z e k v k ，它的项交替地为顶点和边，使得对1 f 七，q 的端点是k i 和m ，称w 是从到吃的一条途径，或一条( ，心) 途径。顶点和k 分别称为w 的 起点和终点。 若途径w 的边q ，e 2 ，e k 互不相同，则称w 为迹：若途径w 的顶点v 0 ，v , , - - - , 屹和 边e i ，乞，气都互不相同，则称w 为路，记为最+ 。；如果在g 中存在( “，1 ，) 路，规定 “和1 ，是连通的；如果对g 中每一对顶点u ， ，都有一条0 ，d 路，则称g 为连通图， 否则称为非连通图：如果一条途径的起点和终点相同，称这条途径是闭的，闭迹 也称为回路：若一条闭迹的起点和内部顶点互不相同，则称它为圈；长为k 的圈称 为k 圈，记为g ，3 圈常称为三角形【1 1 。 定义1 2 3 1 设g 是一个n 阶( 甩芝3 ) k 正则图。若对任意的“，1 ，y ( g ) ，u ， 满足 ( 1 ) 若“与y 相邻，则i 以) n ( v ) l = 五； ( 2 ) 若“与1 ，不相邻，则l ) n ( 1 ，) l = z ； 则称g 为具有参数( ，l ，k ，兄，) 的强i e 贝, u 图，简称( 以，k ，a ，) 强正则图。 圈c ：i 和g 就分别是( 4 2 ，o ，2 ) 和( 5 ，2 ，0 ，1 ) 的强正则图，而圈e o 5 ) 不是强正 则副。 定义1 2 4 1 1 l 不包含圈的图称为无圈图，连通的无圈图称为树，树常用字母r 表示。 一棵含以+ 1 个点且只有一个点的度为刀的树，记为k 。 定理1 2 1 川设无向图g = ( 乃e ) 是一个( 刀，棚) 图，即顶点数为刀，边数为m 的图，则下列命题等价： ( 1 ) g 是树； ( 2 ) g 是连通的，且m = n l ； ( 3 ) g 中无圈，但在g 中任意不相邻两顶点间增加一条边，就得到唯一一个 圈。 定义1 2 5 1 ，5 1 图g 的邻接矩阵彳( g ) = ( ) 是一个力刀矩阵，其中，如果点m 和 点邻接则吩= l ，否则= o ；多项式( g ，五) = d e t ( 以一彳) 则为图g 的特征多项 式，简记为矽( g ) 。 定义1 2 6 1 1 1 图g 的谱为其邻接矩阵a ( g ) 的特征值的集合，记为s p e cg 或 s p e ca ，其中a 为g 的邻接矩阵。若g 的所有不同特征值为五 五 以，则 s p e c g 表示为 3 电子科技大学硕士学位论文 跚c g = 聊复，耕 若g 是，l 阶图，显然有s n ，掰( 丑) + + 扰( 以) = 月，其中a 为谱半径。 定义1 2 7 1 1 ，4 设图g 是一个刀阶图，其邻接矩阵为a ( g ) = ( 嘞) ，对角矩阵 为d ( g ) = ( d e g g l ，d e 9 6 刀) ，则拉普拉斯矩阵为( g ) = d ( g ) 一么( g ) ；多项式 缈( g ，) = d e t ( , u i l ) 则为图g 的拉普拉斯特征多项式，简记为吵( g ) 。 如下图所示 2 1 ： 它的邻接矩阵和拉普拉斯矩阵分别为： 4 ( g ) = 1 3 同谱图 oll0l l0lo 0 llolo o 0l01 l0o l0 我们考虑如下两个斟2 】： 它们的邻接矩阵分别为【2 i ： c 4u 日 图l lg i ( g ) = 图l - 2g 2 4 3一l l2 1一l o0 一l 0 墨，。 一l0一l l 00 3一l0 一l2一l ol2 第一章图谱理论概述 彳( c 4 u 8 ) = ol0lo l 0 00l o0 o o0 l00 ol 01olo 彳( k 。) = o 0lo o 0ol 00 lloll o 010 o o 01o o 特征多项式为【2 l ： ( c j u 8 ，名) = ( 墨。，五) = 五3 ( 名+ 2 ) ( a 一2 ) ， 谱为【2 】： ( - 202 、 s p e c 肚l l 3lj 。 因此这两个图具有相同的谱，但它们并不同构。它们是阶数( 5 阶) 最小的同 谱但不同构的图，但有一个是不连通的，丽阶数( 6 阶) 最小的同谱但不同构的连 通图为【2 1 ： 图1 - 3g 3 其特征多项式为【2 】： 矽( g i ，五) = 矽( g 2 ，五) = a 6 - 7 3 4 - 4 3 3 - 7 3 2 + 4 3 ，- 1 。 阶数( 8 阶) 最小的同谱但不同构的树为【2 1 ： l l 一 7- i i 图1 4g 4 阶数( 1 0 阶) 最小的同谱但不同构的正则图为【3 1 ： 5 电子科技火学硕士学位论文 图i - 5g 5 以上都是选取的邻接矩阵，而如果选取拉普拉斯矩阵，也存在同谱但不同构 的卧3 】： 图l 石g 6 6 第二章d s 图概述 第二章d s 图概述 “w h i c hg r a p h sa r ed e t e r m i n e db yt h e i rs p e c t r u m ? ”这个问题起源于化学，在 1 9 5 6 年，g u n t h a r d 和p r i m a s 首先提出了这个问题：1 9 6 6 年，f i s h e r 在考虑由k a c 提出的“c a no n eh e a rt h es h a p eo f d r u m ? ”这个问题的时候，也提出了这方面的问 题。事实上，这个问题的答案到目前为止还不知道。我们通常把这个问题简称为 d s ( d e t e r m i n e db yt h es p e c t r u m ) ，相应的图称为d s 图，如果不是d s 图，就简称 为n o n - d s 图1 3 l 。 2 1d s 图 在同谱图的研究中，我们还没有找到简便的方法，有效的判断两个图是否同 谱，更无法从图的自身结构去判定，而目前通常采用的是代数方法，它通过对所 研究的图的谱半径的计算和估计来逐步判断其是否同谱。在文【3 】中，e r v a nd a m 和w h h a e m e r s 对同谱图的研究作了一个全面的概述，并建议研究一些类似树等 结构相对简单的图。 2 2 图乙及其性质 于是，x i a o l i n gs h e n ，y a o p i n gh o u 和y u a n p i n gz h a n g 在文【4 】中研究了一类具 有特殊结构的图：最大度为3 的树。如下图所示【4 】： j + h j + 一l 乙( n 1 ) ( j l 2 ) 睨( n 1 ) 图2 1z n 、t 。和w 。 作者首先根据文献【1 3 】提供的方法，计算出了图乙( ，l 1 ) 的谱： s p e c 彳( 乙) = o 2 c o s ( 觜) ，f = 0 l ，以) ；然后，采用排除法，逐步排除那些可 能与其同谱但不同构的图，得到了如下定理： 7 电子科技大学硕士学位论文 定理2 2 1 1 4 i 图z 。( ，z 1 ) 由其邻接矩阵的谱唯一决定。 我们采用文【4 】中的表示方法，把n ( ，l 2 ) 个图的不交并表示为这种形式： g = 乙。+ 乙，+ + 乙。( 1 ，z 。_ 1 2 ，吩z ，i = l ，2 ，七) 。作者通过排除几个特 殊的子图，又得到了如下的定理： 定理2 2 2 1 4 l 图g = 乙。+ 乙，+ + 乙( 1 ，l ls ? 2 n k ，惕z ，f = 1 ，2 ，k ) 由 其邻接矩阵的谱唯一决定。 当l - - - - - 1 2 = = ，n i z ，i = l ，2 ，k 时，我们把g = 乙+ 乙：+ + 乙可以 简写为g = 坛( 吩- - n z ，扛l ，2 ，k ) 。这时，作者选取了用拉普拉斯矩阵来描述 图，得到了以下定理： 定理2 2 3 1 4 i 图乙和红分别由其拉普拉斯矩阵的谱唯一决定。 定义2 2 1 1 2 1 在图g 中，我们把边集e ( g ) 看作点集，两条边相邻看作是两个 点邻接，这样得到的图称为线图，记为( g ) 。 定理2 2 4 1 6 1 4 i 如果图g 和图日的线图同构( g ) 兰三( h ) ， g ，h ) 墨，k ，) ， 那么g 兰日。 接着，作者利用线图的性质，分别证明下面两个定理： 定理2 2 5 1 4 1 图由其拉普拉斯矩阵的谱唯一决定。 定理2 2 6 1 4 l 图形由其拉普拉斯矩阵的谱唯一决定。 定义2 2 2 1 5 1 在一棵树中，有且只有一个顶点的度数大于2 ，这样的树称为星 形树。 定理2 2 7 i s , 1 5 在星形树中，不存在一对同谱但不同构的星形树。 2 3f 形树及其性质 在文【5 】中，w dw a n g 和c h e n g x i a nx u 定义了一种图：r 形树( 最大度为3 的星形树) 。为了准确描述r 形树，作者用t “，厶，厶) 表示r 形树，不失一般性， 假设ls t , 乞厶，z ，i = l ，2 ，3 。r ( ，乞，厶) 一 ，= 气u 气u 气，其中置是含有个 点的路径，1 ，为r 一形树中唯一的3 度点。当= l ，厶= l ，3 = n - 1 时，t ( ，厶，厶) 为 乙；当= 2 ，厶= l ，3 = 刀一2 时，t ( ，乞，毛) 为瓦，因此可以看成是图乙和乙的推 广，r 形树如下图所示： 8 第二章d s 图概述 一一下一一 l 2 “，2 ，毛) 图2 - 2t - 形树 为了估算r “，乞，毛) 的谱半径的范围，作者引用了文献 1 6 q h 的定理，这个定 理的证明提供了一种很有用的方法，在谱半径的估算中，发挥了重要的作用，在 后面的估算中，将会体现出来。这个定理如下所示( 证明见【5 ，1 6 】) ： 定理2 3 1 s 嘲设a 为图t ( ，厶，1 3 ) 的谱半径，则a 2 ，c 3 或者口= 2 ，b = 2 ， c 2 或者a = 2 ，b = 3 ，c ：3 ； ( 2 ) q ( a ，b , c ) 当( 口，玩c ) ( 2 ，l ，3 ) ，( 3 ，4 ，3 ) ，( 3 ，5 ，4 ) ，( 4 ，7 ，4 ) ，( 4 ，8 ，5 ) ，或者a l ， f 口+ c 口 3 ， c l ，b 6 ( 口，c ) ，且( 口，c ) ( 2 ，2 ) ，其中6 ( 口，c ) = 2 + c ，口= 3 ，。 【一l + g 口= 2 定理2 4 2 1 1 7 iq ( a ，b ，c ) 中所有最大特征值在区间( 2 ，4 2 + ；】范围内的图都是 d s 图。 定理2 4 3 1 1 7 1 所有最大特征值在区间( 2 ，x 2 + 5 】范围内的连通图都是d s 图。 在文【1 7 】中，作者把以上结果作了进一步的推广，得到了如下结果： 定理2 4 4 除了图形o 2 ) ，t ( 2 ，2 ，2 ) 和墨。外，所有最大特征值不超过 2 + 5 的连通图都是d s 图。 2 5 本章小结 到目前为止，除了以上这些d s 图外，还有完全图k ，空图( 即没有边的图) ， 只有一条边的图，在完全图e 上少一条边的图，度数为2 的正则图( 圈) 和度数 为力一3 的正则图也是d s 卧7 】。在文【3 】中，作者还列举了大量结构非常特殊的d s 图，如某些强正则图( 圈c 4 和g ) 也是d s 图，但总的来说，还是很少，而且还 1 0 第二章d s 图概述 没有有效的判断方法。 电子科技大学硕士学位论文 第三章图谱理论的重要定理 在这一章中，我们将介绍图谱理论的重要定理，这些定理在后面的证明中起 了非常关键的作用。 3 1 图的特征值的基本性质 定理3 1 1 1 1 1 设g 是具有直径d 的以阶连通图，则 ( 1 ) g 的不同特征值的个数在d + l 与刀之间； ( 2 ) 设五是力阶图g 的任一特征值，l 为边数，则 川1 2 m ( n - 1 ) 。 定理3 1 2 1 1 0 设彳是n 阶连通图g 的邻接矩阵，a = ( g ) ，则有 ( 1 ) 对g 的每个特征值名，均有s a ； ( 2 ) a 是g 的特征值当且仅当g 是正则的；进一步，若是g 的一个特征值， 则重数坍( ) = 1 ； ( 3 ) 若一是g 的一个特征值，则g 是正则偶图； ( 4 ) 若g 为偶图且五是g 的一个特征值，则一五也是g 的特征值，并且 m ( - 2 ) = m ( 五) 。 定理3 1 3 1 设彳= ( ) 是刀阶连通图g 的邻接矩阵，万= 万( g ) ，a = ( g ) ， 则有 ( 1 ) g 的最小特征值丸o ，若g 非空( 可以不连通) ，则以一l ； ( 2 ) g 的最大特征值元满足 万4 a ； ( 3 ) 对g 的任一个导出子图日，有 k ( g ) 九蛔( h ) 缸( h ) k ( g ) 。 定理3 1 4 l l 设么( g ) 的谱为s p e e a ( g ) = ( 朋复) 掰复) ：掰复) ) ，则 , n a 2 = 2 m ， 其中啦是特征值五的重数，m 为g 的边数。 1 2 第三章图谱理论重要定理 定理3 1 5 ( 内插定理眩n 1 ) 设g 是一个图，它的谱为a 五五，又设 g h 的谱是以鸬以- i 则后者插入到前者中去，即 h 五芝鸬以一i 五。 3 2 特殊图的谱半径 定理3 2 i ( d m c v e t k o v i c ，m d o o b ，i g u t m a n i z , s 1 ) 若2 一 人户 丫 图3 - 1g t 同时，若丑 0 ) 是矽( g ，五) 的一个单根： ( 2 ) 若五是g 的任一个其它特征值，则一丑a 丑； ( 3 ) g 的任一条边被删去，最大特征值都将减小。 定理3 3 2 f 3 i 对栉刀矩阵么和曰，则下列性质相互等价： ( 1 ) a 和曰同谱； ( 2 ) a 和曰有相同的特征多项式； ( 3 ) t r ( a ) = t r ( b ) ，且f = l ，2 ，刀。 如果4 是图的邻接矩阵，那么t r ( a ) 表示长度为f 的回路的总数。因此同谱图 有相同数目的长度为f 的回路。特别的，当i = 2 时，它们的边数相同；当f = 3 时， 它们含有相同数目的三角形。 定理3 3 3 m 在任何简单无向图中，长度为4 的闭回路数目等于边数的两倍、 导出子图是长度为2 的路径的数目的4 倍和长度为4 的圈的数目的8 倍的总和。 定理3 3 4 0 卅如果图】，是图x 的子图，则k ( d k ( 的，并且当y 是一个合 适的子图时，等号在图x 是非连通图时成立。 1 4 第三章图谱理论重要定理 定理3 3 5 1 加i 若图g 是简单无向图，y 是图g 中的一个点，用以v ) 表示图g 中 所有包含点y 的圈，则 ( g ，五) = 五矽( g u a ) 一事6 ( g - v - w , a ) - 2 f 6 ( g - v ( g ) ，名) ， 如果图g 为空图时，则矽( g ，兄) = i 。 下面的两个定理在后面两章中起了很重要的作用，主要用它们来估算图的谱 半径。 定理3 3 6 。5 若图g 是由图q 、红的不交并qu ，通过一条边嵋屹连接图 羁中的点嵋和图皿中的点v 2 ，那么 ( g ) = 矽( q ) ( 月r 2 ) 一矽( q 一嵋) 矽( q 一屹) ， 式中皿一表示从图耳中删去点k 和与其相关联的边( f = l ，2 ) 。 定理3 3 7 0 5 0 若c ：l ，只分别表示含有捍个点的圈和路，那么 孵，舻n ( a 一2 c o s 孕) = 2 c o s ( 以a r c c o s 2 2 ) _ 2 ， 纰= 冉m 2 c o s 熹，= 等等。 设名= 2 c o s o ，t 牝- - e 诏，为了便于计算，我们把g ，e 的特征多项式改写成 如下形式： ( c ：，t “2 + f i 2 ) = t 州2 + f 一卅2 2 ，( 3 1 ) 矽( 只，t 1 7 2 + f 一2 ) = f 一叫2o “一1 ) ( t 1 ) 。( 3 2 ) 电子科技大学硕士学位论文 第四章图眈的一些性质 4 1 图职和己的基本性质 我们在这节利用文【5 】中提供的思想和方法，对图2 和e 的谱半径做一些计算 和估计。我们考虑两种最简单的情况：根据图q 。的定义，当 = 3 ，肌_ - - i , 时，为 了方便起见，我们把图q 3 。简记为见；在图见的基础上作一些变化，恰好具有两 个三度点，也就是圈g 和树e 通过一条边连结而成的图，记为e 。当忍= 3 时，树 e 成为路径b ，图弓就是由路径b 中的2r g 点通过一条边与圈c 3 相连结而成的 4 一一二4 一一一l 根据定理3 3 1 ，图见随着刀的增大，其谱半径也逐渐增大，这在图d i 、d 2 的 五( 毛) 五( 日) 丑( e ) 2 2 8 1 7 ，在下面的引理中，我们将对图e o 5 ) 运用定理 马k j 图牝g 8 1 6 第四章图队的一些性质 我们用m a t l a b 直接计算其谱半径： a ( 日。) = 2 3 4 2 9 ，五( 也) = 2 3 0 2 8 ，五( k t j ) = 4 5 。 最后，我们介绍两个图( 这里我们采用文献 5 】中作者给出的定义) ：由两个图 的不交并( 一个为e ，另一个为g ，) ，通过一条路径连结这两个圈( 路径可以压 缩为一点) 构成，此图记为且【5 】；在一个圈中，用一条路径连结圈中任意两点得 到的图记为h 4 1 5 ( 于是得到两个圈，一个为e 。，另一个为c i ) 。 ， ， 、 ，、，、 ，、，、 ，t， ； n l j j n 2 j i t 一一一- j ， ， 、 ， 、 ， 、，一， ， 马 图4 3g 9 4 2 图仇和e 的谱半径估计 ，、 ，、 ，7 。，1 ： 、哼 i l l j 、 ， 、 ， 、 7 、- 一， h i 引理4 2 1 若丑( q ) ，丑( e ) 分别是图见，e 的谱半径，那么 3 4 2 a ( 侥) 5 a ( e ) 2 2 8 1 7 。 证明：我们设图见和e 的阶数为n + 3 ，由定理3 3 6 ，我们得到如下等式： 痧( p 。) = 妒( 只) ( c j ) 一( 一。) ( ) ， 矽( e ) = ( f ) ( c ；) 一( f 一。) ( 最) 。 把等式( 3 1 ) 和( 3 2 ) 代入上面的等式，矽( 见) 和矽( 巨) 变形为： o ) ：= 寿【( 广“- 1 ) ( 卜1 ) ( f 非批_ 2 卜0 4 _ 1 砸3 _ 1 弘叫2 卜o 少瓦( f ) ：! 三兰箬【o 一一+ 1 ) ( t ，2 + t 叫z 一2 ) 一( t 一- 2 + 1 ) ( f 3 z + f 啦一f l 2 ) 】= o 。 进一步化简得： q ) = 三胆( f 2 一f 一2 t v 2 - 1 ) + ( f 们+ f 叫2 一t - 3 2 + 2 ) 】 = i i t 斛v 2 0 + f 吖2 + 1 ) o f 啦一1 ) + o 啦+ f 一啦一f 叫2 + 2 ) 】 = 昏删2 ( t + t v 2 + 1 m 啦一学m 牝一学肿v 2 + t - i 2 _ t - 3 2 + 2 ) 】 = 0 1 7 塑笙堑塑主堂堡垒塞 ( f ) = 篙矿( t 2 - - t - - 2 t i 2 - 1 ) + ( 卜2 ：十1 ) 】 = 篱矿啦+ 1 ) ( f - t v 2 - 1 ) + ( f 2 砌驰十1 ) 】 = t q 丽+ 1 - 2 【f ”( t + t l 2 + 1 ) ( t , 2 1 - ，, 5 ) ( ? 2 1 +022，32一，1)】2,59 = 0 。 一 设锄，乞分别为方程o ) ，o ) 的最大的根，那么 由艳学时，渺i jf d - o ，则t 2 8 5 6 1 ； 另一方面，由于( 2 ) 2 v 2 + 2 一l 2 3 压， a ( 乜) = 么啦+ t 叫2 ( 华啦+ ( 半广：压， 丑( 瓦) = t v 2 + 乞一v 2 ( 2 8 5 6 1 ) v 2 + ( 2 8 5 6 1 ) i ：2 2 8 1 7 ， 于是此引理成立。 证毕 引理4 2 2 若五( 绒) ，五( 乜) 分别是图绒，吃的谱半径且满足l 垅 ，l ，那 么 ( 1 ) 3 压 a ( 见) ( 织) 垢； ( 2 ) 五( 吃) 不是图d 的特征多项式的根。 证明：由定理3 3 1 ，我们得到 五( 见) a ( 乜) ， 再利用引理4 2 1 ，即得 一 第四章图珥的一些性质 _ = 二二一一 3 扼 五( 见) 五( 见) 括， 于是结论( 1 ) 成立。 由定理3 3 6 ，我们得到 矽( 见) = ( d 靖) ( e 。) 一( 见一。) ( 只一。一。) ， 设矽( d m ，力) = o 为图绒的特征多项式方程，所以矽( 绒，五( 或”= 0 ，将 ( d m ) 代入 ( 或) 得 矿( 见，五( 见) ) = ( d 埘，a ( d 卅) ) ( 只m ，a ( 见) ) 一( d 用小丑( 绒) ) ( 只- m - i 五( 绒) ) ， 又因为 五( 哦一) 五( d 厢) ， ( 一。一。) ( 一。) 2 3 乏， 所以 痧( 乜，丑( 见”= ( d 册，五( d ) ) 矿( - m - ! 五( 绒” o ， 那么丑( d 肼) 不是图见的特征多项式的根，结论( 2 ) 成立。证毕 引理4 2 3 若a ( 瓦) ，a ( e ) 分别是图，e 的谱半径且满足3 ，z ，l ，那 么 ( 1 ) 压 五( e ) a ( 疋) 2 2 8 1 7 ； ( 2 ) 丑( 疋) 不是图e 的特征多项式的根。 证明：由引理4 2 1 ，我们得到 嘣忙篇矿( t 2 - t - 2 t l 2 - 1 ) 托z 劫3 2 十1 ) 】= o ( f 3 i ：筹【t m ( f l - t - 2 t 啦- 1 ) 托z 砌3 2 十1 ) 】：o 。 设t ，乞分别为方程( f ) ，m 的最大根，则( 乞) = o ，由于 掺地警地 于是 乞“( 2 一乞一2 t t z _ 1 ) + ( 乞22 龟班一乞- 1 ) = 0 ， 变形为 乞4 ( 乞2 一t 一2 乞t 2 - 1 ) 一( 2 乞2 + 乞+ l - r e , 2 ) = o ， 所以 1 9 电子科技人学硕士学位论文 t e 4 ( 乞2 一t e 一2 t 2 一1 ) 一( 2 3 7 2 + + l t 2 ) o ， 从而 ( 乞) 0 ， 乞，丑( e ) a ( e ) ， 所以由引理4 2 1 ，即得 4 5 a ( e ) ( 见) ，丑( 见) 4 5 五( e ) 。 如果图目与图g 同谱，但不同构，那么图4 , “= l ，2 ) ，k j 和图e 均为图h 的 禁止子图( 如果图g 的任何子图都不与图r 同构，那么图r 就称为图g 的禁止子 图【5 】) 。 我们考虑如下情况： 如果图日与图g 同谱，但不同构，那么由定理3 3 2 知图h 必包含n + 3 个点和 捍+ 3 条边。 情况l ：图日为连通图。 ( 1 ) 如果图h 只包含一个圈q ( 3 a ( 见) ，a ( q ) 4 5 ( 巨) ， 于是图日不可能包含结构为图皿o = l ，2 ) ，也或图e 的图作为子图，所以图h 的 这个分支的结构为图吃( 1 m 万) ，由引理4 2 2 知， 3 4 2 ( 见) 五( g ) ， 这与假设矛盾，因此图日与图g 不可能同谱。 ( 3 ) 若e ( 扛3 ，4 ) ( t h 3 ，嘭 3 ) 是图h 中一个分支的子图，由定理3 3 2 知图 日中同样只有一个分支包含圈c t ，那么从情况2 的第一种情况可知，图日的这个 分支的结构为图u ( 1 m 靠) ，由引理4 2 2 知， 3 4 2 丑( 或) 五( 见) 5 ， 且五( 见) 不是图见的特征多项式的根，图h 至少有一个特征根与图g 不一样，因 此图日与图g 不可能同谱。 综上所述，图h 要与图g 同谱，只有与图g 同构，所以图g 由其邻接矩阵的 谱唯一决定。证毕 4 4 图厶由其邻接矩阵的谱唯一决定 定理4 4 1 若g = e 伽3 ) ，那么图g 由其邻接矩阵的谱唯一决定。 证明：我们假设图日与图g 同谱，但不同构，那么由定理3 3 2 知图h 必包含 n + 3 个点和n + 3 条边。 为了完成其证明，我们考虑如下情况： 情况l ：图日为连通图。 ( 1 ) 如果图日只包含一个圈c 卅( 3 优 阼) ，那么由定理3 3 2 知图日必包含圈 g ，这与假设矛盾。 ( 2 ) 如果图h 只包含一个圈g ，由于图日与图g 同谱，所以图鼠( f = l ，2 ) 均 为图h 的禁止子图，而根据引理4 2 1 ， 五( 见) 4 5 a ( e ) ， 所以图日不可能为图见。又因为图日必与图g 不同构，所以图日必包含如图“ 所示的结构皿作为子图，图风是由囤g 和f 形树的不交并，通过一条边，连结 圈g 中的一个点和丁型树中的一个一度点得到。考虑图日中的子图乜( 3 朋 n ) ， 由引理4 2 3 可知， 2 1 电子科技大学硕士学位论文 ； 五( e ) ( 乜) 2 2 8 1 7 ， 从而 a ( e ) a 饵) ， 也就是说图e 中的两个3 度点距离越小，其图的谱半径越大。因此，图日的谱半径 比图e 的谱半径大，这与假设矛盾。 4 一上 h s 图4 4 h 5 情况2 ：图日为至少含有两个连通分支的图。 ( 1 ) 如果图日的每个分支只包含一个圈，那么由定理3 3 2 知图日其中只有一 个分支包含圈e ，由于 ( 乜) 4 5 a ( 乓) a ( 鼠) o = l ，2 ) ， 于是图h 不可能包含结构为图e o = 1 ，2 ) 作为其分支或子图，所以图h 的这个包 含圈