（计算数学专业论文）图的拉普拉斯特征值的能量和研究.pdf

! 童 独创性声明 | | i i ii i ri ii ii iii i i tlu l y 1 7 4 0 215 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名： 瞧弘1 0 年岁勘旧 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 日期：年月日 摘要 摘要 经过近半个多世纪的快速发展，图的谱理论已逐渐成为图论研究的一个重要 研究领域，同时也是一个很活跃的研究方向。起源于1 8 世纪的图论在计算机科学、 信息论、控制论、运筹学以及信息计算科学中均有广泛的应用。它也与图的其它 一些不变量( 如直径，色数，度序列，连通度等) 联系非常紧密。图谱理论所研究 的对象主要包括图的邻接谱，q 一谱，l a p l a c e 谱，c 一谱，s 一谱，其中对邻接谱 和l a p l a c e 谱的研究最为普遍。在许多应用中，往往需要l a p l a c e 谱半径的好的上 下界估计值。 本文主要研究对于简单图的拉普拉斯特征值的能量的上下界估计值，以及图 的能量的上下确界的探讨。具体包括了以下几方面的内容： 介绍了图的能量以及拉普拉斯能量的一些背景知识，然后介绍对于图的能量 的上下界的研究进展。 对一些特定图的拉普拉斯特征值的能量的上下界及大小进行比较，并给出了 新的上下界。 对于不同的图的能量的上下界进行了分析，并研究了矩阵的特征值的模的k 次方之和的大小。 对一些能量大于某些特定值的图进行了比较分析。 关键词：图的能量，图的拉普拉斯特征值，图的谱图的谱半径，上下界，拉普 拉斯能量，二部图 a b s t r a c t a bs t r a c t a f t e rn e a r l yh a l fac e n t u r yo fr a p i dd e v d o p m e n t ，s p e c t r u mt h e o r yo fg r a p hh a s g r a d u a l l yb e c o m e a l li m p o r t a n ta r e ao fr e s e a r c hi nt h eg r a p ht h e o r y ，a l s oi ti sav e r y a c t i v er e s e a r c hd i r e c t i o n w h i c ho r i g i n a t e di nt h e18 t hc e n t u r yt h eg r a p ht h e o r yh a v ea w i d d yr a n g eo fa p p l i c a t i o n si ni n f o r m a t i o n a l ，c y b e r n e t i c s ，o p e r a t i o n a lr e s e a r c ha n dt h e i n f o r m a t i o n so fc o m p u t i n gs c i e n c e i ta l s oc l o s e l yc o n t a c tw i t hs o m ei n v a r i a n t ( s u c ha s d i a m e t e r , c h r o m a t i cn u m b e r , d e g r e es e q u e n c e ，c o n n e c t i v i t y , e t c ) s p e c t r u mt h e o r yo f g r a p hi n c l u d e sa d ja c e n c ys p e c t r u m ，q s p e c t r u m ，l a p l a c es p e c t r u m ，c s p e c t r u m ， s - s p e c t r u m ，w h i c ht h ea d j a c e n ts p e c t r u ma n dl a p l a c es p e c t r u ma r eo f t e nu s e d i nm a n y a p p l i c a t i o n s ，m e yo f t e nr e q u i r eg o o dl a p l a c es p e c t r a lr a d i u s l o w e ra n du p p e rb o u n d s t h i sp a p e rs t u d i e st h ee s t i m a t ev a l u e so ft h eb o u n d so f l a p l a c ee n e r g y , a sw e l la s t h eu p p e ra n dl o w e rb o u n d so fg r a p he n e r g yf o ras i m p l eg r a p h s p e c i f i c a l l yi n c l u d e s t h ef o l l o w i n ga s p e c t s ： d e s c r i b e st h es o m eb a c k g r o u n dk n o w l e d g eo fg r a p he n e r g ya n dt h el a p l a c e e n e r g y , a n dt h e nd e s c r i b e st h el a t e s tp r o g r e s so f t h eu p p e ra n dl o w e rb o u n d sf o rt h e g r a p he n e r g y c o m p a r i s o nt h eu p p e ra n dl o w e rb o u n d sa n di t ss e c t o ro ft h el a p l a c ee n e r g yf o r s o m es p e c i f i cg r a p h s ，a n dt h e nw eg i v e ss o m en e w u p p e ra n dl o w e rb o u n d sf o rt h e s e g r a p h s a n a l y s i st h ee n e r g yo fg r a p h su p p e ra n dl o w e rb o u n d sf o rd i f f e r e n tg r a p h s ，a n d s t u d i e dt h es e c t o ro ft h em o d e lf o rm a t r i xe i g e n v a l u e so ft h ek t hp o w e r a n a l y s i sa n dc o m p a r a t i v es o m eo ft h eg r a p hw h i c he n e r g yi sg r e a t e rt h a ns o m e s p e c i f i cv a l u e s k e y w o r d s ：e n e r g yo fg r a p h ，l a p l a c i a ne i g e n v a l u eo fg r a p h ，g r a p hs p e c t r u m s p e c t r a l r a d i u so fg r a p h s ，u p p e ra n dl o w e rb o u n d s ，l a p l a c ee n e r g y , b i p a r t i t eg r a p h 一 目录 目录 第一章绪论1 1 1 研究背景及意义l 1 2 国内外研究现状2 1 2 1 图的基本定义及基础定理介绍2 1 2 2 图的能量的定义及基本性质4 1 2 3 图的能量及拉普拉斯能量的发展历史和最新进展6 第二章图的能量在k y f a n 定理中的应用8 2 1k y f a n 定理的介绍8 2 2k y f a n 定理的应用8 2 3k y f a n 定理在最大点度数方面的应用1 0 第三章能量大于特定值的图1 2 3 1 基本概念介绍1 2 3 2 图的能量的下界1 2 3 3 无四边形的双正则图的能量1 3 3 4 无相邻四边形的双正则图的能量1 5 3 5 图的拉普拉斯特征值的次方的和1 7 3 6 合成图的能量大小比较1 8 3 7 图的距离矩阵1 8 第四章图的能量及拉普拉斯能量的一些比较2 1 4 1 前置定理2 1 4 2 图的拉普拉斯能量的上确界2 5 4 3 森林与树的拉普拉斯能量的关系2 8 第五章总结与展望3 5 致谢3 6 参考文献3 7 i i i 第一章绪论 1 1 研究背景及意义 第一章绪论 图论的起源可以追溯到大数学家欧拉( l e o n h a r de u l e r ) 。1 7 3 6 年，当欧拉来到 德国的哥尼斯堡( k o n i g s b e r g , 大哲学家康德的故乡，现在是俄罗斯的加里宁格勒) 时，发现当地的居民有一项饭后的消遣活动，就是他们试图将城中的七座桥分别 各走一遍并且最后回到出发点，但是却从来没有人成功的做到过。欧拉通过严密 的分析证明了这件事是不可能的，并且为此写了一篇论文，一般都认为这是图论 的开始。 图论是数学的一个重要的分支。它以图为研究对象，涉及的领域及其广泛。 凡是涉及排列组合优化问题都离不开图论的知识。比如通信编解码、矩阵运算、 任务分配、g p s 路径规划等等。随着科学技术的日新月异，数学学科及其分支学 科在科学研究及社会发展中发挥着越来越重要的作用。自从欧拉开辟了图论这一 崭新的理论以来，越来越多的科学家及学者投入到图论以及其延伸学科的研究中 来，他们中的许多人为这一领域做出了突出的贡献，使得如今图论不仅仅局限于 数学的领域，而是延伸到了更多的自然科学之中，例如图论在量子化学、物理、 计算机科学、通信网络及信息科学之中有着越来越广泛的应用。特别是在化学图 论方面，图论与电子结合更加的紧密。 图论是一门应用十分广泛且内容非常丰富的数学分支，是近年来离散数学和 组合数学领域最为活跃的分支之一。它的应用范围很广，它不但能应用于自然科 学，也能应用于社会科学。它非但广泛应用于电信网络、电力网络、运输能力、 开关理论、编码理论、控制论、反馈理论、随机过程、可靠性理论、化学化合物 的辨认、计算机的程序设计、故障珍断、人工智能、印制电路板的设计、图像识 别、地图着色、情报检索，也应用于语言学、社会结构、经济学、运筹学、兵站 学、遗传学等方面。图论的研究内容及其独特的研究方法，随着现代科学技术的 不断进步，也越来越显示出其独特的作用和魅力。因而，无论从图论的理论价值， 还是从其实际应用的广度和深度来看，图论及其应用的研究都有强大的生命力， 并且正处于蓬勃发展的新时期。 电子科技大学硕士学位论文 谱图理论主要研究的是图的各种矩阵表示( 主要是l a p l a c e 矩阵和邻接矩阵的 代数与组合性质) ，通过建立矩阵的谱性质( 如特征值和特征向量) 与图的结构性质 ( 如图的不变量) 之间的联系，期望用矩阵的谱性质来刻画图的结构性质。其中， 对于图的能量及图的拉普拉斯能量的上下确界的研究最为深刻和成功。在研究图 论的学者之中，i v a ng u t m a n 和b oz h o u 合作在图的l a p l a c e 能量方面写了一系列 的文章，内容主要是关于各种不同的图的能量及拉普拉斯能量的上下界，以及将 图的能量拓展到矩阵的特征值模的k 次方( k = l ，2 ，3 ，1 2 ，1 3 等等) 。他们还 对一些能量大于某些特定值的图进行了研究。g i n d u l a l 则构造了一个距离矩阵， 从中得到了图的距离矩阵的谱半径和能量之间的一系列结论和公式。 1 2 国内外研究现状 1 2 1 图的基本定义及基础定理介绍 我们把图g 等价于一个有序的对( y ，e ) ，可以简记为g = ( 矿，e ) 。在这里，把 集合y 叫做图g 的点集合或顶点集合，集合中的元素称为图g 的顶点，用n = i v l 代 表图g 的顶点个数。集合e 叫做图g 的边集合，集合中的元素称为图g 的边，用 肋= j e l 代表图g 的边的条数。只有一个顶点而边集合为空集合的图称为平凡图， 而其他所有的图都叫做非平凡图。连接两个相同顶点的边的条数称为该边的重数。 重数大于1 的边叫做重边。其中两个端点为同一个点的边叫做环。如果一个图中 既没有重边也没有环，那么这个图叫做简单图，其他所有图都叫做复合图。这篇 文章里，我们只讨论简单图。 如果一个简单图的任意两个顶点之间都有边相连，那么这个图叫做完全图， 我们把n 个顶点的完全图记做k 。如果一个简单图的顶点集可以分为两个，且这 两个集合中的顶点均不相连，那么这个简单图就称为偶图，也叫做二部图。所谓 的完全偶图就是指一个偶图的两个集合中的任意一对顶点均有边相连，我们用 k 。来表示完全偶图，其中m 和疗分别代表两个点集合中的元素个数。 对于一个简单图g = ( v ，e ) ，我们令集合互= 圳b ，甜，1 ，矿 ，那么我们把图 2 第一章绪论 h = 缈，巨e ) 称为图g 的补图，记做h = g 。很明显，两个集合互为补集，且两 个集合的并集为完全图疋。假设有两个简单图g 1 = ( 巧，互) 和g 2 = ( k ，岛) ，两个图 的顶点之间存在一个一一对应的关系，即m 付屹，u l 付u 2 ，其中v l , u 。巧， v 2 ，“2 砭，且当且仅当“l m 巨时，有“：v 2 易。那么我们称图g l 和g 2 同构，记 做g l 兰g 2 。 我们一般用a 0 , ) 来表示图g 中与顶点y 相关联的边的条数，称作顶点v 的点度 数。且我们用集合8 ( g ) 和a ( o ) 来分别表示图g 的最小点度数和最大点度数。我们 有时候也把顶点度数为奇数的点称为奇点，顶点度数为偶数的点称为偶点。如果 一个简单图g 的所有顶点的度数都等于一个正整数k ，那么我们把这个图称作k 正 则图。 如果图g 的两个顶点“和v 2 _ 间存在( “，1 ，) 路，那么我们把甜和1 ，称为连通的。 更进一步的，如果图g 的任意两个顶点u 和1 ，都存在( “，1 ，) 路，那么我们称图g 为 连通图，否则称为非连通图。 图g 的一条通路是指一组图g 的顶点序列，相邻的两点之间均有边相连。如 果连接这一组顶点序列中的边都互不相同，那么这条通路称作迹。又如果连顶点 也互不相同，那么这条迹又称为路。 如果一条迹的起始顶点和终点相同，那么这条迹称为闭迹。又如果这条闭迹 的起始顶点和内部的所有顶点都互不相同，那么这条闭迹又称作圈，也叫回路。 回路中边的条数称为圈的长度，用k 来表示。按照k 是奇数或偶数，称k 圈是奇圈 或偶圈。3 圈叫做三角形，4 圈叫做四边形。图g 中连接顶点u 和1 ，的最短通路的 长度，称为u 和y 的距离，记做a ( u ，v ) ， i i im a x d ( u ，1 ，) 我们定义它为图g 的直径。 与顶点相连的边数称为该顶点的度数，以该顶点为始边的边数称为出度。以 该顶点为终边的边数称为入度。其中度数为零的点称为孤立点。度数为1 的点称 为悬挂点。 可达：在图g 中如果存在一条1 ，到d 的通路，则称从1 ，到d 是可达的。 连通：在无向图中如果任意两点是可达的，否则是不连通的。 3 电子科技大学硕士学位论文 强连通：在有向图中如果任意两点是相互可达的。 单向连通：在有向图中如果存在任意两点的通路。 弱连通：在有向图中如果其底图是连通的。 权：在图的点或边上表明某种信息的数。 赋权图：含有权的图。 1 2 2 图的能量的定义及基本性质 图的能量研究的起源可以向上追溯到1 9 3 1 年。化学家h u c k e l 在对于有机分子 的能量级进行表示的工作中，对非饱和碳氢化合物作了一种近似的处理，获得了 其对应的分子的图的模型，并用该图对应的矩阵的特征值来表示特定的电子的能 量级。从此以后，他的工作被众多的化学家和数学家们继承，并进行了广泛的推 广和深入的研究，获得了一些非常具有意义的结论。本小节将对图的能量的定义 及一些基本的性质进行简单的介绍和分析。 假设g 是一个具有押个顶点和m 条边的简单图，那么我们不妨称g 是一个 ( ，z ，m ) 图。我们一般用盔来表示图g 的第i 个顶点的度数，用来表示图g 的第i 条 边，i = 1 , 2 ，栉。 图g 的谱，即是由图g 的邻接矩阵的特征值 ，如，丸所构成的集合。而图g 的拉普拉斯谱则是相应的由图g 的拉普拉斯矩阵的特征值肛，2 ，z 。所构成的集 合。那么我们可以得到如下的众所周知的性质及定义： 性质1 , 2 2 1 【1 l = l 。丑= o ；：= 2 m ，( i - i ) 二。肛= 2 m ；：。彳= 2 m + ：。砰( 1 - 2 ) 更进一步的来说，如果图g 由p 个部分组成( p 1 ) ；那么我们不妨令图g 的拉普 拉斯矩阵的特征值按照降序来排列，即“鸬以，那么我们又可以得到如 下的性质： 4 第一章绪论 性质1 2 2 2b i 以一j = 0 ， i = 0 , 1 ，p 一1 以一p 0 定义1 2 2 1 1 2 1一。 有，z 个顶点的一个标定图g 的邻接矩阵彳= ( ) 是- - + n n 的矩阵。其中，如 果_ 邻接吩，则= l ，否则= o 。于是在有阼个点的简单标定图与对角元素为 零的咒阶对称二元矩阵( 其中元素取值为0 和1 ) 之间是一一对应的关系。 定义1 2 2 21 1 l 我们把图g 的能量定义为邻接矩阵4 = ( 嘞) = 彳( g ) 的特征值的绝对值的和： e ( g ) = ：。l 丑i ，i = 1 ，2 ，以 ( 1 3 ) 这个能量的式子具有很好的化学方面的应用，在此我就不再赘述了。根据这个能 量的定义，我们可以很容易的推出以下的几个结论： 性质1 2 2 3 【1 1 口 e ( g ) 0 ，当且仅当m = 0 的时候等号才成立。 【b 】如果图g 只包含两个相互不连接的部分g 1 和g 2 ，那么我们可以得到这样 的一个式子：e ( g ) = e ( g 1 ) + e ( g 2 ) c 】如果图g 除了一个g l 的子图以外，其他的部分都是孤立点的话，那么我 们可以得到：e ( g ) = e ( g 1 ) 定义1 2 2 3 1 3 1 我们定义盔分别为图g 中的点v f 的点度数，i = 1 ，2 ，刀。定义d = d ( g ) 为一 电子科技大学硕士学位论文 个对角元素分别等于4 的对角矩阵，那么图g 的拉普拉斯矩阵可以如下的表示： 三= l ( g ) = d ( g ) 一彳( g )( 1 - 4 ) 那么我们就可以同样的定义图g 的拉普拉斯能量为 l e = l e ( g ) = 二。一2 m n i ( i - 5 ) 如果我们定义乃= 鸬- 2 m n ，i = 1 ，2 ，, 。那么( 1 5 ) 式可以以如下的简单方式来 表示： l e = l e ( g ) = ：。i t , l ( 1 - 6 ) 在这里我们可以很容易的知道，乃，i = 1 ，2 ，挖，是矩阵l ( c ) - 2 m x n 的特征值。 1 2 3 图的能量及拉普拉斯能量的发展历史和最新进展 由于图的能量在数学理论研究、化学及其他各个领域具有重大的科学意义和 应用价值，因此吸引了众多的数学家和化学家来对图的能量进行研究。从最早的 单纯的通过证明和推导来求出图的能量和拉普拉斯能量的上下确界开始，慢慢的 到求解图的邻接矩阵和拉普拉斯矩阵的特征值的模的k 次方之和( k = 2 ，3 ，1 2 , 1 3 ) 等等。后来，很多学者又对某些能量大于特定值的图进行了分析和研究，得到了 很多有意义的成果，例如当e ( g ) 刀时，在化学图论中的应用。而g 1 n d u l a l 则别 出心裁的构造了一个他称之为距离矩阵的新矩阵，从而得到了一系列关于这个距 离矩阵的谱半径与图的能量之间的关系的结论和式子。g u t m a n 和z h o ub o 则在图 的能量和拉普拉斯能量的文章中合作了很多次，并通过对能量极大和极小的单圈 图的刻画，进而对双圈图和二部图的能量也进行了类似的讨论。 下面介绍一些关于图的能量和拉普拉斯能量的定理、推论及性质： 1 2 3 1 图的能量的上下界 定理1 2 3 11 4 1e ( g ) & y 磊m n 不等式恒成立，等号当且仅当图g 全是孤立点或点 度数全为1 时成立。 6 第一章绪论 定理1 2 3 2 1 5 1 e ( g ) 2 聊以+ 板i 面瓦磊i 五万两不等式恒成立，等号当且仅当 图g 是点度数为0 , i ，z 一1 的正则图或者g 是一个非完全连通的强正则图，且有两个 非零特征值的绝对值都为撕荔i 西磊丽而。 定理1 2 3 3 i s l 2 鬲e ( g ) 2 m 不等式恒成立，左边等号当且仅当图g 没有孤立 点且g 是一个完全二部图时成立。右边等号当且仅当图g 没有孤立点且g 是点度 数全为1 的正则图。 1 2 3 2 图的拉普拉斯能量的上下界 我们令m = 朋+ ：。 d t - 2 m 挖1 2 2 ，则可得到如下定理： 定理1 2 3 41 6 1 皿( g ) 压而 定理1 2 3 5 1 6 1 妇( g ) 2 聊栉+ 4 ( n - 1 ) 2 m - ( 2 m n ) z 定理1 , 2 3 6 1 7 1 2 万皿( g ) 2 m 如果g 不含有孤立点，那么左边等号成立的充要条件为g 是一个完全的二部 图，右边等号成立的充要条件为g 是点度数全为1 的正则图。 7 电子科技大学硕士学位论文 第二章图的能量在k y f a n 定理中的应用 2 1k y f a n 定理的介绍 假设m 是一个刀阶实对称矩阵。令s ；( m ) ，i = 1 , 2 ，l ，是矩阵m 的正奇异 值，x i ( m ) ，i = 1 ，2 ，l ，是矩阵m 的特征值。显然，对任意的江l ，2 ，刀，都有 岛似) = l _ ( m ) i 。 图g 的能量等于其邻接矩阵a ( g ) 的正奇异值之和这个结论，对于下面这个定 理来说是非常重要的： 定理2 2 1 1 3 i 假设石，】，z 都是甩阶方阵，并且x + y = z ，那么 h ( x ) + ：，岛( y ) ( z ) 等号成立当且仅当存在一个正交矩阵p ，同时满足以和p 】，都是半正定矩阵。 根据定理2 2 1 ，我们立刻可以得到，若图q ，g y ，g z 的邻接矩阵满足等式 4 ( 瞰) + 彳( g y ) = 彳( g z ) ，则 五( 嚷) + e ( g y ) e ( g z ) 根据这个式子，我们可以得到很多的推论。 2 2k y f a n 定理的应用 通过式子( 2 - 1 ) ，我们可以得到很多简单实用的结论。 推论2 2 1 1 3 1 假设g 是一个刀阶简单图，且否是它的补图，那么 ( 2 1 ) 第二章图的能量在k y f a n 定理中的应用 e ( g ) + e ( g ) 2 ( n 一1 ) 等号当且仅当g 是n 阶正则图或是n 阶正则图的补图时才成立。 如果等号成立，那么由于e ( g ) = 二i 以( g ) l ，e ( 否) = ：。l 乃( 否) l ，我们可以很 容易的得到：五( g ) o ，五( g ) o 。那么换句话来说就是，等号成立的充要条件 是g 和g 都至多只有1 个正特征值。由此我们可以得到以下的三种情况： ( i ) g 没有正的特征值：g 全是孤立点 ( i i ) g 没有正的特征值：g 是，z 阶完全图 ( i i i ) g 和g 都含有1 个正特征值 推论2 2 2 1 3 1 假设b 是一个二部图，且包含口+ 6 个定点，否是二部图的补图， 那么： e ( b ) + e ( b ) 2 4 a b 等号当且仅当召是完全二部图或是完全二部图的补图时才成立。 这个不等式的i i f _ n 需要靠事实彳( b ) + 彳( b ) = 彳( k 6 ) 和e ( 。6 ) = 2 口6 。那么 现在这个不等式就相当于推论2 2 1 了。 在比较早的图论相关的论文中，有很多的论文都讨论过某个图在增加一个悬 挂点或去掉某条边、某个点后，图的谱具有的新性质。在这里，我们同样也可以 应用k y f a n 定理来对一个图g 和去掉一条边后的新图g e 的能量来做一个大小 的比较。 推论2 2 3 1 3 1 假设g e 是图g 去掉一条边p 后的子图，那么： e ( g ) e ( g - e ) + 2 ( 2 - 2 ) 这个推论的证明在文献【4 中已经得到了证明。在文献 4 1 d ? ，还证明了这 个不等式的等号当且仅当e 是g 的一条孤立边时才成立。 我们将( 2 - 2 ) 式的结论推广到所有的( 刀，m ) 图中，那么我们可以得n - 9 电子科技大学硕士学位论文 e ( g ) 2 m 等号当且仅当g 包含m 条孤立边和以一2 m 个孤立点是才成立。这是和定理1 2 3 的 右边部分相同的结论。等号的成立条件也是等价的。 2 3k y f a n 定理在最大点度数方面的应用 首先我们定义e 和只分别为，z 阶完全图和包含，1 个点的圈。疋，。是一个完全 二部图，两个部分分别包含a 和b 个顶点。我们用来表示图中的最大点度数。 引理2 3 1 1 5 1 假设g 是一个包含n 个顶点的非完全图。g + 是在图g 中增加一条 边，那么： 6 ( g ) - 6 ( g ) 2 ( g ) 鸬( g ) 以一l ( g ) 以一1 ( g ) 以( g ) = 心( g ) = o 引理2 3 2 i 5 i 假设g 是至少有一条边的简单图，最大点度数为，那么有： “1 + 等号当且仅当g 为连通图且a = n l 时才成立。 定理2 3 1 1 3 1e ( g ) - 2 m 一2 ( 一压) 等号当且仅当g 是一个星图s a + l ，有m 一条孤立边，万一2 m + a - 1 个孤立点时才 成立。 定理2 3 2 1 3 1g 是一个连通的( 刀，朋) 图，丁是其生成树，那么 e ( g ) 2 ( m - n + 1 ) + e ( 丁) 同构时才成立。 1 0 等号当且仅当g 和乃+ 。同构时才成立。 以下是一些已知道的特定图的能量： e ( e ) = 4 c o s z n s i n z nn 三o ( m o d 4 ) e ( e ) = 4 s i n z n e ( e ) = 2 s i n z l 2 n e ( 只) = 2 s i n z ( 2 n + 2 ) - 2 刀三2 ( m o d 4 ) n 暑l ( m o d 4 ) n 三o ( m o d 2 ) e ( ) = 2 c o s z ( 2 n + 2 ) s i n z ( 2 n + 2 ) - 2n 兰l ( m o d 2 ) 电子科技大学硕士学位论文 第三章能量大于特定值的图 3 1 基本概念介绍 痧? 前面多次提到，图的能量在很多的领域都有广泛的应用，特别是在化学方面。 图的能量的定义就是来源于化学。在量子化学方面，对能量大于特定值的电子图 有非常有意义的性质。因此，这一节我们针对e ( g ) 咒的图来进行讨论。 下面介绍一些基本的事实： 性质3 1 1 1 6 1 如果g 是一个非奇异图，即g 没有零特征值，那么 e ( g ) 以 性质3 1 2 i 8 1 如果g 是一个包含，1 个点和m 条边的简单图，且m 聆2 4 ，那么 e ( g ) ，z 成立。 性质3 1 3 1 8 i 如果g 是任何一个非零点度数的正则图，那么e ( g ) 刀成立。 3 2 图的能量的下界 下面我们介绍一些图的能量的下界： 定义3 2 1 1 9 i 设口，b 都是正整数，且1 a _ d 4 d ( 2 a + 2 b - 1 ) d - 2 a b ( 3 2 ) 这里的d = 2 m n ，是图g 的平均点度数。显然a d b 。 从上式可以看出，为了使e ( g ) ，z 成立，我们需要考察函数 f(x)=x4。x。(。2。a。+。2。b。-。1。)。x。-。2。ab。 当z q ，6 ) 时，找出厂( x ) 1 成立的区间。 直接计算我们可以得到当a 0 ，故 a ( x ) o 对比( 口，6 ) 都成立。 剐f y - 令f o ( x ) = ( 2 a + 2 b 一1 ) x 一3 a b ，然后我们讨论x 口( 功圳2 五( 功的值。因为 x a ( x ) q 坨是恒大于零的，函数厂( 力当五( 曲 0 的时候在区间( 口，6 ) 上对比( a ，功 是增函数。 因为f o ( b ) = 6 ( 2 6 一口一1 ) 很显然是正值，那么我们只需要满足f o ( a ) 0 即可。 显然 ( 口) = a ( 2 a - b - 1 ) 0 i 躲l a f 9 2 a b + l 。所以，我们可以这样说，函数厂( 功 在区间( 口，b ) l - g e f v x ( 口，b ) 是增函数的充要条件是2 a b + l 。那么从式子( 3 2 ) 可以 看出，e ( g ) n f ( a ) ，即 e ( g ) n a 厄a - 1 不等号成立的条件是a l 时，我们有： 性质3 3 1 i 1 0 1 令g 是一个n 阶的没有四边形的点度数为a ，b 的双正则图，那么 当2 a a41。(。2。b。-。1。) 当d 乏雨。l 时，也同样可以满足e ( g ) 力。由此，我们可以得到如下性质： 定理3 3 2 令g 是一个，l 阶的没有四边形的点度数为a ，b 的双正则图，那么当 1 4 第三章能量大于特定值的图 正整数a 和b 满足下列条件之一时，都可以得到： e ( g ) ，l ( 1 ) 2 b l 口2 6 2 证明：因为d 三! 西l d 2 2 b 一1 ，又因为4 d 6 ，故当2 b 一1 a 2 6 2 时， 该定理成立。 ( 2 ) a g ( a ) ，即： 1 5 电子科技大学硕士学位论文 不等式成立的充要条件是a b 2 a 一1 + 3 a 。这样，我们可以得到以下的定理和 性质： 定理3 4 1 假设g 是一个n 阶的点度数为a 和b 且图中所有四边形都不相邻的 双正则图，那么当a 2 时，有： 口云2 口2 一口+ 2 1 即是有e ( g ) 刀成立。因此，我们又得到如下性质： 定理3 4 2 假设g 是一个n 阶的点度数为口和b 且图中所有四边形都不相邻的双正 则图，那么当2 a d d ( 2 b - 1 ) d = d ，所以当 我们满足j 2 6 1 1 时，就有e ( g ) ，z 成立。所以我们有如下性质： 定理3 4 3 假设g 是一个n 阶的点度数为a 和b 且图中所有四边形都不相邻的双正 则图，那么当正整数a 和b 满足下列条件之一时，都可以得到： e ( g ) 刀 ( 1 ) 2 b 一1 a 2 b 2 证明：因为d 2 6 1 1 d 2 2 b l ，又因为口 d b ，故当2 b 一1 口2 b 2 时， 该定理成立。 ( 2 ) a 二 l i l l 第四章图的能量及拉普拉斯能量的一些比较 结合上面的两个结论，我们可以得到如下定理： 定理4 1 4 1 1 s i 假设图g 是一个二部图，顶点数为以，边数为所，对应的点度数分别 为d l ，吐，d 。，以及点平均度数为d = 2 m n ，那么我们有： m a x 扣，孙一孑忙皿c g 脚c g ，+ 批i = i 一- l 4 2 图的拉普拉斯能量的上确界 现在我们给出一些图的拉普拉斯能量的上下界。 首先，我们假设图g 是一个简单图，它有一个连通部分g 1 和他个孤立顶点。 而g l 包括p 个连通部分和m 个顶点。 定理4 2 1 ：假设图g 的拉普拉斯特征值分别为“，2 ，a 。，那么我们有： 姐( g ) 4 m 证明：根据假设条件，图g 是一个简单图，它有一个连通部分g l 和n 2 个孤立顶点。 而g l 包括尸个连通部分和个顶点。这样，我们可以得到图g 的拉普拉斯矩阵如 下： 三= 9 2 g p 0 o o 其中g ，i = 1 ，2 ，p 分别是图g l 的p 个连通部分的拉普拉斯矩阵。由拉普拉斯矩 电子科技大学硕士学位论文 阵的基本性质可知，拉普拉斯矩阵& ，i = 1 ，2 ，p 分别各有1 个零特征值，所以 整个大的拉普拉斯矩阵三共有p + 以：个零特征值，而其他特征值则全为正数。于是， 根据拉普拉斯矩阵的定义加( g ) = ：。k 一2 m n l ，我们可以得到： 三e ( g ) = i m - 一i p i 鸬一2 m l ( n i + 晚) l + 2 m ( p + ”2 ) ( 一+ ，1 2 ) 又因为肛 o ，i = 1 ，2 ，m - p ，2 m ( n i + ，z 2 ) 0 ，所以我们有： e ( g ) ：p f ( g ) + 2 m ( 强- p ) ( n , + 以2 ) + 2 m ( p + ) ( ，z l + 也) = 2 m + 2 m = 4 m 等号当目仅当m ：0 的时候成立。 定理4 2 2 ：假设图g 的拉普拉斯特征值分别为肚，：，以，那么我们有： 4 m ( p + ，吃) “啊+ 嘞) l e ( g ) 证明：根据假设条件，图g 是一个简单图，它有一个连通部分g l 和，z ：个孤立顶点。 而g i 包括尸个连通部分和啊个顶点。这样，我们可以得到图g 的拉普拉斯矩阵如 下： l = 岛 9 2 o o o 其中g l ，i = i ，2 ，p 分别是图g l 的p 个连通部分的拉普拉斯矩阵。由拉普拉斯矩 阵的基本性质可知，拉普拉斯矩阵白，f = 1 , 2 ，p 分别各有1 个零特征值，所以 整个大的拉普拉斯矩阵三共有p + 嘞个零特征值，而其他特征值则全为正数。于是， 2 6 第四章图的能量及拉普拉斯能量的一些比较 根据拉普拉斯矩阵的定义比( g ) = ：，- 2 m n l ，我们可以得到： 皿( g ) = ：户 l - 2 m ( n a + ，z 2 ) | + 2 ，z ( p + 他) ( + n o 又因为, u l 0 ，i = 1 , 2 ，确- p ，2 m ( n a + 咒2 ) 0 ，所以我们有： = ，一一2 m ( n a p ) ( 强+ n 2 ) + 2 m ( p + n 2 ) ( t h + ) 皿( g ) 所以4 m ( p + t h ) ( n _ l + ，z 2 ) l e ( c ) 。等号当且仅当m = 0 的时候成立。 在前面的章节中，我们证明过图的能量的一个上界e ( g ) 2 m 。在这里，根据 上面的定理4 2 2 ，我们可以看出，当满足条件( p + n 2 ) ( n a + 栉2 ) 1 2 时，我们有 e ( g ) 2 m 8 + 1 4 ，故 l e ( g ) l e ( c , ) + l e ( c 2 ) 。 我们又设，z l = 7 ，刀2 = 1 2 ，那么图g l 和g 2 的拉普拉斯矩阵如下： 厶= t j 1，上 一 一 一，i，i，l 一 一 一l，i 一 一 一i_l 一 一 一 i，l 一 一 一 o o 7 o 7