（运筹学与控制论专业论文）具有完美匹配的图依能量的排序.pdf

上海大学博士学位论文 摘要 图的能量定义为图连接矩阵的所有特征根的绝对值之和在化学图论中，研究具有 极值能量的图具有十分重要的理论意义和应用价值图的能量越大( 小) ，相应化合物的 热力学稳定性越强( 弱) 共轭分子图根据其是否具有k e k u l 6 a n 结构，可分为k e k u l 6 a n 分子图和非k e k u l 6 a n 分子图在图论中，k e k u l 6 a n 结构称为完美匹配具有完美匹配的图具有许多化学的性 质例如，是否具有完美匹配对于芳香族系统的稳定性是及其重要的 基于具有完美匹配的图在化学上的重要性，本文研究此类图的极值能量图问题记 此类图的顶点个数为2 n 主要工作和结果有以下五部分 ( 1 ) 考虑了最大度不超过3 ，并且具有完美匹配的树依能量从小到大的排序问题我 们采用了比文献( l ih ，m a t h c h e m 2 5 ( 1 9 9 9 ) 1 4 5 - 1 6 9 ) 更加简捷的方法，当n + l 1 4 时，得到了2 礼一2 r 一5 个具有较小能量的树并加以排序，其中r 由佗+ 1 三r ( m o d4 ) 确定这个结果比文献( l i1 9 9 9 ) 中得到的具有较小能量树的个数多了佗一r 一6 个当 6 n + 1 1 3 时，我们也分别得到了许多具有较小能量的树并加以排序 ( 2 ) 考虑了直径为d ，并且具有完美匹配的树的极值能量图问题当4 d 1 0 时，分别得到了极小能量图对于d = 5 ，当n = 2 h 和扎= 2 h + 1 时，还分别得到了 ( 1 + v 丽- 3 ) 2 和、，佤+ 1 个具有较大能量的树并进行了排序，其中h 是不小于2 的正 整数 ( 3 ) 考虑了具有完美匹配的树依能量从小到大的排序问题我们运用了比文献( z h a n g f j l ih d i s c r e t ea p p l m a t h 9 2 ( 1 9 9 9 ) 7 1 8 4 ) 更加简单的证明方法，得到了此类 图的极小，次- - j , 和次三小能量图 ( 4 ) 考虑了最大度不超过3 ，并且具有完美匹配的单圈图依h o s o y a 指标的排序及其 极小能量图问题首先，在四种特殊情况凡得到了这四类图依h o s o y a 指标从小到大的 排序接着，确定了所考虑图类中多个具有较小h o s o y a 指标的单圈图并加以排序进一 步地，得到了此类图的极小能量图 ( 5 ) 考虑了具有完美匹配的单圈图，得到了此类图的极小能量图 关键词；图的能量，完美匹配，树，单圈图，排序 p h dd i s s e r t a t i o no fs h a n g h a iu n i v e r s i t y a b s t r a c t n l t h ee n e r g yo fag r a p hi sd e f i n e da st h es u mo ft h ea b s o l u t ev a l u e so fa l lt h ee i g e n v a l u e s o ft h eg r a p h t h ei n v e s t i g a t i o no i lt h eg r a p h sw i t he x t r e m a le n e r g i e si so ft h e o r e t i c a l i n t e r e s ta n dp r a c t i c a li m p o r t a n c ei nt h es u b j e c to fc h e m i c a lg r a p ht h e o r y t h el a r g e rt h e v a l u eo fe n e r y , t h eg r e a t e rt h et h e r m o d y n a m i cs t a b i l i t yo ft h ec o r r e s p o n d i n gc o m p u n d c o n j u g a t e dm o l e c u l e si nc h e m i s t r ym a yb ec l a s s i f i e di n t ot w og r o u p s ：k e k u l d a na n d n o n - k e k u l d a nm o l e c u l e s ，d e p e n d i n go nw h e t h e ro rn o tt h e yp o s s e s sk e k u l d a ns t r u c t u r e s ， i e ，t h ep e r f e c tm a t c h i n g si ng r a p ht h e o r y t h eg r a p h sw i t hp e r f e c tm a t c h i n g sp o s s e s s m a n yc h e m i c a lp r o p e r t i e s f o re x a m p l e ，t h ee x i s t e n c eo fp e r f e c tm a t c h i n g si sc l o s e l y c o n n e c t e dt ot h es t a b i l i t yo fa r o m a t i cs y s t e m s i nv i e wo ft h es i g n i f i c a n c eo ft h eg r a p h sw i t hp e r f e c tm a t h i n g si nc h e m i c a lg r a p h t h e o r y ，t h i sk i n do ft h e 酽a p h sw i t he x t r e m a le n e r g i e si si n v e s t i g a t e di nt h i st h e s i s t h e v e r t e xn u m b e ro ft h eg r a p h sc o n s i d e r e di sd e n o t e db y2 n t h em a i nr e s u l t sc a nb ed i v i d e d i n t of i v ep a r t sa sf o l l o w s f i r s t l y , t h eo r d e r i n go ft h em i n i m a le n e r g i e so ft h et r e e sw i t hap e r f e c tm a t c h i n g h a v i n gd e g r e e sn og r e a t e rt h a nt h r e ei 8c o n s i d e r e d b ym e a n so fas i m p l e rm e t h o dt h a n t h a to fl i ( zm a t h c h e m 2 5 ( 1 9 9 9 ) 1 4 5 1 6 9 ) ，w eo b t a i nt h ef i r s t2 n 一2 r 一5t r e e si n t h ei n c r e a s i n go r d e ro ft h e i re n e r g i e sw i t h i nt h ec l a s su n d e rc o n s i d e r a t i o nf o rn + 1 1 4 ， w h e r eri sd e t e r m i n e db y 佗+ 1 三r ( m o d4 ) t h en u m b e ro ft h et r e e so b t a i n e dh e r e e x c e e d st h er e p o r t e dr e s u l t ( l i1 9 9 9 ) b y 佗一r 一6 w ea l s og e tal o to fp r e c e d i n gt r e e si n t h ei n c r e a s i n go r d e ro ft h e i re n e r g i e sw i t h i nt h ec l a s sf o r6 扎- b1 1 3 s e c o n d l y , t h ee x t r e m a le n e r g i e so ft h et r e e sw i t hap e r f e c tm a t c h i n gh a v i n gag i v e n d i a m e t e rda r eo b t a i n e d t h eg r a p h sw i t hm i n i m a le n e r g i e sa r eg i v e nf o r4 d 1 0 a s d = 5 ，w eo b t a i nt h el a s t ( 1 +3 ) 2a n d 狐+ 1 t r e e si nt h ei n c r e a s i n go r d e ro ft h e i r e n e r g i e sw i t h i nt h ec l a s su n d e rc o n s i d e r a t i o nf o rn = 2 ha n dn = 2 h + 1 ，r e s p e c t i v e l y , w h e r eh 2 。 t h i r d l y , t h eo r d e r i n go ft h em i n i m a le n e r g i e so ft h et r e e sw i t hap e r f e c tm a t c h i n gi s s t u d i e d w ee m p l o yas i m p l e rm e t h o dt h a nt h a to fz h a n g l i ( d i s c r e t ea p p l m a t h 9 2 ( 1 9 9 9 ) 7 1 - 8 4 ) t of i n dt h et r e e sh a v i n gt h em i n i m a l ，t h es e c o n d - m i n i m a l ，a n dt h e 1 v t h i r d - m i n i m a le n e r g i e s n e x t ，t h eo r d e r i n go fu n i c y c l i cg r a p h sw i t hp e r f e c tm a t c h i n g sh a v i n gd e g r e e sn o g r e a t e rt h a nt h r e eb yt h e i rh o s o y ai n d e x e si sc o n s i d e r e d f o u rs p e c i a lc a s e si nt h ei n - c r e a s i n go r d e ro ft h e i rh o s o y ai n d e x e sa r es t u d i e d t h ep r e c e d i n gg r a p h si nt h ei n c r e a s i n g o r d e ro ft h e i rh o s o y ai n d e x e sa r ed e t e r m i n e d f u r t h e r m o r e ，t h ec o r r e s p o n d i n g g r a p h sw i t h m i n i m a le n e r g i e sa r ep r o v i d e d f i n a l l y , u n i c y c l i cg r a p h sw i t hp e r f e c tm a t c h i n g sh a v i n gm i n i m a le n e r g ya r ec o n s i d - e r e d t h ec o r r e s p o n d i n gg r a p hw i t hm i n i m a le n e r g yi sm a t h e m a t i c a l l yv e r i f i e d k e yw o r d s ：e n e r yo fag r a p h ，p e r f e c tm a t c h i n g ，t r e e ，u n i c y l i cg r a p h ，o r d e r i n g 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工 作。除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已发表或撰写过的研究成果。参与同一工作的其他同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 日期：矽孑易，7 1 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 库碰吼删 上海大学博士学位论文 第一章绪论 1 1 立题背景和研究意义 1 1 1 1 图的能量 图是图论的基本研究对象，此概念从一开始出现就与分子图具有密切的联系 2 0 世 纪上半叶以来，图的研究与化学建立了新的联系，人们发现h t i c k e l 分子轨道理论与图的 谱之间存在明确的对应关系例如，图的谱对应于分子能级，特征向量对应于分子轨道 等等这样，许多代数图论的结果有了明确的实际背景【1 】 设g 足分子图，a 足其连接矩阵，a 的特征根为a l ，k 在h i i c k e l 分子轨道 ( h m o ) 意义下，图g 的h m o 总弘电子能量定义为 e ( g ) = i a l i + l a s l + i h i ( 1 1 ) 由式( 1 1 ) 定义的能量e ( g ) 可推广到任意图g 的能量对h m o 总卅电子能量的详细 说明可见文献【2 ，3 】 h m o 总7 r 电子能量e 是一个众所皆知的拓扑指标，在理论化学中具有十分重要 的作用作为共轭分子的一个重要参数，它足共轭分子的化学结构和热力学稳定性之间 的一个桥梁 4 】e 越大( 小) ，相应化合物的热力学稳定性越强( 弱) h m o 总7 r 电子能量在化学上有广泛的应用例如，它可以用来判断共轭碳氢化合 物雾化时产生的热量，也可以用来解释分子的结构和性质之间的关系 2 ，p 1 3 6 另外， 它还有一个很重要的应用是可以用来估计共振能量，由它计算得到的共振能量和用更繁 杂的s c fm o 方法得到的共振能量是一致的 2 】 此外，h m o 总卅电子能量和用相当准确的( s t o 3 g ) 从头算方法得到的丌电子 动能相比，具有完美的线性关系 2 】 尽管h m o 总丌电子能量具有局限性，但是，对于一个给定的共轭化合物，相对于 其他更复杂的方法，它仍是一个很好的估计 基于图能量的实际意义和理论价值，在化学图论中，研究图的能量具有十分重要的 地位和意义【5 】 1 1 2 图的h o s o y a 指标 早在1 9 7 1 年，h o s o y a 第个意识到，饱和碳氢化合物一些重要的化学性质与相应 2 第一章绪论 分子图中互不相邻的边的选择有关由此，h o s o y a 引入了图g 的k 匹配数m ( a ，七) ，即 g 中k 条互不相邻的边的数目，并称所有m ( a ，k ) 的和为拓扑指标，其中0 k h 2 】， 礼是g 的顶点个数后来，人们称这个拓扑指标为h o s o y a 指标【2 ，p 1 2 7 一个碳氢化合物的h o s o y a 指标和它的许多物理化学性质具有紧密的联系 6 ，p 1 5 3 】 7 h o s o y a 指标是碳氢化合物的热力学性质的单调函数例如，h o s o y a 指标的对数与 饱和碳氢化合物的沸点基本上具有线性关系，h o s o y a 指标的对数与无圈饱和碳氢化合 物的绝对熵也有紧密的联系f 2 ，p 1 2 9 另外，h o s o y a 指标是碳氢化合物的碳原子骨架图分支延伸的一个测量【6 ，p 1 5 3 对h o s o y a 指标的进一步了解可见g u t m a n p o l a n s k y 2 】2 的著作第十一章 基于h o s o y a 指标的应用背景，在化学图论中，研究图的h o s o y a 指标也具有十分重 要的意义【7 ，8 】 1 1 3 具有完美匹配的图 在化学上，k e k u l 6 a n 结构( 在图论中，称为完美匹配) 的数目简称为k e k u l 6 a n 数 共轭分子图根据其是否具有k e k u l 6 a n 结构可分成两类；k e k u l 6 a n 分子图( k e k u l 6 a n 数 不为0 ) 和非k e k u l 6 a n 分子图( k e k u l 6 a n 数为o ) 【9 】 自从上个世纪以来，在有机化学中，k e k u l 6 a n 结构就已经被应用到多圈共轭系统性 质的研究上人们用k e k u l 6 a n 结构来解释多圈碳氢化合物的结构和反应，得到了许多重 要的成果例如，共轭结构的异构体的热力学稳定性与k e k u l 6 a n 数成正比，即k e k u l 6 a n 数越多，异构体越稳定c l a r 推断不具有k e k u l 6 a n 结构的苯系统是一个不稳定的双游 离基，换句话说，非k e k u l 6 a n 苯环型分子是不存在的因此，是否具有k e k u l 6 a n 结构， 对于芳香族系统的稳定性是及其重要的【1 0 ，p 2 9 1 由于k e k u l 6 a n 分子图的重要性，一个世纪以来，具有k e k u l 6 a n 结构的图一直吸引 了许多化学工作者和数学工作者 1 2 国内外研究概况 图的能量自引入以来，对它的研究一直很热门对它的进一步了解可见g u t m a n p o l a n s k y 2 】和g u t m a n 【1 1 】等有关著作 研究图能量的基本公式源于1 9 4 0 年c o u l s o n 建立的公式，后来人们称之为c o u l s o n 积分公式 c o u l s o n 积分公式有许多重要的运用和推广 2 ，1 2 由c o u l s o n 积分公式， 图的能量可以通过图的特征多项式进行计算根据s a c h s 1 3 】建立的图特征多项式的系 数和图结构之间的关系，c o u l s o n 积分公式有了简捷的推论，这样，在某些情况下，对 上海大学博士学位论文 3 图的能量的研究直接转化为对图的七匹配数的研究 下面，我们对国内外有关于图能量的研究进行概括 1 2 1 图的能量的界 设g 是顶点个数为n ，边数为m 的图决定图g 能量大小的主要因素是n 和m 早 在1 9 5 5 年，h a l l 【1 4 就对这一方面进行了研究1 9 7 1 年，m c c l e l l a n d 【1 5 】首先得到 图g 的总丌- 电子能量的近似值，即e ( g ) a ( 2 m n ) 1 2 ，其中q = o 9 2 。m c c l e l l a n d 的 结果表明，e 随着n 和m 的增大而增大另外，e n g l a n d & r u e d e n b e r g 1 6 】也在这一 方面做了重要的贡献对于图g 的总丌- 电子能量与分子图的三个不变量：顶点个数礼， 边数m 和k e k u l 4 a n 结构之间的关系，也有一个系统的研究 1 7 ，1 8 】 m c c l e l l a n d 1 5 第一个得到了图g 的能量上界，即e ( g ) 、2 m n 随后，许多工 作者把兴趣转移到对图的能量界的研究关于图的能量上界和能量下界有许多结果，见 文献【1 9 ，2 0 ，2 1 ，2 2 ，2 3 ，2 4 ，2 5 】这些能量上界和能量下界估计值，或者不含有参数n 和 m ，或者仅限于共轭碳氢化合物中的一些特殊图类 近几年来，对图的能量上界的研究有以下进展k o o l e n 等【2 6 】得到了图g 的含 钆和m 的能量上界k o o l e n & m o u l t o n 2 7 】证明了文献 2 6 】得到的能量上界优于 e ( g ) 、2 m n 而后，k o o l e n m o u l t o n 2 8 得到了偶图g 的含佗和m 的能量上界 当g 是偶图时，文献【2 8 】得到的能量上界优于文献 2 6 得到的进一步地，g u o 【2 9 】 考虑了当边数和顶点数满足一定条件时偶图g 的能量上界，其所得到的能量上界优于文 献 2 8 得到的记图g 的度序列为也，其中1 i 佗z h o u 3 0 】得到了图g 的含n ，m 和也的能量上界，且刻划了具有最大能量的图和具有最大能量的偶图y u 等 3 1 】得到 了图g 的含n ，m ，也和2 一度t i 的两个能量上界，其中t i 是g 中与顶点耽相邻的顶点 的度之和进一步地，l i u 等【3 2 】得到了比文献【2 8 ，3 0 ，3 1 】更好的两个能量上确界最 近，l i u l u 【3 3 】得到了图g 邻接矩阵的最大特征根的上确界和能量e ( g ) 的上确界 1 2 2无圈图依能量大小的排序 。 首先，研究者考虑了树的极值能量图问题记r n 是n 个顶点的树的集合g u t m a n 【3 4 证明了r n 中具有最大能量的树是一条路，李乔和冯克勤【3 5 】也独立地得到了相同的 结论 g u t m a n 3 4 】也给出了前四个具有最小能量的树和具有次二大能量的树约三十 年后，l i l i 【3 6 】得到l 中的次五小至次七小能量树和次三大能量树随后，g u t m a n 等f 3 7 得到l 中的次二小至次七小能量树，次三大和次四大能量树 接着，研究者考虑了具有完美匹配的树的极值能量图问题记t 2 n 是顶点个数为2 佗， 具有完美匹配的树的集合皿2 n 是t 凯中顶点度不超过3 的树的集合易见雪孙与无 4 第一章绪论 环烯烃分子图的碳原子骨架是一致的，因而具有物理与化学背景【1 】由于路岛n 分别属 于t 轨和m 2 n ，故它是t 2 n 和皿2 n 的最大能量图关于t 2 n 和霍2 n 的最小能量图问题， g u t m a n 2 2 】利用计算机搜索，提出了两个猜想，他还进一步地对所有顶点个数小于1 6 的图验证了他的猜想十二年后，z h a n g l i 【3 8 】证明了这两个猜想的正确性，且给出 了t 2 n 的次二小和两个次三小能量图，其中这两个次三小能量图不可比较接着，z h a n g l i 【4 0 】考虑了t 2 n 和2 n 的最大能量图问题，得到了t 2 n 和m 2 n 的次二大至次四大 能量图 李怀恩【3 9 】继续考虑了m 2 n 中极小能量图的排序问题，确定了皿2 n 中近【1 1 】个较小 能量的树并加以排序和此问题有关的个论题是最高已占轨道( h o m o ) 与最底未占轨 道( l o m o ) 差的大小比较问题，作为图的一个参数，它有明确的物理化学背景【4 l 】绍 嘉裕和洪渊【4 2 确定了h o m o 和l o m o 差最大的图恰好是m 2 n 中的最小能量图张 福基和常安 4 3 】确定了h o m o l o m o 差较大的图( 当顶点个数不少于1 0 时) 由文献 4 2 ，4 3 】中所得的结论，可以看出，从总丌- 电子能量与h o m o l o m o 两个角度对树进 行考察，有些数学结论没有一致 1 】 近几年来，研究者主要考虑了树在给定某些条件下的极值能量图问题，主要有以下 几个方面的进展 候耀平p 矧考虑了具有给定匹配大小的树，得到了最小和次小能量图，并且给出了 最小和次小能量值王霄霞和郭晓峰【4 5 】考虑了具有给定非悬挂边数的树，得到了最小 和次小能量图 记f n ，d 是顶点个数为n ，直径为d 的树的集合y a n y e 【4 6 】得到了r m d 中的最 小能量图进一步地，z h o u l i 【4 7 得到了r n ，d 中的次小能量图o u 4 8 】考虑了f n ，d 的最大能量图问题，当d = 5 时，得到了最大能量图，且给出了最大能量图的h o s o y a 指 标表达式；当d = 4 时，他对f n d 中具有最大h o s o y a 指标的图提出了一个猜想，后来， 这个猜想被l i u 【4 9 证明成立 、，e c h e n 【5 0 考虑了给定两分划的树依能量和h o s o y a 指标的排序l i n 等【5 1 考 虑了具有给定最大度的树，在一定约束条件下，得到了最大能量图和最小能量图 y a h y e 【5 2 】考虑了具有许多悬挂顶点的树，得到了最大能量图y u l v 【5 3 】考虑了具 有k 个悬挂顶点的树，得到了最小能量图 1 2 3有圈图依能量大小的排序 下面，根据所含圈的不同分( i ) - ( i v ) 叙述这一方面的进展 ( i ) 单圈图 上海大学博士学位论文 5 首先，研究者考虑了偶单圈的最大能量图问题g u t m a n h o u 【5 4 得到了偶单圈 的最大能量图进一步地，h u a 【5 5 】得到了偶单圈的次二大能量图在文献 5 5 】的基础 上，通过计算机搜索，g u t m a n 等【5 6 】确定了偶单圈的最大，次二大和次三大能量图 同时，研究者考虑了单圈图的极值能量图问题h o u 【5 7 得到单圈图的最小能量 图h o u 等【5 8 】得到了单圈图的最大能量图进一步地，c h e n 等 5 9 】刻划了单圈图的 次- - d , 和次三小能量图 接着，研究者考虑了具有完美匹配的单圈图的极值能量图问题对于度不超过3 ，并 且具有完美匹配的单圈图，王文环 6 0 】得到了能量下界图；进一步地， w a n g 【6 1 】等得 到了此类图中部分图的最小能量图对于具有完美匹配的单圈图，“等 6 2 得到了最小 能量图和次小能量图 近几年来，研究者主要考虑了单圈图在给定某些条件下的极值能量图问题，主要有 以下几个方面的进展 z h o u l i 6 3 】得到了具有给定二分划的偶单圈图的最小能量图对于具有给定圈 长和悬挂顶点数的单圈图，h u a 【6 4 】得到了此类图中部分图的最小能量图；在文献【6 4 】 的基础上，进一步地，h u a w a n g 6 5 确定了此类图的最小能量图l i z h o u 6 6 得到了具有给定直径的单圈图的最小能量图w a n g 等【67 】得到当单圈图的圈上每个顶 点度都为3 时的最小能量图 ( i i ) 双圈图 h o u 6 8 】得到了至多有一个奇圈的双圈图的最小能量图进一步地，z h a n g z h o u 6 9 刻划了在一定条件下双圈图的最小，次小和次三小能量图y a n g & z h o u 【7 0 】确定 了给定直径d 的双圈图的最小能量图张建斌和周波【7 1 】得到了偶双圈的最小能量图 l i u z h o u 【7 2 】得到当一个圈长为4 r + 2 时的偶双圈图的最小能量图，其中，是正整 数 ( i i i ) 三圈图 目前，对三圈图的极值能量图的研究刚刚开始 l i 等 7 3 】得到了三圈图在一定限 制条件下的最小和次- - d , 能量图 ( i v ) 多角形系统 多角系统是连通平面图且没有割点，其每一个内面是边长为1 的正多边形 对六角系统的研究已很深入，见文献【1 1 ，7 4 】在六角系统中，若每一个顶点至多属 于两个六角形，则称这个六角系统为内缩六角系统在内缩六角系统中，若每一个六角 形至多只能和两个六角形相邻，则称为链状六角系统 在文献 7 5 和【7 6 】中，z h a n g 等分别得到了链状六角系统的最小能量图和最大能 6第一章绪论 量图进一步地， r a d a 【7 7 】采用和文献【7 5 】基本类似的方法，得到了内缩六角系统的 能量的排序 r a d a t i n e o 7 8 】考虑了链状多角形系统，当多角形的顶点个数为4 n 一2 时，得到 了最小能量图 最近，何梅芝等 7 9 】得到了全角六角链的最小能量图r e n z h a n g 8 0 】得到了双 链状六角系统的最小能量图 1 3 本文主要内容 根据对国内外参考文献的了解和调查，研究图的能量具有十分重要的意义由于图 能量e 越大( 小) ，相应化合物的热力学稳定性越强( 弱) ，因此，一般地，对于给定顶点数 和边数的连通图中，找出具有最大或最小能量的图是一个有意义且待解决的问题 基于具有完美匹配的图在化学上的重要性，且迄今为止，对于此类图的极值能量图 的研究还不够深入，因此，本文研究此类图的极值能量图问题主要考虑以下五种类型 的图： ( i ) 度不超过3 ，并且具有完美匹配的树； ( i i ) 给定直径d ，并且具有完美匹配的树； ( i i i ) 具有完美匹配的树； ( i v ) 度不超过3 ，并且具有完美匹配的单圈图； ( v ) 具有完美匹配的单圈图 主要研究内容包括以下五部分 在第二章里，考虑类型( i ) 中图依能量从小到大的排序问题 在第三章里，考虑类型( i i ) 中图的极值能量图问题 在第四章里，考虑类型( i i i ) 中图依能量从小到大的排序问题 在第五章里，考虑类型( i v ) 中图依h o s o y a 指标的排序及其极小能量图问题 在第六章里，考虑类型( v ) 中图的极小能量图问题 上海大学博士学位论文 第二章h i i c k e l 树的极小能量图的排序 7 在h i i c k e l 分子轨道理论中，所考虑的共轭碳氢化合物的分子常用碳原子骨架图来表 示，此类图的特征是最大度不超过3 ，并且具有完美匹配，我们称此类分子图为h i i c k e l 分子图h i i c k e l 分子图在化学上具有一定的应用背景例如，度不超过3 ，并且具有完 美匹配的树与无环烯烃分子图中的碳原子骨架是一致的【1 】在本章里，我们简称最大度 不超过3 ，并且具有完美匹配的树为h f i c k e l 树 记皿2 n 是顶点个数为2 竹的h i i c k e l 树的集合在本章里，我们研究皿2 n 中图依能 量从小到大的排序问题 2 1 基础知识 设t 是具有r 个顶点的树，a ( t ) 是其连接矩阵，t 的特征多项式是 1 3 】 ( t ，z ) = d e t x i a ( t ) _ 口i z h = e ( - 1 ) 知m ( t , k ) x 卜知， ( 2 1 ) 其中i 是r 阶单位矩阵，a o ，a l ，a ，是t 的特征多项式的系数，仇( r ，k ) 表示丁的 k 匹配数，即t 中七条互不相邻的边的个数记( zz ) = 0 的r 个根为入l ，即 为相应图t 的特征根共轭分子形成时，所产生的能量和总的7 r - 电子能量紧密相关， 在共轭分子中，总的丌电子能量，在h m o 意义下，可以表示成【2 】 e ( t ) = m ( 2 2 ) e ( t ) 也可以表示成c o u l s o n 积分式 2 】 e c t ，= 昙z + 刍h l1 + 否 r 2 1 仇c z 后，z 2 知i 出， c 2 3 ， 易见e ( t ) 是m ( t ，) 的严格单调递增函数 对于任意两个图g 1 和g 2 ，g u t m a n z h a n g 3 4 ，3 5 ，8 】定义了如下的拟序关系， 当k 0 ，有m ( g l ，k ) m ( g 2 ，七) ，记g 1 g 2 或g 2 g 1 若存在一个k ，使得 m ( g 1 ，k ) m ( g 2 ，七) ，记g l g 1 若g 1 g 2 且g l g 2 ，记g l = g 2 若 g 1 g 2 都不成立，称g l 与g 2 不可比较 8 依式( 2 3 ) ，有 第二章i - f 砬c k e l 树的极小能量图的排序 五t 2 = 号e ( 丑) e ( 乃) ， 7 1 磁r ，则e a s , ，6 t u 2 ，n 一2 u 2 h ，n 一2 h u 2 ，l + 1 ，住一2 h l u 2 h l ，n 一2 h + 1 阢，n 一1 ， ( 2 1 1 ) 式俚1 i ) 中第一和第二个等号成立分别当且仅当r = 1 和7 = 0 引理2 6 ：s l 当1 r 2 3 ，有 础 础扩卜f a s ，, 2 什l 、f a s ，, 2 计2 掰v 硪扩2 搿， ( 2 1 2 ) 式偿j 纠中第一和第二个等号成立分别当且仅当7 2 = 2 和r 2 = 1 当r 2 = 0 ，式侣1 2 ) 去掉“f a 8 ，, 2 掣+ 1 f a s ，, 2 掣+ 2 后仍成立 引理2 7 s 当1sr l 3 ，有 蹦 碟- 1 # 礞“磕+ 2 f a 2 ，z 磕_ 2 乒 碟， ( 2 1 3 ) 式偿f 砂中第一和第二个等号成立分别当且仅当r l = 2 和r l = 1 当r 1 = 0 ，式俾i s ) 去掉磕+ 1 。磕+ 2 。后仍成立 由以上引理，我们得以下六个推论 推论2 1 当1 r 2 3 ，有 磊 宁- 1 擘“口 6 s , 2 y + 2 d 8 , ，2 6 y e 譬_ 2 e 如s , 2 ， ( 2 1 4 ) 式偿j 引中第一和第二个等号成立分别当且仅当r 2 = 2 和r 2 = 1 当r 2 = 0 ，式俾钏去掉乎+ 1 g 口s , ，2 6 y + 2 后仍成立 证明：由引理2 1 和引理2 6 ，推论2 1 成立 推论2 2 当1 r l 3 ，有 e ： 孑1 。 1 。叫2 z + 2 ，2 6 叫2 z , 2 孑2 j 口2 , 6 ，t ( 2 1 5 ) 式偿! 砂中第一和第二个等号成立分别当且仅当r l = 2 和r l = 1 当r 1 = 0 ，式俾j 砂去掉“e 譬1 。口2 x ，6 + 2 。后仍成立 证明：由引理2 1 和引理2 7 ，推论2 2 成立 由引理2 1 和引理2 6 ，我们可得以下推论2 3 - 2 6 由于推论2 3 2 5 的证明和推论 2 6 相似，因此在这里我们省略推论2 3 - 2 5 的证明，只给出推论2 6 的证明 1 2 第二章i t 6 c k e l 树的极小能量图的排序 推论2 3 当3 a b ，则： 俐若o = 4 x + 1 或4 x + 3 ，有e 。1 , 暑d 2 6 , 1 ； 和砂若口= 4 x 或4 x + 2 ，有g ：暑口 6 1 , 2 ，等号成立当且仅当n = b 推论2 4 当5 a b ，其- i 。 俐若q = 4 x + 1 或4 x + 3 ，有：e 蒜； 一砂若口= 4 x 或4 x + 2 ，有s 蒜n 3 , ，b 1 ，等号成立当且仅当o = b 推论2 5 当7 a b ，贝j ： 例若o = 4 x + 1 或4 x + 3 ，有e 。l , ，：； 以砂若口= 4 x 或4 x + 2 ，有：j d ，6 1 , 4 ，等号成立当且仅当n = b 推论2 6 当9 a b ，则； 俐若n = 4 x + 1 或4 x + 3 ，有：口1 ，, 6 5 ； 一砂若口= 4 x 或4 x + 2 ，有蒜口5 , 1 ，等号成立当且仅当口= b 证明：当o = b 等号显然成立当b 口+ 1 ，有础= 砖蒜5 和 州搿叫= 巨 由引理2 6 得：若a = 4 x + 1 或缸+ 3 ，有 若a = 4 x 或4 z + 2 ，有 b b b b a + 1 a + 2 a + 3 a + 4 硪= 磋：蒜5 础盘句= 由引理2 1 ，推论2 6 得证 设珊是不小于2 的正整数，下面引入引理2 8 磁， 引理2 8 俐若f 口a s ，, 6 磁和f 口a s ，, l 磁车l ，则。f d a s ，, t 加 磁车加 似若飞f a s , 。t 磁，和碟1 6 磁暑。，则，。 磁。 证明：( i ) 当n 0 = 2 时，在f 口a s ，, t2 和e 群2 的研2 上，记e = u 6 + 1 2 ，由引理2 4 ，得 仇( ，毒0 2 ，z ) = m ( ，乏0 2 一e ，z ) + m ( ，玉0 2 一十l 一仇卜卜2 ，i 一1 ) = m ( 1 ，z ) + m ( 碟，i 一1 ) 上海大学博士学位论文 同理，可得 m ( 麟2 ，i ) = m ( 磁车。，i ) + m l 一, r a 一, b 矿，i 一1 ) 比较上面两式，由引理2 8 ( i ) 的条件，有 f 口a s ，, t2 瑶品， 由引理2 8 ( i ) ，当b 1 1 ，有搿 f 9 9 5 扩, 1 因此，当b 9 ，有 矗f ，, 5 ，0 ( 2 1 6 ) ( i i ) 当a = 1 0 ，b 1 0 ，由引理2 6 ，有 f i u