（基础数学专业论文）谱在图能量及图排序中的应用.pdf

摘要 谱图理论主要研究图的谱性质和图的结构性质之间的关系，期望通过谱 性质来刻画结构性质谱图理论在结构化学中的一个应用就是：通过对有机分 子建立图模型，应用图的特征值定量分析其能量级和稳定性，从而产生图的能 量的概念 本文主要研究；( 1 ) 单圈图的能量在删边情形下的变化情况，以及图的 l a p l a c i a n 的能量的积分表达形式；( 2 ) 按照图的l a p l a c i a n 谱半径。对含有相 同顶点数的单圈混合图进行排序 g u t m a n 和h o u 等人对树和单圈图的极端能量已给出明确的刻画本文 从另一个角度考虑图的能量问题，即图在局部变化下。其能量的变化情况针 对于单圈图，我们发现：边的删除一般会导致能量的减少，但是对某些单圈图 也会存在例外的情形，即删边导致能量的增加 2 0 0 5 年，g u t m a n 和z h o u 把图的l a p l a c e 特征值引入到图的能量中，给出 了图的l a p l a c i a n 能量的定义对于正则图，图的能量与图的l a p l a c i a n 能量是 一致的考虑到图的能量有一个非常优美的c o u l s o n 积分公式图的l a p l a c i a n 能量是否也有一个类似的表达形式呢? 我们给出了图的l a p l a c i a n 能量的若干 积分形式 根据图的谱半径( 或其它极端特征值) ，对一些图类( 如树，单圈图等) 进行 排序，可以了解这些图类的一些极端性质近期，f a n 确定了l a p l a c i a n 谱半径 达到最大的非奇异单圈混合图，并与t a m 和z h o u 刻画l a p l a c i a n 谱半径达到 最大的双圈混合图对含相同顶点数的所有单圈混合图，我们按照l a p l a c i a n 谱半径的大小，分别确定了谱半径达到最大，次大和第三大的单圈图 本文组织结构为：第一章介绍谱图理论及图的能量的简要背景，常用的概 念和术语，以及研究问题和研究结果；第二章主要讨论单圈图在删除一条边 后能量的变化问题；并给出l a p l a c i a n 能量公式的积分形式；第三章则对单圈 混合图按照l a p l a c i a n 谱半径进行排序 关键词：图；能量；l a p l a c i a n 能量；l a p l a c i a n 谱半径 a b s t r a c t t h es p e c t r a lg r a p ht h e o r ym a i n l ys t u d i e st h er e l a t i o n sb e t w e e nt h es p e c t r a lp r o p e r t ya n dt h es t r u c t r u ep r o p e r t yo fg r a p h s ，a n dn s e st h es p e c t r a lp r o p - e r t yt oc h a r a c t e r i z et h es t r u c t r u ep r o p e r t yo fg r a p h s a ni m p o r t a n ta p p l i c a t i o n o fs p e c t r a lg r a p ht h e o r yi ns t r u c t u r a lc h e m i s t r yi sa sf o l l o w s b ye s t a b l i s h i n g g r a p hm o d e l so fo r g a n i cm o l e c u l e sa n da p p l y i n gt h ee i g e n v a l u e so ft h eg r a p h s ， w et h e nh a v eaq u a n t i t a t i v ea n a l y s i so fe n e r g yl e v e l sa n ds t a b i l i t i e so ft h e o r g a n i cm o l e c u l e s ，w h i c hl e a d st ot h ec o n c e p t i o no fg r a p he n e r g y t h i st h e s i sm a i n l ys t u d i e s ( 1 ) t h ev a r i a t i o no fe n e r g yo fa u n i c y c l i cg r a p h b yd e l e t i n ga ne d g e ，a n dt h ei n t e g r a lf o r m u l ao fl a p l a c i a ne n e r g yo fag r a p h ， a n d ( 2 ) t h eo r d e ro fu n i c y c l i cm i x e dg r a p h so i lt h es a m en u m b e ro fv e r t i c e s a c c o r d i n gt ol a p l a c i a ns p e c t r a lt a d i n s g n t m a na n dh o ue t a 1 h a v eg i v e nc l e a rc h a r a c t e r i z a t i o n so ft r e e sa n d u n i e y c l i cg r a p h sw i t he x t r e m ee n e r g i e s i nt h i st h e s i s ，w ed i s c u s st h ev a r i a t i o n o fe n e r g yo fa g r a p ha f t e ra l o c a lc h a n g e f o ru n i c y c l i cg r a p h s ，w ef i n dt h a ti n g e n e r a le n e r g yd e c r e a s e si fd e l e t i n ga ne d g e b u ti ti sn o tt r u et os o m es p e c i a l u n i c y c l i cg r a p h s i n2 0 0 5 g u t m a na n dz h o ui n t r o d u c e dt h el a p l a c ee i g e n v a l u e st ot h e g r a p he n e r g y , a n dg a v et h en o t i o no fl a p l a c i a ne n e r g yo fag r a p h ，w h i c hi s c o n s i s t e n tw i t ht h ee n e r g yo fag r a p hf o ra l lr e g u l a rg r a p h s i nt h i st h e s i s ， w eg i v es o m ei n t e g r a lf o r m u l a so fl a p l a c i a ne n e r g yb a s e do nc o u l s o ni n t e g r a l f o r m u l a a c c o r d i n gt os p e c t r a lr a d i u so fg r a p h s ( o ro t h e re x t r e m ee i g e n v a l u e s ) ， o n ec a no r d e rs o m ec l a s s e so fg r a p h s ( f o re x a m p l e ，t r e e sa n du n i c y c l i cg r a p h s ) ， w h i c hw i l lh e l pu su n d e r s t a n ds o m ee x t r e m ep r o p e r t i e so fg r a p h s r e c e n t l y f a nc h a r a c t e r i z e dt h en o n s i n g u l a ru n i c y c l i cm i x e dg r a p h sw h o s el a p l a c i a n s p e c t r a lr a d i u sa t t a i n st h em a x i m u m ，a n d a l s oc h a r a c t e r i z e dt h eb i c y c l i cm i x e d g r a p h sw h o s el a p l a c i a ns p e c t r a lr a d i u sa t t a i n st h em a x i m u mw i t ht a m a n d z h o u i nt h i st h e s i s w ed e t e r m i n er e s p e c t i v e l yt h eg r a p h sw h o s el a p l a c i a n s p e c t r a lr a d i u sa r et h el a r g e s t ，t h es e c o n dl a r g e s ta n dt h et h i r dl a r g e s ta m o n g a l lu n i c y c l i cm i x e dg r a p h sc o n t a i n i n gt h es a n l en u m b e ro fv e r t i c e s t h eo r g a n i z a t i o no ft h i st h e s i si sa 8f o l l o w s i nc h a p t e r1 ，w ei n t r o d u c ea b a c k g r o u n do fs p e c t r a lg r a p ht h e o r ya n dg r a p he n e r g y ，s o m ec o n c e p t i o n sa n d n o t a t i o n s ，a n dt h er e s e a r c hp r o b l e m sa n dr e s u l t s i nc h a p t e r2 ，w ed i s c u s s t h ec h a n g e so fe n e r g i e so fu n i c y c l i cg r a p h sb yd e l e t i n ga l le d g e ，a n dg i v es o m e i n t e g r a lf o r m u l a so fl a p l a c i a ne n e r g yo fag r a p h i nc h a p t e r3 ，w eo r d e r u n i c y c l i cm i x e dg r a p h sb yt h e i rl a p l a c i a ns p e c t r a lr a d i u s k e y w o r d s ：g r a p h ；e n e r g y ；l a p l a c i a ne n e r g y ；l a p l a c i a ns p e c t r a lr a e d i u s 符号 【n j n e ( g ) l e ( g ) c a ( g ；z 1 钆( g ；) a p ( g ) m ( g ，k ) 符号说明 说明 同构 不大于n 的最大整数 不小于n 的最小整数 图g 的能量 g 的l a p l a c i a n 能量 a ( g ) 的特征多项式 l ( g ) 的特征多项式 a ( a ) 的特征值 l c g ) 的特征值 图g 的最大度 g 的k 一匹配数 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得宝截天学或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：澎淘蹙 签字日期：口了 年4 月塘日 学位论文版权使用授权书 本学位论文作者完全了解宝徽聪有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授破徽：夭扫以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 学位墨笔篓篙解誓誓椴篡二名：影琵磁学位论文作者签名：汐、涵赢 导师签名：7 乙儿彰之 签字日期：2 d 0 年年月偿日签字日期：沙，刁年f 月3 护日 学位论文作者毕业去向： 工作单位： 电话： b 7 6 5 毕t z 辱- 7 通讯地址：邮编： 第一章引言 第一章引言 1 1简要背景 谱图理论的主要研究图的各种矩阵表示( 主要是l a p l a c e 矩阵和邻接矩阵) 的代数与组合性质，通过建立矩阵的谱性质( 如特征值和特征向量) 与图的结 构性质( 如图的不变量) 之间的联系，期望用矩阵的谱性质来刻画图的结构性 质 图的邻接谱的研究最早源于量子化学研究领域由h i i c k e l 【1 】于1 9 3 1 年 引进的对非饱和碳氢化合物的一种近似处理产生了对应分子的图论模型，其 中图的特征值被用来表示特定电子的能量级很多年以后，h i i c k e l 模型与谱 图的数学理论之间的联系在【2 】和【3 1 中才被认识到，并且从此被众多化学家 和数学家广泛的开发利用 图的l a p l a c e 谱是图谱理论中的另一研究领域与图的邻接谱的研究相 比，尽管早在1 8 4 7 年g k i r c h h o f f 已将图的l a p l a c e 谱用于电流网络的研究并 给出了著名的矩阵树定理【4 】，图的l a p l a c e 谱的研究受到人们普遍关注则是 近几十年的事情在七十年代初期，通过图的l a p l a c e 矩阵在一些文献【5 ，6 】 中的出现，人们才逐渐地认识到它由于图的l a p l a c e 谱比图的邻接谱包含的 信息多，而且更加自然和重要，近年来成为谱图理论的一个非常活跃的研究专 题综述文章r m e r r i sm ，b m o h a r 【8 ，9 】等详尽叙述了l a p l a c e 谱研究中的 若干专题以及应用 由于h i i c k e l 的工作，研究者应用谱图理论研究结构化学中有机分子的能 量级和稳定性给定非饱和碳氢化合物，其结构可以用分子图来表示分子 的电子能量级实际上就是对应图的邻接矩阵的特征值的绝对值之和分子的 稳定性及相关的化学性质与图的谱性质有着紧密的联系【1 0 】最近g u t r a a a 等 人【l l ，1 2 ，1 3 1 发现饱和的碳氢化合物( 即烷烃) 的光电子谱与潜在的分子图的 安徽大学硕士学位论文：谱在图能量及图排序中的应用 l a p l a c e 特征值也存在着联系 1 2概念与记号 设g = ( k e ) 为n 阶简单图，其顶点集为v = v ( g ) = 饥，v 2 ， ，其边 集为e = e ( g ) 顶点f v 的邻域定义为 r g ( 口) = “：u 口毋若n g ( v ) = 0 ， 则称为”为g 的孤立点”的度d g ( ”) 是指g 中与”关联的边数g 的 最大度与最小度分别记为g 和如在不相混淆的情形下，上述分别简记为 扣) ，d ( ”) ，a ，6 图g 称为正则的，如果它所有顶点的度都相同 坼，g ，耳和坼分别是r 个顶点的完全图，圈，路，和有r 个孤立点的简 单图对于路p r ，用形式b = ? j l t ，2 坼表示异的边为v l v 2 ，v 2 v 3 一v r 1 v r 设g = ( k e ) 为简单图如果如( g ) = 1 ，顶点口v 称为g 的悬挂点 若顶点“v 与一个悬挂点相邻，则称u 为g 的准悬挂点如果e 是g 的一 条边，用g e 记g 删去边e 后所得到的图更一般地，用g 一 e - ，e 女) 记 g 删去边e 1 ，e 女后所得到的图设 y ( g ) ，g 一口记图g 删去顶点”以及 所有与口关联的边后所得到的图 在图论中，还有一个很重要的的概念：图的匹配g 中由不相邻边构成 的任一个集合称为是g 的一个匹配g 的一个匹配称为完美的，如果该匹配 里的边关联g 的所有顶点如果g 的一个匹配含有k 条边，则称该匹配为g 的k 一匹配显然，k 一匹配与k 个k 2 拷贝的子图相关记图g 的 - 匹配 数为m ( g ，七) 特别的，m ( g ，1 ) 恰为g 的边数。约定m v ，0 ) = 1 注意到一个 k 一匹配覆盖2 k 个顶点，因此对n 阶图g 来说，当k , q 2 时，匹配不存在； 故，只要k n 2 ，则m ( g ，k ) = 0 设g = ( k e ) 为含n 个顶点和m 条边的简单图图g 的关联矩阵b = 】 定义如下。如果顶点吩在边e i 上，定义= l ；否则，定义b 0 = 0 易见， b 是m n 的( 0 ，1 ) 一矩阵图g 的定向关联矩阵c = 陋力定义如下：给图g 一个定向，定义勺= 1 ，如果顶点是边e 起点；定义c 4 i = 一1 ，如果顶点吩 是边q 终点；对于其他情形，定义c 4 j = 0 易见，c 是m n 的( 0 ，1 ，一1 ) 矩 2 第一章引言 阵称d = d ( g ) = d i a g d ( v 1 ) ，d ( 2 ) ，d ( ) 为图g 的度对角矩阵图g 的 邻接矩阵a = a ( g ) = 【a i j 】定义为；若啦与相邻。则= l ；否则叼= 0 容易验证：c r c = d ( g ) 一a ( g ) ；l ( g ) 上述矩阵l ( g ) 称为图g 的l a p l a c e 矩阵( 1 4 1 ) 下面给出混合图及其矩阵表示设g = ( k e ) 是一个简单混合图，顶点 集v = v ( g ) = 1 ，抛，) ，边集e = e ( g ) = e l ，e 2 ， ，其中e ( g ) 含有若干有向边，若干无向边可以发现，简单混合图是由简单图通过对其部 分边定向而获得边e e ( g ) 的符号s g n e 定义为：如果边e 是无向边，则 s g n e = 1 ；如果e 是有向边，则s g n e = - 1 如果q 巧e ( g ) ，令啦j = s g n ( v i v j ) ， 否则a i j = 0 a ( g ) = ( 0 0 称为图g 的邻接矩阵g 的关联矩阵定义为竹m 阶矩阵m = m ( g ) = p m ，】：如果e j 是一条与姚相邻的无向边或者是头为 的有向边，元素m j 的赋值为m 订= l ；如果勺是一条尾为的有向边，元 素r a i j 的赋值为”玎= l ；否则元素盯w = 0 ，图g 的l a p l a c e 矩阵定义为 l = l ( g ) = m m r = d ( g ) + a ( g ) ，其中m r 是关联矩阵m 的转置 1 3研究问题及主要结论 下面简要介绍本文所研究的问题，以及所取得的一些主要结论我们所获 得结论的编号均采用它们出现在各自章节中的编号本文主要讨论了如下问 题；( 1 ) 单圈图的能量在删边情形下的变化情况，以及图的l a p l a c i a n 的能量 的积分表达形式；( 2 ) 按照图的l a p l a c i a n 谱半径，对含有相同顶点数的单圈 混合图进行排序，包括最大图，次大图与第三大图的刻画 一图的能量与l a p l a c i a n 能量 图的能量定义为图的邻接矩阵的特征值的绝对值之和具体地，设g 为一 个n 阶图，a ( g ) 为它的邻接矩阵设a ( g ) 的特征值为a 1 ( g ) ，a 2 ( g ) ，a 。( g ) 图g 的能量定义为( 1 0 】) ： e ( g ) = 眦g ) 3 安徽大学硕士学位论文；谱在图能量及图排序中的应用 图的能量可以追溯到1 9 3 1 年h f i c k e l 【1 】对有机分子的能量级表示的工作 他对非饱和碳氢化合物作了一种近似处理，获得了对应分子的图模型，并用图 的特征值表示特定电子的能量级从此他的工作被众多的化学家和数学家广 泛推广和深入研究，获得了一些有意义的结论 1 5 ，1 6 ，1 7 ，1 8 】近期，h o u 和 g u t m a n 分别刻画了能量极大【1 9 】和能量极小【2 0 】的单圈图，并对双圈图和二 部图的能量也进行了类似的讨论【2 1 ，2 2 】 我们在2 1 节讨论单圈图的能量在删边情形下的变化情况对于后者，我 们发现：边的删除一般会导致能量的减少；但是对某些单圈图也会存在例外 的情形，即删边导致能量的增加，见图2 1 3 这方面的工作还需要进一步地探 讨主要结论有； 记g ( mz ) 为含n 个顶点的单圈图的集合，且单圈图中的圈的长度为1 定理2 1 5 设g 9 ( 竹，j ) 且l 0 ( m o d4 ) ，t ”是圈q 上任意一条边则 g t o 的能量小于g 的能量，即 e ( g ) e ( a u 口) 定理2 1 6 设g g ( n ，z ) 且z i0 ( r o o d4 ) ，g 是由圈q 在其某个顶点 附 加n f 条悬挂边所获得，如图2 1 2 的图( i i ) 所示设u ”是圈a 上的一条边 ( u 埘， ”) 则g 一删的能量小于图g 的能量，即， e ( g ) e ( a t 口) 如前所述，图的能量定义为图的邻接矩阵的特征值的绝对值之和2 0 0 5 年，g u t m a n 和z h o u 【2 3 】把图的l a p l a c 矩阵的特征值引入到图的能量定义 中设g 为一个含m 条边的n 阶图，l ( g ) 为它的l a p l a c e 矩阵设l ( g ) 的 持征值为弘l ( g ) ，舰( g ) ，鲰( g ) 。图g 的l a p l a c i a n 能量定义为( 【2 3 】) ： =卦(gle(g) 一斟 = 旧) 一等| i = l 注意到百2 m 即为图g 顶点的平均度当g 为正则图时， l e ( g ) = e ( g ) 4 第一章引言 g u t m a n 和z h o u 在【2 3 】中给出图的l a p l a c i a n 能量的看十性质关于图的 l a p l a c i a n 能量的研究还处于开始阶段，结论还不多见 考虑到图的能量有一个非常优美的c o u l s o n 积分表达形式【1 0 图的l a p l a - c i a n 能量是否也有一个类似的积分表达形式呢? 我们在2 , 2 节对此问题展开 研究，获得了如下结论，其中九( z ) = d e t ( x i 一三( g ) ) 为图g 的l a p l a c e 矩阵 l ( c ) 的特征多项式 定理2 2 1 若g 是一个含礼个顶点和m 条边的图，则 冽g ，= ；e n 吨此( 鲫蚪鲁) 肌( g ；i x + 等) 出 = ；e 卜一z 扩d 钆( g ；i x + 警) 卜 定理2 2 2 若g l 和g 2 是两个具有相同顶点数n 和边数m 的图，则 冽刚一c 矧= ；e - n 瓯k + 等) ，钆( g 2 ；i x + 驯如 定理2 2 3 若g 是含n 个顶点和m 条边的图设妒( g ；z ) = ( 一h p 札( g ；i x 一1 ) 则 船= 昙e 。- 2 k ；( 。一一等测卜 二单圈混合图的序 根据图的邻接矩阵或者l a p l a c e 矩阵的谱半径( 或者其它的极端特征值) ， 对一些图类( 如树，单圈图等) 进行排序，可以了解该图类的一些极端性质 针对于树。f a l l a t 和k i r k l a n d 刻画了在直径为d 顶点数为n 的树集中含有极 大和极小代数连通度的树针对于单圈图，c h a n g 和t i a n 2 4 刻画了在含完 美匹配的n 阶单圈图中谱半径最大次大的单圈图情形g u o 2 5 1 刻画了在含 k 个悬挂点的n 阶单圈图中谱半径最大的单圈图情形 近期，f a n 把上述工作推广至混合图上在 2 6 】f a n 确定了l a p l a c i a n 谱半 径达到最大的非奇异单圈混合图在【2 7 】中f a n ，t a m 和z h o u 刻画l a p l a c i a n 谱半径达到最大的双圈混合图在本文的最后一章，对所有含相同顶点数的单 圈混合图，按照l a p l a c i a n 谱半径的大小，确定了谱半径达到最大( 简称最大 5 安徽大学硕士学位论文；谱在图能量及图律序中的应用 图) ，谱半径达到次大( 简称次大图) 和谱半径达到第三大( 简称第三大图) 的单 圈图主要结论为； 定理3 2 3 对所有n 个顶点上的单圈混合图，当n 5 ，图3 1 1 中的图 g l m 一3 ，o ；t 1 ) 是唯一的最大图( 在符号同构意义下) 定理3 2 5 对所有n 个顶点上的单圈混合图，当n25 ，舀1 ( n 一3 ，o ；n ) 是 唯一的次大图( 在符号同构意义下) 定理3 2 6 对所有n 个顶点上的单圈混合图，当n 5 ，图3 1 ，1 中的 g 1 m 一4 ，1 ；n ) 是唯一的第三大图( 在符号同构意义下) 6 第二章图的能量与l a p l a c i a n 能量 第二章图的能量与l a p l a c i a n 能量 本章主要讨论图的能量与图的l a p l a c i a n 能量中的若干问题，主要结果 有； 1 给出了若干类单圈图，使得：按某种方式删除此类图中圈上的边，则图的 能量减少； 2 给出了图的l a p l a c i a n 能量的积分表达形式 2 1删边对单圈图能量的影响 本节将详细讨论删边对单圈图能量的影响设g 是n 阶的简单图其邻 接矩阵a ( a ) 的特征多项式为 n c a ( a ；z ) = d e t ( z l _ a ( g ) ) = 啦( g ) z ”一 i = 0 方程“( g ；z ) = 0 的n 个根称为是g 的邻接特征值，分别记为a l ( g ) ，a 2 ( g ) ， 。( g ) 因为邻接矩阵a ( a ) 是实对称的，故a ( g ) 的所有特征值均为实数 图g 的能量定义为 e ( g ) = m 鲱 能量e ( g ) 也可表示成g o u l s o n 积分公式的形式。 即i 札f + 霜o 。1h 胁儿水垆) 2 + ( 争锄“印纠) 2 卜 关于能量e ( g ) 的性质可以参看综述【l o 】 对于图g 的上述特征多项式“( g ；z ) ，令如( g ) = i a i ( g ) i ，江0 ，1 ，n 显 然，b o ( a ) = 1 ，b 2 ( g ) 是g 的边数，g 的女一匹配个数用记号m ( g ，鼬表示 7 安徽大学硕士学位论文：谱在图能量及图排序中的应用 若g 是一个二部图。则当k20 ，咄( g ) = m ( g ，女) 和幻+ 1 ( g ) = 0 若g 是一 个单圈图，则有类似的结果约定：当 0 ，( - i ) a 2 k ( g ) o ； 若f - 2 r + 1 且r 是奇数时，则对所有的0 ，( 一1 ) o a 2 k + l ( g ) 0 ； 若f _ 2 r + 1 且r 是偶数时，则对所有的20 ，( - 1 ) 2 + 1 ( g ) 0 根据引理2 1 1 ，以及上面的化学能量c o u l s o n 积分公式可得， e c g ，= ；z + 。刍n ( 翼c g ，z 巧) 2 + ( 薹。+ 。c g ，z + 1 ) 2 a z 此公式在后面的正面过程中作用举足轻重 二部图的能量公式可写成更简洁的c o u l s o n 积分公式： e c g ，= ；z + 。刍h ，+ 粪吻c g ，z 材 出 从上面的公式我们可知，e ( g ) 是关于吻( g ) 严格单调增加函数 为了获得啦( g ) 在图论意义上的表达形式，综述【1 0 】引入一种s a c h s 图 s c 日s 图指的是它的分支必须是由圈或者是只有两个顶点的完全图恐或者 二者兼而有之所构成的一类图图2 1 1 所示的三个图都是s a c h s 图 g 1g 2 图2 1 1 三个s a c h s 图 对于图g 中的一个s a c h s 图s ，记k a c s ) ，c g ( s ) 和n a ( s ) 分别为图s 的 分支数，圈数和顶点数记& ( g ) 为g 中具有 个顶点的所有s a c h s 图构成 的集合 8 f 【 瓯 v 第二章田的能量与l a p l a e i a n 能量 引理2 1 2 1 1 0 】( s a c n s 定理) 当i l ， 啦( g ) = ( - i ) k o ( 5 ) 2 ( 鳓 s e 矗( g ) 引理2 1 ，a 2 0 1 若g 蛋( n ，! ) 且f o ( m o d4 ) 设是图g 中圈a 上的 任意一条边，则有下面的关系式成立 岛( g ) = 岛( g w ) + 也一2 ( 0 一一u ) + 2 b i t ( g q ) 引理2 1 4 1 1 0 】设u 与口是图g 中两个相邻的顶点，e 是连接顶点“和 的边则图g ，g e 和g t 一口的匹配个数满足下面的等式 m ( g ，七) = m ( g e ，女) + m ( g 一“一口，女1 ) ，2 1 下面讨论单圈图的能量在删边情形下的变化情况 定理2 1 5 设g o ( n ，f ) 且l 0 ( m o d4 ) ，伽是圈q 上任意一条边则 g u 口的能量小于g 的能量，即e ( g ) e ( g w ) 证明：根据能量的c o u l s o n 积分形式， e c g ，= ；1 ， 一+ 。o o 。1 ；h 【( 妻。c g ，。巧) 2 + ( 妻a 巧+ 。c g ，。+ ) 出 和引理2 1 3 ， b i ( g ) = b i ( o t 口) + 如一2 ( 0 一一 ) + 2 6 一f ( g q ) 从而 阮( g ) 玩( g u 口) ，f o r i = 0 ，1 ，2 ，1 由于e ( o ) 是一个关于参数b i 严格单调增加的函数，所以e ( g ) e ( g 一 “口) 但是，至少存在一个i ，满足6 ( g ) 阮( g 一 ) ；否则b i 一2 ( g t 一 ) = 6 i 一；( g 一岛) = o ，这是不可能的故不等式e ( g ) e ( g 一伽) 严格成立 _ 下面对单圈图g 岔( z ) ( fio ( m o d4 ) ) 进行讨论那么，此时定理2 1 5 是否还成立呢? 9 安徽大学硬士学位论文；谱在囝能量及图排序中的应用 定理2 1 6 设g g i n ，z ) 且z i0 ( r o o d4 ) ，g 是由圈劬在其某个顶点t c ，附 加n 一! 1 条悬挂边所获得，如图2 1 ，2 中的图( i i ) 所示设伽是圈q 上的一 条边( “，口 ) 则g 一“口的能量小于图g 的能量，即，e ( v ) e ( g - u v ) t 移 图( i )图( i i ) 证明：注意到g 是一个二部图，且r e ( a ) = 根据能量的c o u l s o n 积分形 e c g ，= ；z + 。刍h ，+ 薹5b v ( g ) = 2 j d z 下面将证明；对于所有的j = 1 ，2 ，矗，b 2 j ( v ) b 2 j ( g 一伽) 我们分情形讨 论 情形l ：j e ( g t 1 根据定理2 1 5 和定理2 1 6 ，对于某些类的单圈图，删去其圈上的某条边， 图的能量都减少了但这个结论并不是对所有的单圈图部成立下面我们从具 体的例子进行说明对于图2 1 3 中的各图，应用数学软件，我们获得如下结 论，所给数值精确到0 0 0 1 e ( g 1 ) 9 1 9 0 0 e ( g t 一1 1 , 1 ) ) 9 4 0 9 2 e ( g 1 一伽2 ) 9 5 1 7 6 e ( g 2 ) 9 ，1 5 2 8 e ( g 2 一“t 1 ) 9 4 0 9 2 ， e ( g 3 ) 9 2 1 1 2 4 = p ( g 5 ( o ，o ；4 ) ) 安徽大学硕士学位论文：谱在雷能量及图排序中的应用 那么当 = 4 时，根据定理3 1 1 ，a 1 ( 1 ，o ；4 ) 和c 5 ( 0 ，0 ；4 ) 或者是其符号同构图 分别是最大图和次大图下面的讨论中我们不妨假设侣5 引理3 2 1 在符号同构意义下，含n 个顶点的最大图是图3 1 1 中的g l ( r ，s ；n ) ( r 8 o ) ；含n 个顶点的次大图是图3 1 1 中的图 证明：根据定理3 1 1 ，在符号同构下，最大图是一个全无向图所以只需 要讨论所有的全无向图设g 是一个含有n