（系统分析与集成专业论文）几类特殊图的zagreb指标.pdf

摘要 摘要 组合化学的一个中心问题就是寻找具有某种物理或化学性质的分子。为了得 到所期望的分子，首先要得到这种分子的的拓扑指标并计算指标值，然后建立具 有这种指标值的分子图的数据库。 z a g r e b 指标主要用于分子设计、分子复杂性等方面，它反映了分子骨架的 分支程度，并与分子的能量有关z a g r e b 指标及其各种改进形式不但可以定量 的描述分子的结构，而且可以分析相关分子的结构与性能及之间的关系。本文主 要研究了双圈图和分子图的第一广义z a g r e b 指标的极值、双圈图的第二z a g r e b 指标的极值。 在论文的第一章，我们介绍了一些重要的拓扑指标，基本的图论概念和术 语，各种拓扑指标的研究进展以及在论文中我们得到的主要结果。 在论文的第二章，我们研究了双圈图的第一广义z a g r e b 指标取得极值、次 大( 小) 值、第三大( 小) 值的充要条件，并给出了所对应的图的结构 在论文的第三章，我们研究了分子图的第一广义z a g r e b 指标取得次大值和 次小值的必要条件 在论文的第四章，我们研究了双圈图的第二z a g r e b 指标的极值和次大( 小) 值、第三大( 小) 值的充要条件，并给出了所对应的图的结构。 在论文的第五章，我们对z a g e r b 指标提出了一些可以进一步研究的问题。 关键词：树，单圈图，双圈图，分子图，第一z a g r e b 指标，第二z a g r e b 指 标，第一广义z a g r e b 指标，改进的z a g r e b 指标，极值 1 1 1 a b s t r a c t a b s t r a c t ac r u c i a lq u e s t i o ni nc o m b i n a t i o nc h e m i s t r yi ss e a r c h i n gm o l e c u l e sw i t hs o m e p h y s i c o c h e m i c a lc h a r a c t e r i s t i c s i no r d e rt oo b t a i nt h ee x p e c t e dm o l e c u l e s ，w e f i r s t l yg e tt h et o p o l o g i c a li n d i c e so ft h em o l e c u l e sa n dc o m p u t et h ev a l u e ，t h e n e s t a b l i s ht h ed a t a b a s ec o n t a i n i n ga l lo ft h em o l e c u l a rg r a p h sw i t ht h ev a l u e t h ez a g r e bi n d i c e sa r em a i n l yu s e di nm o l e c u l ed e s i g n ，m o l e c u l ec o m p l e x i t y a n ds oo n t h e yd e s c r i b et h em o l e c u l es k e l e t o nb r a n c h ，a n dc o n c e r n sw i t ht h e m o l e c u l a re n e r g y t h ez a g r e bi n d i c e sa n dt h e i ri m p r o v e m e n tf o r m sm a y n o to n l y d e s c r i b et h em o l e c u l es t r u c t u r e ，b u ta n a l y z et h ec o r r e l a t i o nw i t ht h ec h a r a c t e r - i s t i c s t h i st h e s i sm a i n l ys t u d i e sb i c y c l i cg r a p h sa n dm o l e c u l a rg r a p h sw i t ht i l e e x t r e m a lv a l u e so ft h ef i r s tg e n e r a lz a g r e bi n d e x ，a n db i c y c l i cg r a p h sw i t ht h e e x t r e m a lv a l u e so ft h es e c o n dz a g r e bi n d e x i nc h a p t e r1 ，w ef i r s t l yi n t r o d u c es o m ei m p o r t a n tt o p o l o g i c a li n d i c e sa n d b a s i ct e r m i n o l o g i e s ，t h e ng i v eab r i e fo v e r v i e wt ot h em a i nr e s u l t so ft h et h e s i s i nc h a p t e r2 ，w ec h a r a c t e r i z ea l lt h eb i c y c l i cg r a p h sw i t ht h es m a l l e s t ，t h e s e c o n da n dt h i r ds m a l l e s tv a l u e so ft h ef i r s tg e n e r a lz a g r e bi n d e x ，a n dt h eb i c y c l i c g r a p h sw i t ht h el a r g e s t ，t h es e c o n da n dt h i r dl a r g e s tv a l u e so ft h i si n d e x i nc h a p t e r3 ，w eg a i ns o m en e c e s s a r yc o n d i t i o n sf o rt h em o l e c u l a rg r a p h st o a t t a i nt h es e c o n ds m a l l e s ta n dl a r g e s tv a l u e so ft h ef i r s tg e n e r a lz a g r e bi n d e x i nc h a p t e r4 ，w ec h a r a c t e r i z ea l lt h eb i c y c l i eg r a p h sw i t ht h es m a l l e s t ，t h e s e c o n da n dt h i r ds m a l l e s tv a l u e so ft h es e c o n dz a g r e bi n d e x ，a n dt h eb i e y c l i c g r a p h sw i t ht h el a r g e s t ，t h es e c o n da n dt h i r dl a r g e s tv a l u e so ft h i si n d e x i nc h a p t e r5 ，w ep r o p o s es o m ep r o b l e m sf o rf u r t h e rr e s e a r c ho nz a g r e b j n d i c e s k e y w o r d s ：t r e e ，u n i c y c l i cg r a p h ，b i e y c l i cg r a p h ，m o l e c u l a rg r a p h ，t h ef i r s t z a g r e bi n d e x ，t h es e c o n dz a g r e bi n d e x ，t h ef i r s tg e n e r a lz a g r e bi n d e x ，t h em o d i f i e d z a g r e bi n d e x ，e x t r e m a lv a l u e i v 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，印：研究生在校攻读 学位期间论文工作的知识产权单位属于西北工业大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查 阅和借阅。学校可以将本学位沦文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩日】或扫描等复制手段保存和汇编本学位论文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作 者单位为西北工业大学。 保密论文待解密后适用本声明。 学位论文作者签名：王盘l 一 年弓月1 砷日 指导教师签名丝! 唠 年弓月【吕日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的 学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所 知，除文中已经注明引用的内容和致谢的地方外，本沦文不包含任何其 他个人或集体已经公开发表或撰写过的研究成果，不包含本人或他人已 申请学位或其它用途使用过的成果。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名：主垒 歹一7 年5 月j 牛日 第一章绪论 第一章绪论 1 1 引言 图论是数学中一个比较年轻的分支，但在最近二十几年中有关图论本身及 其应用都得到了迅猛的发展在二十世纪三十年代以后，由于在生产管理，交通 运输、计算机和通讯网络等领域中许多离散问题的出现，大大的促进了图论的发 展特别在二十世纪七十年代，科学技术的突飞猛进增长，使得图论不仅与数学 的其它分支如群论矩阵论、拓扑学、概率论、组合数学等有了紧密的联系，而 且在生物学、运筹学，计算机科学，信息论、系统论、控制论等方面有了研究应 用的价值 众所周知，分子是由原子组成的，任何两个原子之间可以形成化学键，也可 以不成键，这是可以分辨的尽管分子的几何参数如分子之间的距离，键角等 是可以测量的，但是由于分子一直在做不停的运动，如分子的振动，内转动等， 使得分子中原子的位置会发生变化另外，分子的几何性质也会随着周围环境的 影响，比如温度。压力等而发生改变由于分子在不停的运动，我们可以把分子 的内部运动和所受的外部影响对其几何性质的影响看成是连续的，并没有键的破 坏或形成因此，在这些形变过程中，尽管分子的几何性质会发生改变，但是在 分子中原子之间的相互关联的性质并没有改变我们说分子中原子相互连通的全 部信息就确定了分子的拓扑性质 一个图是指一个有序三元组( g ) ，e ( g ) ，皿g ) ，其中v ( v ) 是非空的顶点 集，e ( g ) 是不与v ( g ) 相交的边集，而皿g 是关联函数，它使g 的每条边对应 于g 的无序顶点对若e 是一条边而札和甜是使得皿g ( e ) = u z ) 的顶点，则 称边e 连接顶点“和口；顶点和口称为边e 的端点从图的定义我们可以看 到，图表达的是点与边的连接关系因此从图的定义，我们知道图所表达的是图 的拓扑性质 在化学图论中，我们就用一个图来描述分子的拓扑结构我们用顶点表示原 子，边表示键，该图称之为分子图在考虑饱和及共轭的碳氢化合物时。顶点只 代表碳原子而忽略去氢原子，边只代表碳一碳原子之间的化学键，这种图叫做分 1 第一章绪论 子的骨架图，也称之为隐氢图分子图表达了分子的拓扑性质如果两个分子中 的原子之间具有相同的连通性质。或者说，它们具有相同的分子图，那么就可以 说两个分子的拓扑性质是相同的 一般来说，研究分子的拓扑指标，我们把在分子图中，或其矩阵表示中。不 依赖于顶点的标号方式的量叫做分子图的不变量例如图的顶点数，边数等都 可以作为其不变量。虽然分子的拓扑性质可以由分子图来描述，但是从本质上来 讲，分子图不是一个可以用数值来明确描述的对象而在实际应用中，通常用不 同的数值来描述分子的不同的可测量的物理化学性质。所以为了将分子的拓扑性 质与分子的可测量的物理化学性质联系起来，很有必要引入一些可以用数值表示 的量，并且它们与分子图中的某些性质有关经研究发现，分子图的各种不变量 不但可以定量的描述分子的结构，而且可以分析相关分子的结构与性能之间的关 系通常把具有这种作用的的分子图的不变量叫做分子拓扑指标 在化学界经常会遇到计算某分子图的拓扑指标值，从而统计的估计相对应的 分子的某种物理或化学性质同时也会遇到其逆问题，即想合成具有某种活性的 化合物因为分子图可以表示分子结构并且分子的拓扑指标可以统计的反映分 子的物理和化学性质，因此我们可以借助图论这个有用的工具，得到相应的分子 图，使得分子图的拓扑指标值为某个具体值或者在某个域内，这就是求给定分子 图的拓扑指标值的逆问题 当今组合化学的一个中心问题就是寻找具有某种物理或化学性质的分子为 了得到所期望的分子，首先要得到这种分子的拓扑指标，然后利用计算机搜索， 建立具有这种指标值的分子图的数据库，最后在库中选择最理想并且能够合成的 结构去合成它们这一过程的关键是建立具有某拓扑指标值的分子图的数据库， 而建立这个数据库所要解决的问题就是求给定分子图的拓扑指标的逆问题因 此，该问题的深入研究对有目的合成一些分子或药物有指导作用，具有重要的理 论价值和应用背景 在本章的第二节中，我们介绍了论文中所用到的一些图论中的概念和术语； 在第三节中，我们介绍了几种常用的拓扑指标；在第四节中，我们重点介绍了第 一广义z a g r e b 指标极值问题的研究进展；在第五节中，我们给出了第二z a g r e b 指标极值问题的研究进展；在第六节中，给出了本文的主要研究成果 2 1 1 2 基本概念与术语 1 2 基本概念与术语 本文只考虑有限简单图本文中没有说明的概念与术语见f 2 1 ，2 6 】 一个图是指个有序的三元组( v c a ) ，e c g ) ，妒g ) ，其中v ( c ) 是非空的顶点 集，e ( g ) 是不与v ( c ) 相交的边集，而妒g 是关联函数，它使g 的每条边对应 于g 的无序顶点对若e 是一条边，而札和口是使得i g ( e ) = 删的顶点，则 称边e 连接顶点和钉；顶点u 和钉称为边e 的端点 一条边的端点称为与这条边关联，反之亦然与同一条边关联的两个顶点称 为相邻的；与同一个顶点关联的两条边也称为相邻的端点重合为一点的边称为 环，端点不相同的边就称为连杆 一个图称为有限的，如果它的顶点个数和边数都是有限的只有一个顶点的 图称为平凡图，其它所有的图都称为非平凡图 如果一条边的两个顶点重合，则称之为环一个图称为简单图，如果它既没 有环也没有两条连杆连接同一对顶点 图g 的顶点度d ( u ) 是指g 中与“关联的边的数目记a ( g ) 为顶点最大 度，即所有顶点关联边的数目的最大值；d ( g ) 为顶点最小度，即所有顶点关联边 的数目的最小值我们用d ( g ) 是图g 的度序列，即d ( c ) = f d l ，d 2 ，厶1 ， 序列扛；1 ，z 字，z 纠表示图g 有啦个度为。的顶点，其中i = 1 ，2 ，t m 表示度为i 的顶点个数j v c c ) j = n 表示g 中顶点个数我们用v ( a ) 表示 图g 的顶点集，用e ( c ) 表示图g 的边集 我们用d ( g ) 表示图g 的度序列，即d ( g ) = f d l ，d 2 ，一，磊】。其中也表 示第i 个顶点的度度序列还可以表示为d c g ) = 【z ? 1 ，z 乳，z 纠，其中堙 表示图g 有吼个度为孔的顶点 g 的一条途径是指一个有序非空序列w = r o e l l e 2 e 讥，它的项交替她 为顶点和边，使得对1si k ，边e ；的端点是地一1 和地称钟是从如到御k 的一条途径顶点珈和巩分别称为w 的起点和终点，而饥，耽，一，一l 称为 它的内部顶点整数k 称为叫的长 若途径w 的边e l ，e 2 ，e 互不相同，则w 称为迹；若途径伽的顶点 3 第一章绪论 ”1 ，观，u 一l 也互不相同，则称7 1 1 为路 称一条途径是闭的，如果它有正的长度且起点和终点重合若一条闭迹的起 点和内部顶点互不相同，则它称为圈本文记d = “1 u 2 u 仳l ( 3 兰七sn ) 为 g 中的圈，c k 为圈长为n 的圈围长是指一个图中最短的圈长 一般地，起点和终点分别为u 和口的路记为f l u ，u 】一条路p 称为c 一 路，若l v ( c ) ny ( p ) i = 1 而且，p 称为极大的，如果p 不是g 中另外一条 不同于p 的c 一路的子图 顶点铭和移之问的距离是指最短( 缸，口) 路的长，记为d ( 钍，v ) 如果顶点 乱v ( p ) 定义顶点札与圈c 之间的距离，是指顶点与圈上一点u 之间的距 离，记为d ( 乱，c ) ，其中口v ( p ) n v ( c ) 特别地，若“v ( c ) ，则d ( u ，c ) = 0 另外，记点集p y = 缸v ( g c ) i d ( x ，e ) = d ( u ，c ) + 1 ，u x e ( g ) ) 李学良和赵海兴在文献【1 7 】中定义了这样一种指标；a 。( g ) = e 。y ( g ) d ( 让) ”， 其中m 为整数或者形如1 肛的分数，其中k 为非零的整数假设图g 的度 序列为d ( a ) = 【d l ，d 2 ，d i ，d j ，训，并且满足匾屿+ 2 。则 用( 也一1 ，d j + 1 ) 代替池，d j ) ，会得到一个新的图g ，其对应的度序列为 d ( g ) = 【d 1 ，d 2 ，也一1 ，d j + 1 ，引他们发现对于拓扑指标( g ) ， 当m 为形如1 k 的分数，其中自为非零的正整数时，o ，m ( g ) o 。( g 7 ) 于是他们将拓扑指标o t 。( g ) 定义为f ( a ) & 和r 分别表示n 个顶点的星图和路双星图昂，。是由星图筛+ 1 的 除中心外的任一顶点与星图& 的中心重合得到7 1 和7 - 2 分别表示度序列为 d ( t ) = 【3 ，2 ”2 ，1 】和d ( t ) = 【3 2 ，2 ”6 ，1 4 】的树的集合 1 3 几种重要的拓扑指标 拓扑指标是从由分子图所表示的化合物集合到实数集的一种映射许多拓扑 指标与化合物的物理化学特征密切相关分子的拓扑性质是分子在内外因素连 续变化过程中始终保持不变的几何性质，它是分子的固有的性质之一不同的分 子拓扑指标反映了分子的不同性质在这一节，我们重点介绍几种常见的拓扑指 标 4 1 3 几种重要的拓扑指标 1 w i e n e r 指标 美国化学家h o r a l dw i e n e rf 1 】1 于1 9 4 7 年提出了w i e n e r 指标定义如下， w ( g ) = 石1 d ( 乱，口) 一u v e e ( g ) 其中e ( g ) 表示图g 的边集，d ( 仳，钞) 是图中顶点钍和 之间的距离该指标是 目前在化学界公认的第一个分子拓扑指标五十多年来科学家们就是采用该指标 在统计化学，结构化学，有机化学以及药物研究等方面展开研究的w i e n e r 拓 扑指标是建立在分子图上拓扑距离的不变性的基础之上的 2 1 胁n d i 6 指标 r a n d i d 【8 】于1 9 7 5 年提出了这个以他自己的名字命名的指标定义如下： r ( g ) = 阶) d ( 口) 一 u v e e ( g ) 其中e ( g ) 表示图g 的边集，d ( u ) 是顶点u 的度r a n d i d 指标有时也被称为 连通度指标该指标能测量饱和碳氢化合物的碳原子的分支程度，能很好的描述 分子的结构特性和结构活性之间的关系，因此被广泛用于q s p r 理论的研究 2 广义r a n d i d 指标 随着对r a n d i d 指标的研究的深入，1 9 9 8 年b a l l o b 瓠和e r d s sf 3 】提出了广 义r a n d i 6 指标指标定义如下。 冗( g ) = 【d ( u ) d ( t ，) 】。 u v e e ( g ) 其中a 0 ，e ( g ) 表示图g 的边集，d ( u ) 是顶点“的度 4 z a g r e b 指标 最初的z a g r e b 指标是在1 9 7 2 年被提出来的【4 】4 ，包括第一z a g r e b 指标 以 和第二z a g r e b 指标m 2 定义如下t m ( g ) = d ( 乱) 2 ， u v ( a ) ( g ) = d ( “) d ( u ) u v e e ( g ) 5 7 第一章绪论 其中v ( v ) 表示图g 的顶点集，e ( g ) 为边集，d ( 秕) 是顶点“的度这两个指 标是科学家t r i n a j s t i 6 和g u t m a n 在研究分子结构中完整的们电子能量的独立 性时提出来的它们反映了分子骨架的分支程度，并与分子的能量有关这些观 点在文献 4 】中有详细叙述逐渐地，这两个指标作为分子结构的描述方法被越 来越多的人所重视，在一些书籍和评论中被人们所关注【5 ，6 ，2 2 ，7 ，8 】，一些论 文对z a g r e b 指标的数学性质进行了研究【1 2 ，1 3 ，1 4 ，1 5 】 5 改进的z a g r e b 指标 在z a g r e b 指标中，内部的原子和键对z a g r e b 指标的贡献要大于外部的， 而在实际中，由于外部的原子和键关联着更大的分子表面，因此估计它们对研究 分子的物理，化学和生物特性会更有作用于是人们想到将z a g r e b 指标进行改 进，提出了改进的z a g r e b 指标，其形式为s ”姐= l l d ( u ) 1 1 1 d ( u ) l = l l d ( , 0 1 2 ， u e v ( a )“v ( g ) ”m 2 = f 1 d ( “) d ( 口) 】= 【d ( “) d ( ”) 】_ 1 v e e ( a )u v e e ( g ) 近年来，z a g r e b 指标及其改进形式被用在分子复杂性、手征、z e - 异性等 研究上，对q s p r 和q s a r 的研究中也广泛用到了这些指标【9 ，2 3 ，1 0 ，1 1 】 6 第一广义z a g r e b 指标 李学良和郑洁在其文章【1 6 】中提出了第一广义z a g r e b 指标的概念t 岬( g ) = d ( 。) 。 口v ( g ) 其中o l 是一个不等于0 和1 的实数李学良，张胜贵等 1 7 ，1 8 】对树和单圈图的 第一广义z a g r e b 指标的极值做了研究 1 4 第一广义z a g r e b 指标极值问题的研究进展 在文献【1 7 】中，李学良和赵海兴给出了拓扑指标，( g ) 关于树的最小值、次 小值、第三小值和最大值、次大值、第三大值，还有化学树的最小值，次小值， 最大值、次大值的结果结论如下， 6 1 4 第一广义z a g r e b 指标极值问题的研究进展 定理1 1 ( 【l7 】) 设t 是n 个顶点的树若拓扑指标，( t ) 满足，( t ) ，( r ) ， 则 0 ) ，( t ) 达到最大值当且仅当t 垒，( t ) 达到第二大值当且仅当t 望 一3 1 ，( t ) 达到第三大值当且仅当t 竺品- 4 2 ( i i ) ( t ) 达到最小值当且仅当t 鲁r ，( t ) 达到第二小值当且仅当t 垡_ r 1 ， ( t ) 达到第三小值当且仅当t 垒r 2 定理1 2 ( 【17 】) 设丁是n 个顶点的树若拓扑指标( t ) 满足，( t ) ，( r ) ，则 ( i ) ，( t ) 达到最大值当且仅当d ( t ) = 【4 4 ，i + 1 ，l ”1 】 ( i i ) ( t ) 达到第二大值当且仅当i = 0 时，o ( t ) = 【4 ”1 ，3 ，2 ，1 ”1 】；i = 1 时，d ( t ) = 【4 ”1 ，3 2 ，1 ”1 】；i = 2 时，d ( t ) = p ，2 2 ，1 ”2 1 定理1 4 ( f 17 】) 设丁是满足顶点数是礼并且n 一2 = 3 a + i ，i = 0 ，1 ，2 的化学 树，若拓扑指标i ( t ) 满足，( t ) 0 ，则 矸( g ) 达到第三大值当且仅当d ( g ) = h 一2 ，2 3 ，1 ”4 】 若g ( n ) 0 并且方程g ( n ) = 0 的唯一零根n o ( a ) ，则当7 n 伽( d ) 时， d ( g ) = h 一2 ，2 3 ，1 ”4 】当忆= n o ( a ) 并且n o ( a ) 是一个整数时，d ( g ) = h 一3 ，4 ，2 ，l ”3 】或者d ( g ) = 【礼一2 ，2 3 ，1 ”4 j 定理1 8 ( 【1 8 】) 设g 是n 个顶点的单圈图，当d ( 0 ，1 ) 并且n 7 时，有 ( i ) 岬( g ) 达到最大值当且仅当d ( g ) = 【2 ”】； ( i i ) 衅( g ) 达到第二大值当且仅当d ( g ) = 3 ，2 ”2 ，1 】； ( i i i ) j l 卵( g ) 达到第三大值当且仅当d ( g ) = 【3 2 ，2 ”4 ，1 2 】 张惠玲在其毕业论文【1 9 】中还研究了单圈化学图的第一广义z a g r e b 指标的 极值问题结论如下； 定理1 9 ( f 1 9 】) 设g 是n 个顶点的单圈化学图，当o ( - - 0 0 ，0 ) u ( 1 ，+ o o ) 并 且n 7 时，有 ( i ) 聊( g ) 达到最小值当且仅当d ( g ) = 【2 ”】； ( i i ) 聊( g ) 达到第二小值当且仅当d ( g ) = 【3 ，2 ”2 ，1 】； ( i i i ) 卵( g ) 达到第三小值当且仅当d ( g ) = 【3 2 ，2 ”4 ，1 2 】 8 1 4 第一广义z a g r e b 指标极值问题的研究进展 定理1 1 0 ( 【l9 】) 设g 是n 个顶点的单圈化学图，当o ( 0 ，1 ) 并且n 7 时， 有 ( i ) 卵( g ) 达到最大值当且仅当d ( g ) = 【2 ”1 ； ( i i ) 聊( g ) 达到第二大值当且仅当d ( g ) = f 3 ，2 ”2 ，1 】； ( i i i ) 卵( g ) 达到第三大值当且仅当d ( g ) = 【3 2 ，2 ”4 ，1 2 】 定理1 i i ( 【1 9 】) 若g 在n 7 个顶点的单圈化学图中肘f ( g ) 达到最小，当 q ( 0 ，1 ) 时，则g 满足 卵( g ) f ( 仃) 其中 聊，=巨2a-i-na。=：若三n=o=mod3 定理1 1 2 ( 【1 9 】) 若g 在扎7 个顶点的单圈化学图中 卵( g ) 达到最大，当 口( 一o o ，0 ) n ( 1 ，+ o o ) 时，则g 满足m p ( g ) f ( n ) 其中 跏，= 瞄戮若- n = - - = o m 竺o d 3 ； 在文献【2 0 l 中，胡玉梅和李学良等给出了分子图的第一广义z a g r e b 指标的 最大值和最小值结论如下。 定理1 1 3 ( f 2 0 】) 设函是n 个m 条边的分子图，其度序列为【d l ，d 2 ，矗】， 并且满足陋一d ，i 1 ，其中对任意的i ，当口 1 时，o 冠。( 岛) 达到最小值；当0 o t 1 时o 冗。( c o ) 达到最大值并且 。如(c2：2+i2：二(n：-2；)：,三；i：二三；：若茎二m=三n-乏11；兰 第一章绪论 定理1 1 4 ( 2 0 】) 设g o 是竹个m 条边的分子图，并且满足至多有一个2 度顶 点或了度顶点如果n ，m 满足下列条件之一： ( i ) m = n 一1 ； ( i i ) 仇视6 ，其中n = 6 ，仇1 0 ，并且礼= 7 ，m 8 则当a 1 时，o 冠。( g o ) 达到最大值；当0 a 1 时，o 冗。( g o ) 达到最小值并且 嘲长兰 o ( 2 m n ) 3 ，若2 m 一佗三o ( m o d 3 ) g 社 + 2 0 + 4 a ( 2 m n 一1 ) 3 ，：茗i - 2 m n 兰x ( m o d 3 ) ； + 3 8 + 4 。( 2 m n 一2 ) 3 ，若2 m 一九三2 ( r o o d 3 ) 1 5 第二z a g r e b 指标极值的研究进展 郎荣玲在其硕士论文【2 5 】中讨论了树和单圈图的第二z a g r e b 指标的最大值 和最小值，并给出了对应的图的结构文章还给出了任意的简单图的第二z a g r e b 指标达到最小值的必要条件结论如下； 定理l 1 5 ( f 2 5 】) 设? 是冗个顶点的树，则m 2 ( t ) 4 如一2 ) 当且仅当t 与 p n 同构时等号成立 定理1 1 6 ( 2 5 1 ) 设t 是礼个顶点的树，则 幻( t ) 一1 ) 2 当且仅当t 与 星k 1 。一1 同构时等号成立 定理1 1 7 ( 【25 】) 设g 是r t 个顶点n 条边的简单连通图，则 ( 1 ) 尬( g ) 蛾当且仅当g 与g 同构时等号成立 ( 2 ) 如( g ) 礼2 + 3 当且仅当g 与碍同构时等号成立其中l n n 为连接k t ，。一1 的任意两个叶子点所得到的图 定理1 1 8 ( 2 5 t ) 若g 在n 个顶点仇条边的简单连通图中( g ) 最小。则g 满足( g ) 一6 ( g ) s2 第二z a g r e b 指标实际上就是广义r a n d i d 指标的一种特例张惠玲在其毕 业论文【19 】中还给出了单圈图的广义r a n d i d 指标的最小值，并给出了对应的图 的结构结论如下： 1 0 1 1 6 本文的主要结果 定理1 1 9 ( 【1 9 】) 设g 是亿5 个顶点n + 1 条边的简单连通图，则 如( g ) 达 到最小值当且仅当g 掣联其中磁为只有两个不相邻的3 度顶点，其余均为 2 度顶点的双圈图，并且尬( b ：) = 4 佗+ 1 6 其结构如下图， 图1 1 定理1 2 0 ( f 19 】) 若g 是n 个顶点扎条边的简单连通图当口1 时，r o ( c ) n 4 “当且仅当g 是g 时等号成立 1 6 本文的主要结果 图的z a g r e b 指标研究有重要的应用价值，近年来一直是图论科学中一个很 活跃的课题本文的主要任务是研究三类图的z a g r e b 指标 在本文的第二章，我们得到了双圈图的第一广义z a g r e b 指标的最大( 小) 值、次大( 小) 值、第三大( 小) 值，并给出了对应的图的结构结论如下： 定理1 2 1 设g 是一个顶点数礼5 的双圈图，口是一个实数且满足q 1 则 卵( g ) 取得最小值当且仅当g 鲸 定理1 2 2 设g 是一个顶点数乱5 的双圈图，o 是一个实数且满足口 0 或 1 口 2 则 ( i ) m t ( c ) 取得次小值当且仅当g 鲤； ( 既) 蚜( g ) 取得第三小值当且仅当g 鲤 定理1 2 4 设g 是一个顶点数n 5 的双圈图则 ( t ) 聊( g ) 取得次小值当且仅当g 鲧u 鲽； ( 甜) 朋 ( g ) 取得第三小值当且仅当g 鳞o 鳃 】1 第一章绪论 定理1 2 5 设g 是一个顶点数礼25 的双圈图 则m p ( g ) 取得最小值当且仅当g 垒哦 定理1 2 6 设g 是一个顶点数佗5 的双圈图 则对所有足够大的整数n ，则 ( i ) 肘p ( g ) 取得次小值当且仅当g 型磁； ( i i ) 懈( g ) 取得第三小值当且仅当g 掣砩 定理1 2 7 设g 是一个顶点数竹5 的双圈图 则 ( i ) 卵( g ) 取得最大值当且仅当g 鲤； ( i i ) 岬( g ) 取得次大值当且仅当g 鲧； ( i i i ) 岈( g ) 取得第三大值当且仅当g 绒 a 是一个实数且0 n 1 o 是一个实数且0 o 1 口是一个实数且0 o 2 则 ( i ) 衅( g ) 取得次大值当且仅当g 笺碟； ( i i ) 衅( g ) 取得第三大值当且仅当g 笺联若礼= 5 ；g 些嘲若n 6 定理1 3 0 设g 是一个顶点数n 5 的双圈图则 ( i ) m 2 ( g ) 取得次大值当且仅当g 型瑶或磁若n = 5 ；g 皇瑶或磁若 n = 6 ；g 型磁若扎7 ； ( i i ) 聊( g ) 取得第三大值当且仅当g 鲚若n = 5 ；g 垒磷若礼= 6 ； g 垡磁若n 7 定理1 3 1 设g 是一个顶点数扎5 的双圈图，o 是一个实数且1 n 2 设n o 是方程6 0 一5 0 一4 0 + 2 2 0 一1 = 0 在区间肛，铆上的根则 ( i ) 竹( g ) 取得次大值当且仅当g 皇月：若礼= 5 ；g 竺磁若佗= 6 ；当 n = 7 时，g 竺磁若1 a a o ，g 型群或磁若o = 咖，g 型磁若 咖 o 2 ；当扎8 时，g 些磁； ( z i ) 衅( g ) 取得第三大值当且仅当g 竺瑶若n = 5 ，6 ；当佗= 7 时，g 鲁瑶 若1 口 o o ，g 兰硪若d = o l o ，g 皇磁若o l o 口 2 ；当n 8 时， g 羔砩 1 2 1 6 本文的主要结果 定理1 3 2 设g 是一个顶点数佗5 的双圈图，o t 是一个实数且口 0 设 q o 是方程3 护一2 3 。一1 = 0 的负根则对所有足够大的整数n 。 ( i ) 卵( g ) 取得次大值当且仅当g 皇磁； ( i i ) 蜂( g ) 取得第三大值当且仅当g 竺磁若口o t o ，g 竺瑶若口o o t 1 或q 0 时，聊( g ) 取得次小值的必要条件是a ( c ) 一巧( g ) = 2 定理1 3 4 设g 是n 个顶点m 条边的分子图，且m ，n 满足下列条件之一， ( 1 ) m = n 一1 ； ( 2 ) m 芝佗28 ，其中几= 6 时，m 1 0 ，或礼= 7 时，m 8 则当0 o t 1 时，朋p ( g ) 取得次小值的必要条件是n 2 + 珊= 2 定理1 3 5 设g + 是铭个顶点m 条边的分子图，当0 口 1 ，且第一广义z a g r e b 指标取得最大( 次大第三大) ， 最小( 次小、第三小) 值；o l 0 ，且第一广义z a g r e b 指标取得最大，最小( 次 小，第三小) 值；0 o 1 ，且第一广义z a g r e b 指标取得最小、最大( 次大、 第三大) 值；对足够大的n ，0 o l x t = 6 ( g ) 且。t1a z = i v c g ) | ，我们定义图g 的 度序列d ( g ) = 【z ：1 ，z 字，z 纠如果a i = 1 ，我们通常用黾代替茹? 1 对于一个船个顶点的双圈图，如果d ( g ) = f 3 2 ，2 ”2 】，则称g 属于图类 或；如果d ( g ) = 【4 ，2 ”1 】，则称g 属于图类鲧；如果d ( g ) = 【3 3 ，2 ”4 ，1 】， 则称g 属于图类簖；如果d ( g ) = 【4 ，3 ，2 ”3 ，1 】，则称g 属于图类鳞；如果 d ( g ) = 【5 ，2 ”2 ，1 1 ，则称g 属于图类鳞；如果d ( g ) = 【3 4 ，2 ”6 ，1 2 】，则称g 属于图类鳞我们用g ：表示图g 属于图类鳞“= 1 ，2 ，3 ，4 ，5 ，6 ) 很显然，对 一个观个顶点的双圈图g 。如果6 ( g ) 22 ，则有g 鲩u 鳐 与上面类似，我们用砩表示图序列为d ( 砩) = b 一1 ，3 ，2 2 ，1 ”4 】的双圈 图；用瑶表示图序列为d ( h ，2 。) = h 一1 ，2 4 ，1 ”5 】的双圈图；用磁表示图 序列为d ( 蟛3 ) = h 一2 ，4 ，2 2 ，1 ”4 】的双圈图；用磷表示图序列为d ( 磁4 ) = 机一2 ，3 2 ，2 ，1 ”- 4 】的双圈图；用磁表示图序列为d ( 磁) = m 一2 ，3 ，2 3 ，1 ”5 】的 双圈图 顶点数小于5 的双圈图只有一个，对其研究是没有什么意义的因此，我们 所讨论的双圈图的顶点数不小于5 】4 2 2 树和单圈图