（应用数学专业论文）图论在化学能量和网络方面的应用.pdf

摘要 摘要 对图能量的研究是图论中一个很活跃的研究方向。设g 是有限、简 单、无向图，n 个点，m 条边。4 ( g ) = ( ) 是图g 的邻接矩阵， ，也，丸 是么( g ) 的n 个特征值，也称为图g 的特征值，则称e ( g ) = 引乃i 为图g 的 能量。在化学领域中，共轭分子生成产生的热能几乎等于该分子的7 9 电子总能量，而分子的万一电子总能量的计算又可归咎于e ( g ) = i = l 阮f 的 计算。本文根据几种图能量的一些主要结果，讨论了单圈图的能量。单 圈图是图论中比较特殊的一类的图，若从其圈上去掉一条边则其就变成 了树，它的能量计算有比其它图较为简便的算法。本文通过对单圈图的 特点的研究，找到了一对同谱的等能量图。 在图论中，另一活跃的研究方向是网络中的路由算法。在计算机的 网络拓扑模型图中，由于超立方体图q 具有的良好的一拓扑性质，所以它 能够成为计算机超大规模并行计算互联网的结构模型。在超立方体中， 在研究它的容错路由方面，安全向量起着很重要的角色，在吴杰的文章 1 】中，每一个节点的安全向量都要经过船一1 轮的计算，计算比较麻烦。 本文在此基础上，改进了安全向量的定义，并通过节点的安全矩阵来确 定节点的安全向量。这种方法，计算方面不仅简单些，而且，也可以判 断与节点距离为k 的所有节点间是否存在最优通路。 本文第一章是绪论部分。第二章给出了能量的概念，并给了几种特 殊类图的能量计算以及性质。通过计算比较，给出了部分图能量的计算 方法，并给出一些等能量的几对图。并着重讨论了单圈图的能量。第三 章分析了超立方体的结构特点。根据安全向量的定义，改进了超立方体 中的安全向量，并给出了通过节点的安全矩阵来求节点安全向量的方法。 第四章进行总结。 关键词：图；能量；单圈图；超立方体图；安全向量；容错路径； 广东工业大学理学硕一# 位论文 a bs trac t t h er e s e a r c ho ng r a p he n e r g yi sav e r ya c t i v er e s e a r c hd i r e c t i o ni nt h e g r a p ht h e o r y i fw es u p p o s e dt h a tg i sal i m i t e d ，s i m p l e ，a n du n d i r e c t e d g r a p h ，t h a ti th a snn o d e sa n dme d g e s ，t h a t 彳( g ) 2 ( ) 脚i st h ea d ja c e n t m a t r i xo fg a n d ，如，九a r en a m e dnc h a r a c t e r i s t i cv a l u e so f a ( g ) ，n a m e l y ， t h ec h a r a c t e r i s t i cv a l u e so fg r a p hg ，e ( g ) = 主? i 丑ii sn a m e dt h ee n e r g yo f g r a p hg i nc h e m i s t r yd o m a i n t h eh e a te n e r g yp r o d e u c e db yt h eg e n e r a t i o n o fc o n j u g a t e dm o l e c u l ei sn e a r l ye q u a lt o 万一t h ee l e c t r o n i ct o t a le n e r g yo f t h em o l e c u l e ，b u tt h ec o m p u t a t i o no f 万一t h ee l e c t r o n i ct o t a le n e r g yo ft h e m o l e c u l em a yp u tt h eb l a m eo nc o m p u t a t i o no fe ( g ) = 引 a c c o r d i n g t ot h em a i nr e s u l t so fs e v e r a lk i n d so fg r a p he n e r g y ，t h ea r i t i c l ed i s c u s s e d t h ee n e r g yo fu n i c y c l i c u n i c y c l i cg r a p hi saq u i t es p e c i a lk i n do fg r a p hi n g r a p ht h e o r y i fas i d ei sr e m o v e df r o mi t sc i r c l e ，i tw i l lt u r nt ob eat r e e i t s e n e r g yc o m p u t a t i o ni sm u c hs i m p l e rt h a na n yo t h e rg r a p ha l g o r i t h m ap a i r o fc o s p e c t r a le q u i e n e r g e t i cg r a p h sh a v e b e e nf o u n di n t h i sd i s s e r t a t i o n t h r o u g hs t u d y i n gt h ec h a r a c t e r i s t i co fu n i c y c l i cg r a p h i ng r a p ht h e o r y ，a n o t h e ra c t i v er e s e a r c hd i r e c t i o ni si nt h en e t w o r k r o u t i n ga l g o r i t h m i nt h en e t w o r k st o p o l o g i c a lm o d e l ，a st h eh y p e rc u b eq h a sg o o dt o p o l o g i c a lp r o p e r t y ，i tc a nb e c o m et h ec o m p u t e ru l t r am a s s i v e l y p a r a l l e lc o m p u t e ri n t e r n e t ss t r u c t u r a lm o d e l i nh y p e r c u b e i ns t u d y i n gi t s f a u l t - t o l e r a n tr o u t i n ga s p e c t ，t h es a f e t yv e c t o ri sp l a y i n gav e r yi m p o r t a n t r o l e i nw uj i e s 【1 1 a r t i c l e e v e r yn o d e ss a f e t yv e c t o rm u s tu n d e r g oan - 1 t u r n sc o m p u t a t i o n ，t h ec o m p u t a t i o ni sq u i t et r o u b l es o m e b a s e do nt h i s ，t h e a r t i c l ei m p r o v et h es a f e t yv e c t o rd e f i n i t i o n ，a n dd e t e r m i n et h en o d e ss a f e t y v e t o rt h r o u g hi t ss a f e t ym a t r i x t h em e t h o d sa d v a n t a g ei sn o to n l yh a v i n ga s i m p l ec o m p u t a t i o n ，b u tj u d g i n gw h e t h e rt h e r ei st h em o s ts u p e r i o rp a t h b e t w e e nt h en o d ea n da n yo t h e rn o d et ow h i c ht h ed i s t a n c ef r o mt h en o d ei s i i 薹【 a b s t r a c t t h i sf i r s tc h a p t e ri st h ei n t r o d u c t i o np a r t t h es e c o n dc h a p t e rc o v e r st h e e n e r g yc o n c e p ta sw e l la st h ec o m p u t a t i o n sa n dn a t u r eo fs e v e r a lk i n d so f s p e c i a lg r a p he n e r g y t h r o u g hc o m p u t a t i o nc o m p a r i s o n ，i ti n v o v l e st h ec o r n p u t a t i o nm e t h o do fp a r t i a lg r a p he n e r g ya n ds e v e r a lp a i r so fe q u i e n e r g e t i c g r a p h ，a n de m p h a t i c a l l yd i s c u s s e dt h eu n i c y c l i cg r a p he n e r g y t h et h i r dc h a - p t e rh a sa n a l y z e dt h eh y p e r c u b es t r u c t u r ef e a t u r e 。a c c o r d i n gt ot h es a f e t y v e c t o r sd e f i n i t i o n ，t h es a f e t yv e c t o ri si m p r o v e d ，a n dt h em o t h e do fc o m p - u t i n gt h en o d e ss a f e t yv e c t o ri sd r a w nt h r o u g hi t ss a f e t ym a t r i x t h ef o u r t h c h a p t e ri st h es u m m a r y k e yw o r d s ：g r a p h ；e n e r g y ；u n i c y c l i cg r a p h ；s u p e r c u b eg r a p h ；s a f e t y v e c t o r ；f a u l t r o u t i n gp a t h i i i 广东t 业大学理学硕十学位论文 独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是 我个人在导师的指导下进行的研究工作以及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，不包含本人或其他用途使用过的成果。与我一同 工作的同志对本研究所做的任何贡献均已经在论文中作了明确的说明， 并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取 得的，论文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此 声明。 3 2 指导教师签字： 论文作者签字： 年月日 第一章绪论 第一章绪论弟一早珀下匕 图论是组合数学的一个重要组成部分，近几年里，它已经发展成数 学的很多重要分支，因为图论在其它重要学科领域诸如计算机，运筹学， 系统工程以及物理学，电子学，生物学等方面的广泛应用，现在越来越 受到科学界尤其是数学界的关注与重视，由于组合数学，代数学，拓扑 学以及概率方法等的结合，现代图论除了传统的研究领域外己经发展成 为包括代数图论，拓扑图论，随机图论等分支在内的多个领域，促进了 图论的发展同时，图论的迅速发展也带动了其它学科的飞跃发展和一些 困难问题的解决。例如图论的发展为计算机网络的优化和信息传递的可 行性提供了良好的发展空间。 图论的应用领域很广，其中比较热门的两大领域有： 一、在化学领域内对图能量的研究。h u c k e l 分子轨道( h m o ) 总的万 电子能量e 是个众所周知的拓扑指标，在理论化学中，具有十分重要的 作用，一个共轭分子的h m o 总的万电子能量是共轭分子的化学结构和热力 学稳定性之间的一个桥梁，由文献【2 】可知它可以解释分子的结构和性质 之间的关系。h m o 总的万电子能量也与共轭的碳氢化合物形成时所释放的 能量紧密相关。和一些复杂的方法相比较，h m o 总的万电子能量对于共轭 化合物的能量估计是相当好的。图g 的能量e ( g ) 是由h m o 总的万电子能 量推广到任意图的能量。4 ( g ) 是图g 的邻接矩阵，彳( g ) 的特征值称为图 g 的特征值。e ( g ) 定义为图g 的特征多项式所有特征根的绝对值之和。 图g 的能量e ( g ) 自引入以来，由文献【3 ，4 】可知对它的研究一直很热门， 早在19 4 0 年，c o u l s o n 给出了图的能量和图的多项式之间的一个直接的联 系，郎c o u l s o n 积分公式 3 1 。图g 的顶点个数n 和边数m 是决定e ( g ) 的主 要因素。对这一方面的研究可追溯到19 5 0 年h a l l 所做的工作【钉。对于图能 量的界，在l9 7 1 年，m c c l e l l a n d 首先得到e ( g ) 的上下界 e l 。许多工作者 把兴趣也转移到对图能量的界的研究，对于这一方面已有很多研究成果 【4 7 i 1 】。 研究具有极值能量图是化学图论中一个重要课题，由文献 12 ，13 】 广东工业大学理学硕士学位论文 可知极值能量图在化学上具有十分重要的地位。关于极值能量图也有很 多结果1 1 4 ；g u t m a n 和y a o p i n gh o u 证明了在偶单圈图中群的能量最大】。 f u j iz h a n g 和h u a i e nl i = i e 明了在具有完美匹配的胛阶树中，e 的能量最小 u 6 ，e 是由星图k 。一，的每个顶点加一条悬挂边而得到的树，这是g u t m a n 在文献【1o 】中提出的一个猜想。y a o p i n gh o u 证明了在至少有一个奇圈的 连通双圈图中，霹4 的能量最小u 7 ，其中霹4 是7 5 个悬挂顶点到完全偶 图k ，的一个度为3 的顶点。y a o p i n gh o u 证明了在单圈图中，霞的能量 最小】，其中是胛阶星图加一条边。张建斌，周波证明了在聆个顶点， 刀+ 1 条边的恰有两个圈的连通二部图的集合g ( n ) 中，z ( n ；4 ，4 ) 是g ( ，2 ) 中具 有能量最小的图【1 9 】，其中z ( ，z ；4 ，4 ) 是两个长为4 的圈恰含有一个公共点， 其余刀一7 个点都是悬挂点且均与这个公共点相邻。f e n gl i ，b oz h o u 证明 了在( 4 , 4 ) 划分的二部单圈图中，b ( 4 ，4 ) 的能量最小【z o 】，其中b ( 4 ，4 ) 是 在四边形的相邻的两个点上分别挂2 个悬挂点。另外f u j iz h a n g 等还证明 了六角链的最小和最大能量图 2 1 2 2 。 二、在计算机领域中对网络路由算法的研究。网络的拓扑结构是设 计和制造集群计算机或超大规模并行计算机系统的第一步，也是实现各 种协议的基础，它对网络的性能、系统可靠性和费用都有重大影响。若 把互连网络中的处理器抽象成一个点，把处理器之间的信道抽象成两点 之间的连线，那么该网络的拓扑结构就被抽象成一个图，研究网络拓扑 结构问题就归结为研究图的结构问题，网络的容错性研究可以转化成对 图的参数研究。超立方体q 是典型的网络拓扑结构，由于它具有高度的 正规性、对称性、可靠性、强容错性、直径短、可嵌入性和网络通信能 力的可扩展性等优点，使其深受实践者的喜爱。随着多处理机系统规模 的增大，系统出现链路或节点故障的概率也随之增大。在超立方体结构 的容错路由设计方面，人们做了大量的工作，文献 2 3 】在文献 2 4 的基础 上改用矩阵来表示各邻接点的每条链路是否存在链路故障，提出了最优 通路矩阵( o p t i m a lp a t hm a t r i c e s ，简称o p m s ) 的概念及其容错路由算法， 文献 2 5 在文献【2 3 】的基础上修改了o p m s 的定义，提出了扩展最优通路 矩阵( e x t e n d e do p t i m a lp a t hm a t r i c e s ，简称e o p m s ) 的概念及其容错路由 算法，文献 2 6 在文献【2 3 、 2 5 的基础上提出了极大安全通路矩阵 2 第一章绪论 ( m a x i m u ms a f e t yp a t hm a t r i c e s ，简称m s p m s ) 的概念及其容错路由算 法，它们记录的最优通路信息都比安全向量( s a f e t yv e c t o r s ，简称s v s ) ， 扩展安全向量( e x t e n d e ds a f e t yv e c t o r s ，简称e s v s ) 要多，搜索最优 通路的能力比s v s ，e s v s 要强，它们都是s v s 的容错路由算法的扩展，而 m s p m s 是s v s ，e s v s ，o p m s 以及e o p m s 的最大扩展。 本文所指的图都是有限、无向、简单图。 广东工业大学理学硕十学位论文 第二章图的能量 帚一早 图目y 月e 里 本章主要是介绍单圈图能量的计算方法，以及单圈图类型的划分。 通过计算7 阶以及7 阶以内的单圈图的能量，找到一对等能量图。为了计 算单圈图的能量，首先要介绍一些基本的概念和引理。 2 1 基本概念 定义2 1 1 能量：设图g 有n 个顶点，m 条边，称为( n ，m ) 图。g 的邻 接矩阵是a ( g ) ，图g 的特征多项式是矽( g ，旯) = d e t ( m 一彳( g ) ) 。矽( g ，a ) = 0 的 根 ，乃，九是图g 的特征值。由于a ( g ) 是实对称矩阵，所以图g 的特 征值都是实数，图g 的能量被定义为：e ( g ) = j aj + l 五l + + i 九i 在化学中，分子图的能量与这个图所表示的分子的万电子总能量有 密切关系。共轭分子生成所产生的热能几乎等于该分子的万电子总能 量，而分子的万一电子总能量的计算又可归咎于e ( g ) = 闰i = n ，i 的计算。 图g 的特征多项式痧( g ，x ) = d e t ( x i - a ( g ) ) = 哆x ”。 令6 f ( g ) = l q ( g ) l ，汪o ，1 ，门。那么6 0 ( g ) = i ( g ) l = l ，6 2 ( g ) 是图g 边 的个数，令m ( a ，k ) 为图g 的k - 匹配数( 一个k 匹配就是图g 的k 条边的 集合，其中这k 条边中没有任何两条是有公共点的) 。特别的，若g 是无 圈图，那么如女= m ( g ，k ) 和b 2 女+ 1 = 0 ，k 0 d s 。 定义2 1 2 等能量图：同阶的两个图如果能量相等，则称该二图为 等能量图。 设g 是聆阶非本原图，令h j = g 疋 砭，h 2 = g c 4 ，经计算有 e ( q ) = e ( h 2 ) = 4 e ( g ) ，所以马和必是一对等能量图【2 7 】其中 表示张量 积。 4 笫二章图的能量 定义2 1 3 树图 连通的无圈图称为树，常用丁来表示。 定义2 1 4 循环图 令s 1 ，2 ，n ) ，其中如果i s ，那么，2 一i s 也成立。图g 的点集 合为v = ，v l ，u 一1 ) ，并且如果f j ( m o d n ) s ，则v ，就和v j 相关，这时 称图g 为循环图。圈e 是循环图的特殊情况。 定义2 1 5 单圈图 具有n 个顶点，胛条边的连通图称为单圈图。 若单圈图g 里面含有长度为j 的圈，则用g ( n ，) 来表示。显然有 g ( n ，行) = c ( 聆，行) = g 和g ( n ，n - 1 ) = c ( 玩l q 一1 ) = 群。) 。其中c ( n ，z ) 表示所有n 个顶点且含圈c 的单圈图的集合，并在圈c f 上连有力一z 个悬挂点；彰表 示在圈g 上挂一个路见- ，的所有的单圈图的集合。 2 2 主要定理及引理 当g 是树图丁时，则其能量e ( t ) 可表示成下列积分形式【2 8 】： 印啪降k = l 蛳妯卜 这里的m ( r ，k ) 是树图丁的k 匹配。并且e ( t ) 是所有匹配数m ( t ，k ) ， 后= o ，l ，2 ，嗟 ，的严格单调增量函数。 即如果聊( 互，后) m ( t 2 ，| i ) ， 忌= o ，1 ，2 ，唾】，则e ( 互) e ( 互) ，且至少有一个聊( 互，庇) m ( t z ，忌) 时， 则 e ( 五) e ( 乏) 。 引理2 2 。1 ( s a c h s 定理)设g 是玎个点，m 条边的无向图，其邻接 矩阵为a ( g ) ，那么其特征多项式( g ，x ) 中，项x ”的系数为： 广东工业大学理学硕上学位论文 ( 一1 ) 唧7 2 酬们。 y 其中y 是g 中具有，个顶点的s a c h s 子图( 即每个分支为一条边或者一 个圈的子图) 集c o m p ( ，) 和c y c ( ；o 分别为y 的分支个数和圈的个数。 引理2 2 2 t 2 9 】若g 是个含有一个长度为，的圈的单圈图，那么对于所 有的k 0 ，都有( 一1 ) a 2 t 0 。进一步，如果，= 2 r + l ，并且，是奇数( 相反 的厂是偶数) ，有( 一1 ) 。a 2 m 0 ( 相反的是( 一1 ) a 2 + 1 0 ) 。 引l l2 2 3 t 2 9 】( a ) 令g g ( n ，) ，其中，是模4 不恒等于0 ，如果w 是g 中q 上的一条边，那么有：6 f ( g ) = 勿( g 一甜v ) + 包一2 ( g 一“- v ) + 2 b , 一，( g c f ) 。 ( b ) 令g g ( n ，) ，并且令“v 为g 上的一条悬挂边，悬挂点为，那么有： 6 l ( g ) = 包( g v ) + 包一2 ( g u v ) 。 引理2 2 4 1 2 7 1 如果c 是一个n 阶的循环矩阵，其第一行元素为： q ，a 2 ，那么c 的行列式为：d e t c = 1 1 ( q + a 2 c o 。+ 吃粤2 7 + + a n c o 7 ) 。 这里的c o 是1 的刀次单位根。 若g 是刀阶循环图，且a ( g ) 的第一行中，数字1 在口，+ 1 的位置上，其 余位置上数为o ，那么它的特征值则为： c o 。口1 + 国加：+ + 国7 唧：0 刀一1 ，是1 的n 次单位根) 。 在研究极值能量和等能量图方面已有下列结果： 2 3 一些能量结果 1 f i “对于船个点的树图丁，最大能量图为路，最小能量为以，另外 几种图能量顺序为： e ( x 。) e ( y n ) e ( z 。) 2 个点的二部图，那么e ( g ) 去( 石+ 习。等号 成立的条幅当且仅孙2 v ，g 是一爪2 _ 半，学) 设计的关 联图。 4 1 3 4 1 - 设g 是一个门个点，m 条边的图，它的度序列为西，d 2 ，以，那么 e ( g ) + 等式成立当且仅当g 或者是兰乞研= 2 m ) ，屯( 聊= 刀( 刀一1 ) 2 ) ，一个非完全连 8 ；卜b ；鬈。 黾 足奎 肌鼍 第二镦图的能鬣 通强正则图，具有两个非平凡的特征值，其绝对值为、( 2 所一p ) 2 ( n 1 ) ) v脾 或者为n r , ( m = 。 5 1 3 s 1 设g 是个连通图，有，z 个点，m 条边，那么e ( g ) + ，等式成立当且仅当g 是完全图琏，或者g 是 个强正则图，具有两个非平凡的特征值，其绝对值皆为： ? 2 磁一( 2 磁斑) 2 ro 设单蚕图g 具有嚣个项点，n 条边，黑g ( n ，；来表示所有瓣个顶点且 里面含有长度为j 的圈的单圈图，c ( n ，) 表示所有，2 个顶点且含圈c ，的单 匿图的集合，并在圈g 上连有辑一个悬挂点；表示在圈q 上挂一个路 岛一，的所有的单圈图的集合。 显然有g ( n ，托) = c ( 妨= g 和g ( n ，孵一1 ) = 0 ( n 1 ) = 群一1 。 对于单露隧能量，有如下主要结果： 2 5 主要结果 定理2 5 1 g ( n ，) 是具有胛个顶点，且含有一个圈c ：的单圈图的集 合。( 3 z 嚣) ；在7 阶及7 阶以内的单圈圈中，只存在一对等能量图，并 且它们是同谱的。 证哽：对于单圈图能量的计算，可将单圈图分为两大类： 一类是循环图；另类是带有悬挂边的单圈图；由弓| 理2 2 。4 可知， 若g 是门阶循环图，且a ( g ) 的第一行中，数字l 在a ，+ l 的位置上，其余 位置上数为0 ，那么它舱特征值则为： 国问+ 缈心+ + 。鲰：0 歹n - 1 ，c o 是1 的n 次单位根 9 广东工业大学理学硕士学位论文 对于第一类循环图来说，它的特征值都很容易求出来，因而其能量 可以很容易得出。 经过计算可得，z = 8 以及8 以内的第一类的循环图的谱以及能量，如 下表2 1 所示： 表2 一l t a b l e 2 1 阶数 谱能量 玎 3 2 ，一1 ，- 1 4 4 2 ，0 ，- 2 ，0 ) 4 5 2 ，2 c o s ( 2 7 r 5 ) ，2 c o s ( 2 ，r 5 ) ， 2 + 4 ( c o s ( z 5 ) - t - c o s ( 2 7 r 5 ) ) - 2 c o s ( r r 5 ) ，- 2 c o s ( r e 5 ) ) 6 2 ，1 ，一1 ，- 2 ，- 1 ，1 8 7 2 ，2 c o s ( 2 ，r 7 ) ，- 2 c o s ( 3 z r 7 ) ，2 + 4 ( c o s q r 7 ) + c o s ( 2 x 7 ) + - 2 c o s q r 7 ) ，- 2 c o s q r 7 ) ， c o s ( 3 x 7 ) ) - 2 c o s ( 3 x 7 ) ，2 c o s ( 2 x 7 ) ) 8 2 ，压，0 ，一压，2 ，一压，0 ，压 4 + 4 4 2 对于第二类图，设刀个点的图g 的特征多项式为： n ( g ；x ) = d e t ( x i - a ( g ) ) - - z 口，x ”。 令b = a i l ，当g 是无圈图时，对于k 0 来说，6 2 。= 聊( g ，后) 和6 2 m = o 成 立。m ( g ，k ) 是图g 的k 匹配数。 当圈长，0 m o d 4 ，即，4 ，8 ，1 2 ，1 6 ，时，由引理2 2 3 可求出图的包( g ) 值，再根据引理2 2 2 可确定呸值的符号，从而可写出图g 的特征多项式。 从而求出图的能量。 对于，= 4 ，8 ，1 2 ，1 6 ，的时候，由引理2 2 1 可求出图g 的特征多项式系 数。 经计算可得刀= 7 以及7 以内的第二类单圈图的特征多项式，谱以及 l o 第二章图的能量 能量如下所示： 当刀= 4 时，只有1 种情况。当刀= 5 时，有4 种情况。其图形，特征多 项式，谱和能量等如下表2 2 所示： 表2 2 t a b l e 2 2 阶 种图形特征多项式谱能量 数 类 n数 41 人 o ( x 1 = x 4 4 x 2 一1 ，- 1 4 8 1 2 ，0 3 1 1 1 ， 4 9 6 2 4 类 - 2 x 十12 17 0 1 ) 54 队 矽( x ) = x 5 5 x 3 o ，( 括一1 ) 2 ，以+ 西 类_ 2 x 2 + 3 x 一( 压+ 1 ) 2 ， ( 1 - , f i - 3 ) 2 ， 矽( x ) = x 5 5 x 3 6 4 2 8 6 2 x 2 + 4 x + 2 - 1 6 7 5 1 ，- 1 ，- 0 5 3 9 2 ， 1 ，2 2 1 4 3 大 矽( x ) = x 5 5 x 3 - 1 8 1 3 6 ，一1 ，o ，0 4 7 0 7 5 4 8 8 7 2 x 2 + 2 z ，2 3 4 2 9 i 矽( x ) = x 5 5 x 3 o ，- + 4 1 0 + 2 4 1 71 2 ，4 1 0 + 2 4 1 7 u + 2 x - + x 1 0 2 x 1 71 2 + 1 0 2 4 1 7 同样道理当刀= 6 时，有12 种情况，根据上述方法可以计算出6 阶的 单圈图的特征多项式以及能量如下： 矽( x ) = x 6 6 x 4 + 8 x 2 2 x 一1 ， 矽( x ) = x 6 6 x 4 2 x 3 + 6 x 2 1 ， e ( g ) = 7 4 6 5 8 e ( g ) = 2 ( 垢+ 4 5 ) 广东工业大学理学硕士学位论文 ( x ) = x 6 6 x 4 2 x 3 + 5 x 2 ， 矽( x ) = x 6 6 x 4 2 x 3 + 7 x 2 + 2 x 一1 ， 矽( x ) = x 6 6 x 4 2 x 3 + 3 x 2 ， 矽( x ) = x 6 6 x 4 2 x 3 + 6 x 2 + 2 x 一1 ， o ( x ) = x 6 6 x 4 2 x 3 + 8 x 2 + 4 x 一1 ， 矽( x ) = x 6 6 x 4 2 x 3 + 7 x 2 + 4 x ， 矽( x ) = x 6 6 x 4 + 5 x 2 1 ， 矽( x ) = x 6 6 x 4 + 5 x 2 ， 矽( x ) = x 6 6 x 4 + 4 x 2 ， o ( x 1 = x 6 6 x 4 + 6 x 2 2 ， e ( g ) = 6 4 8 5 2 e ( g ) = 7 4 1 6 e ( g ) = 6 1 7 2 2 e ( g ) = 7 3 4 2 5 e ( g ) ：3 + 压+ 廊 e ( g ) = 7 1 9 1 6 e ( g ) = 7 2 0 7 8 e ( g ) = 2 + 2 x 5 e ( g ) = 2 而 e ( g ) = 6 6 0 2 6 当n = 7 时，共有31 种情况，单圈图的特征多项式及其能量为： o ( x 1 = x 7 7 x 5 + 1 3 x 3 7 x ， 矽( z ) = x 7 7 x 5 + 1 2 x 3 2 x 2 + 4 x ， 矽( x ) = x 7 7 x 5 + 1 2 x 3 2 x 2 3 x ， ( x ) = x 7 7 x 5 + 6 x 3 2 x 2 2 x ， ( x ) = x 7 7 x 5 + 1 3 x 3 2 x 2 6 x + 2 ， 矽( x ) = x 7 7 x 5 2 x 4 + 9 x 3 2 x ， 矽( x ) = x 7 7 x 5 2 x 4 + 1 l x 3 + 2 x 2 4 x ， 矽( x ) = x 7 7 x 5 2 x 4 + 7 x 3 ， 矽( x ) = x 7 7 x 5 2 x 4 + l o x 3 + 2 x 2 3 x ， 1 2 e ( g ) ：2 + 2 厮+ 2 廊 e ( g ) = 8 4 2 8 6 e ( g ) = 7 4 6 5 8 e ( g ) = 8 1 2 8 2 e ( g ) = 8 9 1 7 3 e ( g ) = 8 0 0 9 4 e ( g ) ：压+ 6 i 万 e ( g ) = 7 0 2 0 6 e ( g ) = 8 2 2 5 9 第二章图的能量 矽( x ) = x 7 7 x 5 2 x 4 + 1l x 3 + 4 x 2 - 2 x ， e ( g ) = 8 1 7 0 9 矽( z ) = x 7 7 x 5 2 x 4 + 1 2 x 3 + 4 x 2 - 4 x ，e ( g ) = 7 5 4 9 2 ( x ) = x 7 7 x 5 2 x 4 + 8 x 3 ，e ( g ) = 3 + 万 ( x ) = x 7 7 x 5 2 x 4 + 1 0 x 3 + 2 x 2 - 2 x ， e ( g ) = 8 0 8 5 1 驴( x ) = x 7 7 x 5 2 x 4 + 1 2 x 3 + 4 x 2 - 5 x - 2 ， e ( g ) = 8 8 7 0 1 矽( x ) 兰x 7 7 x 5 2 x 4 + 4 x 3 ， e ( g ) = 6 6 4 2 8 矽( x ) = x 7 7 x 5 2 x 4 + 8 x 3 + 2 x 2 2 x ， e ( g ) = 7 9 6 8 8 矽( x ) = x 7 7 x 5 2 x 4 + 1 0 x 3 + 4 x 2 2 x ， e ( g ) 亍8 11 7 9 ( x ) = x 7 7 x 5 2 x 4 + ll x 3 + 4 x 2 3 x ， e ( g ) = 8 3 0 1 1 矽( x ) = x 7 7 x 5 2 x 4 + 1l x 3 + 4 x 2 - 5 x - 2 ，e ( g ) = 6 + 2 4 2 矽( x ) = x 7 7 x 5 2 x 4 + 1 2 x 3 + 6 x 2 - 4 x - 2 ， e ( g ) = 8 8 6 0 6 ( x ) = x 7 7 x 5 2 x 4 + 1 2 x 3 + 6 x 2 2 x ， e ( g ) = 8 2 6 1 7 矽( x ) = x 7 7 x 5 2 x 4 + 1 3 x 3 + 6 x 2 5 x 一2 ， e ( g ) = 8 9 4 0 8 矽( x ) = x 7 7 x 5 + 9 x 3 - 3 x ， ( x ) = x 7 7 x 5 + 4 x 3 ， 矽( x ) = x 7 7 x 5 + 8 x 3 ， 矽( x ) = x 7 7 x 5 + 1 0 x 3 4 x ， ( x ) = x 7 - 7 x 5 + 1 0 x 3 - 5 x ， 矽( x ) = x 7 - 7 x 5 + 6 x 3 ， 矽( x ) = x 7 - 7 x 5 + 1 0 x 3 4 x ， 1 3 e ( g ) ：2 + 2 6 丽+ 2 卮孺 e ( g ) = 2 4 i i e ( g ) ：扛i 而+ 扛j 而 e ( g ) ：2 + 2 届 e ( g ) = 8 2 0 7 8 e ( g ) = 2 + 2 4 9 e ( g ) = 2 + 2 4 i - 6 广东工业大学理学硕十学位论文 ( x ) = x 7 7 x 5 + 1 l x 3 6 x ， 矽( x ) = x 7 7 x 5 + 9 x 3 4 x ， e ( g ) = 8 1 2 e ( g ) = 8 0 0 4 由上述计算结果知，当刀= 7 时，下面的图1 和图2 能量相等，其能量为 2 + 2 而。并且它们的谱为： o , - 1 , 1 , - l ( x 而+ 扬，三( 河+ 历，一三( 河一面，丢( 河一扬) 。 图2 1 g r a p h 2 1 图2 2 g r a p h 2 - 2 本章小结：本章主要讨论了图论在化学能量方面的应用，对图能量 给予介绍，并给出了关于能量的一些主要结果。对于不同类型的图，其 能量有不同的特点。在这一章里，本人所做的工作有：通过对单圈图的 图特点的分析，将单圈图分为二大类，第一类为循环图；第二类为带有 悬挂边的单圈图，进一步细分第二类单圈图，根据圈长可分为 ，= 4 ，8 ，1 2 ，1 6 ，和，0 m o d 4 ，两种情况，依据分法分别计算出7 阶以内的单 圈图的能量，从而得出一对同谱的等能量图。 1 4 第三章超立方体网络算法 第三章超立方体网络算法 3 1 超立方体基本概念 定义3 1 1 超立方体 3 6 】超立方体是一个由2 ”个节点组成的 1 维的 图，记作q 。图中每个节点地址用0 到2 ”一1 个二进制数字来表示，其中 每个节点都有，z 个邻节点和它相连，当且仅当两节点地址有且只有一个 数字相异时，它们是相连的。节点地址记为u ( n ) u ( n - 1 ) 甜( 1 ) ，u ( i ) o ，1 ) ， 1 f 玎，其中“( f ) 表示节点地址的第f 位。“( 是指甜沿f 维的邻节点，是甜 的第i 维的地址。如：11 0 1 ( 2 ) = 1 0 0 1 ，标志。定义了两个节点地址相异的 维数，如：1 0 0 1 0 1 1 1 0 = 0 1 1 1 。 定义3 1 2 距离【3 6 】对于7 1 维超立方体q 中的节点，a ( c o , ，书，q ) ， b ( q 7 ，q 一。7 ，q7 ) ，其中国，国，7 0 ，1 ) ，j 1 ，z 】；定义么，曰之间的互异位的个 数，即彳，曰之间的h a m m i n g 足e 离为么，b 之间的距离；若4 ，b 之间的距离为 k ，则称么，b 具有k 距离。 定义3 1 3k 距离最优通路【3 6 1 对于疗维超立方体q 中的节点彳，b ， 若它们之间的距离为老，且么，召之间存在一条距离为k 的通路，则称么，曰 之间存在k 距离最优通路，或简称为4 ，b 之间存在最优通路。 定义3 1 4 相对地址【3 6 】两个节点4 ，b 的相对地址r e l ( a ，b ) 等于两 个节点地址相应位的异或即若a ( c o , ，吧书，q ) ，b ( 鸭7 ，一。7 ，q ) ，则 r e l ( a ，b ) = ( 魄o 7 ，鸭一。o 一1 ，qoq ) ，同节点坐标一样，两节点的相 对地址也可看成是一个厅位二进制数。 对于每个点a 都存在一个向量与之对应，记为s y = ( 1 l i , “：，“。) 特别 的，s v k 的值代表的是该点是否能够到达距离为k 的点。 定义3 1 5 安全向量乜故障点的安全向量为( o ，0 ，0 ) ，如果4 是故 障的一端，那么对于点么来说，另