（应用数学专业论文）给定匹配数的树的零阶广义randic指标的界.pdf

摘要 为了研究饱和碳氢化合物的碳原子骨架的分支程度，著名化学家m r a n d i c 于1 9 7 5 年提出了一种重要的分子拓扑指标分支指标( b r a n c h i n gi n d e x ) 分支 指标又称为连通性指标( c o n n e c t i v i t yi n d e x ) 或r a n d i c 指标，它与分子的物理 化学性质有着非常紧密的关系。在1 9 7 7 年，k i e r 和k a l l 等发展了分子连接性指数 概念，定义了零阶r a n d i c 指标o r ( z c r o t h - o r d c rr a n d i ci n d e x ) x 1 i 和j z h e n g 又提出了零阶广义r a n d i c 指标( 记为。疋，其中口为任意实数) ，引起了更多数学 家和理论化学家的关注和研究 目前，对零阶广义r a n d i c 指标的研究主要集中在极值问题上，即：在某个图 类中，什么样的图具有最大( 或最小) 的零阶广义r a n d i c 指标 本文研究给定匹配数的树的零阶广义r a n d i c 指标的极值问题，主要结果如 下： 1 当口= - i 时，确定了u 疋1 的最大值及最小值并刻画了达到该极值的图类，该 结果表明：( 1 ) 嚏l 与匹配数之和最小的极图为化学树( 即最大顶点度不 超过4 的树) ；( 2 ) 具有最大值u 疋l 的极图与给定匹配数具有最小 1 心砖口 0 ) 指标的极图是同构的嘲 二 2 当0 口 1 及- 1 口 0 时，分别确定了。咫的最大值及其极图 关键词：树、零阶广义r a n d i c 指标、匹配 a b s t r a c t t h i sp a p e rs t u d i e st h ee x t r e m a lp r o b l e mr e l a t e dt oz e r o t h - o r d e rr a n d i ci n d e xo f t r e e sw i t hag i v e ns i z eo ft h em a x i l n u mm a t c h i n g s t h em a i nr e s u l t sa r e 鹋f o l l o w s ： ( 1 ) w h e n 口= - 1 ，t h em a x i m m nv a l u ea n dm i n i m u mv a l u eo fo 疋a r cd e t e r m i n e d a n d , f u l 恤l n o r c ，t h ec o r r e s p o n d i n ge x t r e m a l 廿e e sa r ca l s oc h a r a c t e f i z e c l ( 2 ) w h e n0 口 1 ，t h em a x i m u l nv a l u eo fo 心a n d t h ec o r r e s p o n d i n ge x t r e m a l t r e e sa r ed e t e r m i n e d ； ( 3 ) w h e n 一1 口 0 ，t h em i n i m u m v a l u eo fo 如a n dt h ec o r r e s p o n d i n ge x t r e m a l k e yw o r d s ：t r e e ；z e r o t h - o r d e rg e n e r a l r a n d i ci n d e x ；m a t c h i n g 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在 论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。 本人依法享有和承担由此论文产生的权利和责任。 声明人( 签名) ：寺托衫陟 d l 唧年尹月分日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留 并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 本学位论文属于 1 保密() ，在年解密后适用本授权书。 2 不保密( ) ( 请在以上相应括号内打。一) 作者签名：寺掺胯 日期：加7 年夕月z 日 翩懿橱蹴醐。砷年夕川朋 给定匹配教的树的零阶广义r a n d i c 指标的界 1 1 研究背景及选题意义 第一章引言 图论是一门有趣而且应用性很强的学科，从历史上看，它的每一次重要的进 步都离不开对实际问题的解答尝试，如欧拉和哥尼斯堡七桥问题、凯莱和化学中 同分异构体的计数问题以及基尔霍夫在电网络上所做的工作等等。现代图论随着 生产管理、军事、交通运输、计算机和通讯网络等领域中许多离散问题的出现而 得到了长足的发展，产生了很多分支。其中组合化学是比较活跃的一个分支，它 在药理学( 药物设计) 、医药化学、结构化学、有机化学以及环境科学等方面有 着非常重要的应用。 众所周知，分子是由原子组成的，任何两个原子之间可以形成化学键，也 可以不成键，这是可以分辨的。尽管分子的几何参数，如分子之间的距离、键角 等是可以测量的，但是由于存在着各种分子内的运动，如分子的振动、内转动等， 从而使得分子中原子的位置是不固定的。另外，分子的几何性质也会随着周围环 境的影响，比如温度，压力等面发生改变。由分子内部的运动和各种外部的影响 所引起的分子几何性质的改变可以看成是连续的形变，或拓扑变形，因为没有键 的破坏和形成。尽管在这种形变的过程中分子的若干几何性质发生了改变，但分 子中原子之间相互关联的性质保持不变，而分子中原子相互连通的全部信息确定 了分子的拓扑性质。 在数学化学中，我们用图来描述分子的拓扑结构。我们用顶点代表分子中的 原子，用边代表原子之间形成的化学键，这种图被称为分子图。在考虑饱和以及 共轭的碳氢化合物时，顶点只代表碳原子而略去氢原子，边只代表碳碳原子之 间的化学键，这种图叫做分子的骨架图，也称为隐氢图，如图1 所示。分子图不 仅是分子拓扑结构的直观表达形式，而且表达了分子的拓扑性质，如果两个分子 中的原子之间具有相同的连通性质，或者说，它们具有相同的分子图，那么就可 以说这两个分子的拓扑性质是相同。 人 反 一 一c千月纠 一 r 效 r hli卜i。h hiiri，h 卜 给定匹配数的树的零阶广义r a n d i c 指标的界 2 图l ：分子和分子的骨架图 一般来说，我们把在分子图或其矩阵表示中不依赖于顶点的标号方式而改变 的量叫做分子图的拓扑不变量。例如，分子图的不变量可以是顶点的数日，边的 数目，等长度路径的数目，邻接矩阵的顶点度，距离矩阵的距离度。另外，分子 图的特征多项式以及图谱都是分子图的不变量。 虽然分子的拓扑性质可以用分子图来表达，但是从本质上来看，分子图是个 非数值的数学对象。而在实际的应用中，分子的各种可以测量的物理化学性质通 常都是用数值来表达的，因此为了把分子的拓扑性质与分子的各种可以测量的物 理化学性质联系起来，必须首先把从分子图中所获得的信息转变为一种能用数值 表达的量。经研究发现，分子图的各种不变量就是能够起到这种作用的量。也就 是说，分子图的不变量不但可以定量地表达分子的结构，而且还可以用来表示相 关分子的结构与性能之间的关系，通常把具有这种作用的分子图的不变量叫做分 子拓扑指标。分子拓扑指标在化学中的应用已经成为当前信息化学的重要内容。 当今组合化学的一个中心问题就是寻找具有某种物理或化学性质的分子。因 为分子的拓扑指标可以统计地反映分子的物理和化学性质，因此为了得到所期望 的分子，首先就要得到这种分子的拓扑指标，然后利用计算机搜索，建立具有这 种指标值的分子图数据库，最后在库中选择理想并且能够合成的结构去合成它 们。这一过程的关键是建立具有某拓扑指标值的分子图数据库，而建立这个数据 库所要解决的问题就是求给定分子图的拓扑指标的逆问题，即求出相应的分子 图，使得该分子图的拓扑指标值等于预先设定的某个具体值或者在预先设定的某 个范围内。该问题的深入研究对有目的合成一些分子或药物具有非常重要的理论 价值和应用背景。 极值问题是组合化学中另一个有趣而且有应用背景的研究分支，它本身也是 极值图论的一个典型的应用。什么样的分子结构具有大的拓扑指标值，什么样的 分子结构具有小的拓扑指标值，以及由此衍生而来的某类分子结构的拓扑指标值 界( 上界或下界) 的确定，都可以服务业帮助建立分子图数据库。 给定匹配数的树的零阶广义p a m d i c 指标的界 1 2 几种重要的分子拓扑指标 3 自美国化学家h w i e n e 9 1 】在1 9 4 7 年提出目前在化学界公认的第一个分子拓 扑指m - - w i e n e r 指标以来，已报道约4 0 0 个分子拓扑指标，不同的分子拓扑指标 反映该分子的不同性能，它们在物质的定量- 性质活性相关性( q s p r q s a r ) 的 研究中都发挥了重要的作用。其中最著名的就是w i e n e r 指标、h o s o y a 指标和 r a n d i c 指标。 w i e n e r 指标 w i e n e r 指标最初定义为路径和【1 1 ，即在一个分子中所有原子之间的键的个 数之和。后来在1 9 7 1 年，日本化学家h o s o y a 2 】给出了基于距离矩阵d 的新定 义：距离矩阵d 的上三角或下三角的元素值之和，即 形= 矿( g ) = 寺岛 ( 1 1 ) 其中岛为距离矩阵的元素。w i e n e r 指标是建立在分子图拓扑距离的不变性的 基础之上的。w i e n e r 指标提出后在统计化学、结构化学、有机化学以及药物研 究等方面都得到了广泛的应用和研究。 h o s o y a 指标 继h w i e n e r 的开创性工作之后，拓扑指标发展史上又一重要指标是由 h o s o y a m 于1 9 7 1 年提出的h o s o y a 指标，它是第一个在分子简单回归问题上发 现的不变量，它被定义为： 一。g ，= 朋， m 2 ， 其中，z 是图g 的顶点数，匕j 为不超过兰的最大整数，p ( g ，七) 是在图g 中选取 k 条边，使两两都不相邻的选取方法的数目，称为k 一匹配数。规定p ( g o 产l ， p ( o , 1 产图g 的边数。 这种拓扑指标最重要的性质是它与分子图的特征多项式有关。h o s o y a 指标 不仅在化学上，而且在物理学和数学上都得到了广泛的应用和研究。 给定匹配数的树的零阶广义r a n d i c 指标的界 r , 锄d i c 指标 为了研究饱和碳氢化合物的碳原子骨架的分支程度，m r a n d i c 3 于1 9 7 5 年 提出了一个拓扑不变量) c ，它被定义为图唧，e ) 中所有相邻顶点的度的乘 积开方再求逆之和，即 l z = ) c ( g ) = ( d g ( u ) d g ( v ) ) q ( 1 3 ) 胀e ( g ) 其中如 ) 为顶点“的度。m r a n d i c 称x 为分支指标( b 啪c gi n d e x ) ，同时 指出该指标与烷烃分子的很多物理和化学性质者都显示出了很强的相关性，如沸 点、k o v a t s 指标、生成焓、a n t o i n e 汽压方程的参变量、表面积以及水溶解度 等等。r a n d i c 指标具有很低的退化度，能很好地描述分子的结构特性和结构活 性之间的关系，被广泛应用于q s p r q s a r 理论的研究，已被大多数的化学家 所接受，是一个非常成功的拓扑指标。接着在1 9 9 8 年，b b o l l o b a s 和e e r d o s t 4 1 将r a n d i c 指标中的一i i 推广到任意一个非零实数口，提出了广义r a n d i c 指标， 即 吃= 心( g ) = ( 如( 甜) 如( 动口 ( 1 4 ) 柳( g ) 在1 9 7 7 年，k i e r 和k a l l t 5 1 等发展了分子连接性指数概念，定义了零阶r a n d i c 指标，即 l o r = o r ( g ) = ( 如( 1 ，) ) 1 、 7 一 、 u 、 ，7 垤y ( g ) 后来，l ia n dz h e n g t 6 1 将零阶r a n d i c 指标中的一百1 推广到任意一个非零实数口， 提出了一个图的零阶广义r a n d i c 指标，即 。如= o 如( g ) = ( 如( v ) ) 口 垤矿( g ) 给定匹配数的树的零阶广义r a n d i c 指标的界 1 3 术语和记号 5 本文所研究的图都是有限的无圈连通图即树。v ( g ) ，e ( g ) 分别表示图g 的顶点集和边集，g 的顶点数即阶数用n 表示。夕是e ( g ) 的子集，称是g 的 一个匹配，如果中任意两条边无公共端点。如果的某条边与顶点v 关联， 则称饱和顶点v ，并且称v 是饱和的。如果g 的每个顶点均为饱和的， 则称为g 的一个完善匹配。 对于g 中的一个顶点u ，我们用n d u ) 表示由g 中所有与u 相邻的顶点组 成的集合，用d g ( u ) 表示顶点u 的度。如果顶点u 和v 相邻，那么连接这两个顶 点的边我们记为u v 。我们用g u 表示从g 中删去顶点u 后所得到的点导出子 图，用g - u v 表示从g 中删去边u v 后所得到的边导出子图。s n 和p n 分别表示 n 个顶点的星图和路。通常用t 来表示一棵树，即无圈的连通图。t 中度为l 的点称为t 的悬挂点，连有悬挂点的边称为悬挂边。对任意一个实数x ，lxl 是 指不小于x 的最小整数，而lxl 则是指不大于x 的最大整数。其他未加予说明 的术语和符号均引自文献 7 1 。 1 4 零阶广义r a n d i e 指标极值问题的研究进展及文本结果 有关图的零阶广义r a n d i c 指标，我们最感兴趣的是刻画这些指标达到极值 时的极值图或图类。这些问题的解决有很强的应用背景，所以受到越来越多的化 学家、数学家以及相关科学家们的关注并致力研究，得到了大量的结果( 见x l i 和i g u t m a n 的专著【唧。 k i e r 和k a l l 5 】等发展了分子连接性指数概念，定义了零阶r a n d i c 指标， 即 l o 犬= o r ( g ) = ( 如( y ”1 v e 矿( g ) l ia n d z h e n g 同将零阶r a n d i c 指标中的一j 1 推广到任意一个非零实数口， 提出了了一个图的广义零阶r a n d i c 指标，即 给定匹配数的树的零阶广义r a n d i c 指标的界 6 o 如= o 如( g ) = ( 如o ) 厂 v e v ( g ) l p a v l o v i c 网确定了具有最大零阶r a l l d i c 指标的图类。rl a n g 和x l i 0 0 l 等也刻划了具有最大和最小m l ( g ) 指标的分子图类( n , m ) - g r a p h s ，其中m l ( g ) 指标是z 砌指标之一( 定义m 1 暑u 心f o r 口= + 2 ) 。 l i 和z h a o t l l 垓0 划了树图中分别具有第一、第二、第三大和小的零阶广义 r a n d i c 指标，其中口值分别取七、一k 、i 1 、一i 1 ，这里七为不小于2 的整数。 h z h a n g g l s z h a n g 1 2 】证明了无圈图中分别具有第一、第二、第三大和小 的零阶广义r a n d i c 指标。 y h u 和x l i 等【1 3 1 确定了( n ，1 1 1 ) g r a p h s 中具有最大和最小零阶广义r 吼d i c 指标的化学图( 即顶点度不超过4 的图) 。 l i 和z h a o t l 4 1 也证明了具有第一、第二大和小零阶广x r a n d i c 指标的化学树 ( 即顶点度不超过4 的树) ，其中口 l 。 本文研究一类树图在给定匹配数零阶广义r a n d i c 指标的极值问题。当 - 1 口 l , a 0 时，我们证明了一类树图具有零阶广义r a n d i c 指标的最小值和 最大值。同时，注意到两个有趣的结果：当口= - 1 时，零阶广义r a n d i c 指标与 匹配数之和最小值的极图类为化学树( 即最大顶点度不超过4 的树) 以及得到了 给定匹配数具有最大。疋l 指标的极图与给定匹配数具有最小心砖口 o ) 指 标的极图是同构的嘲。 给定匹配数的树的零阶广义r a n d i c 指标的界 第二章给定匹配数零阶广义r a n d i c 指标的界 7 本苹在l ia n dz h e n g 【6 】等研究图的零髟 厂义r a n d i c 指标基础上，针对树图 在给定匹配数研究零阶广义r a n d i c 指标的极值问题。当一l 口 1 , a 0 时，我 们确定了一类树图具有零阶广义r a n d i c 指标的最小值和最大值。同时，注意到 两个有趣的结果：当口= - 1 时，零阶广义r a n d i c 指标与匹配数之和最小值的极 图类为化学树( 即最大顶点度不超过4 的树) 以及给定匹配数具有最大。疋l 指 标的一类树图与给定匹配数具有最小如口 o ) 指标的一类树图是同构的， 这一类树图具有很强的物理和化学背景。本章分两部分来证明给定匹配数一类树 图具有最大和最小零阶广义r a n d i c 指标。 - 2 1 一类具有最大和最小。疋i 指标的树图 首先我们需要介绍一些概念及标记。 用e 表示匹配数为顶点数为，z 的树的集合( 聆2 f 1 ) 。 设r 露为一树集且满足： 5 ：墨 r 一， i i ：对任意树t r 疗，夕，丁u 墨 r 厅，这里我们把星图墨，岛的一个 悬点与树t r 刀，卢的一个悬点粘在一起得到的树记为丁u 墨 ( i = 2 ，3 ，) 。设r 0 = 乃，r 一且d ( 、) = 七( 后2 ) ， ( i = l ，2 ，) ) ，这里设每个星图墨，毛的中心点为、 引理l ：对任意树乙，r 开，声0 2 ) ，则 k ( 蹦川) + 石2 一警+ 吾 ( 2 - 1 1 ) ( 2 1 1 ) 式中等式成立当且仅当乙r 易且后= 等 给定匹配数的树的零阶广义m 嘣指标的界 证明：设p ( 瓦) i = 拧，为树瓦，户的匹配数。通过简单计算，我们得到： 刀= i y ( ) i = 兰( d ( 飞) - 1 ) + + l 8 = d ( 飞) + l 即兰d ( 飞) = 刀一l ，于是我们有 憧。( ) = 2 + 喜( d ( k ) 一2 ) + t f l - 1 + 喜南 憧。( ) = 2 + ( d ( k ) 一2 ) + 下+ 熹 娟q 嘻南一警专 由柯西一许瓦兹不等式： ( 2 1 2 ) 8 = 善生1 ， 等式成立当且仅当d ( 飞) = 七，这 刀一 、吩7 里七为不小于2 的整那1 ，2 ，鼽再由2 1 2 式可得叫飞) = 七= 等 因此，。足。( 瓦) 加一1 ) + i p i 2 一警+ 吾 等式成立当且仅当乙，芦r ：， 且扣等引理1 证毕 z j l 理2 ：设o x n - 1 ，m ) = 玉錾一兰+ ! ，则 刀一x i ，l lx 函数f ( x ) 。，等式成立当且仅当x = 了n - 1 证明：当o o 因此，引理3 得证。 我们定义殇为顶点数为刀( 2 ) 的树，它是由一1 个悬点连接到星图 墨晰l 的一1 + 非e e 心点显然t 丹o 是一棵匹配数为顶点数为，z 的树且 t ：，是顶点数为2 的完美匹配树，见图1 。 p lt t ， 通过简单计算，我们得到 图1 。 p lt t ： 给定匹配数的树的零阶广义r m d i c 指标的界 乜( 殇向一譬+ 南一丢 定理2 ：对任意乙e 加2 p ) ，则有 k ( m 刀一鲁+ 而1 一三等式触当且仅当 乙，t 二o ( n = 2 f 1 ) 或乙“t 刀o 如 2 ) 证明：当乙- t o 夕或乙：r 刀o 时，定理2 显然成立。现在设任意 e ，( 刀2 历，当= 1 时，乙，口为星图，定理2 显然成立。当2 时，设树乙，中最大顶点度为噍。， ) = p 2 。在树乙中存在一顶点 v 乙，且满足： ：，( 1 ，) = 乃啊，_ ，_ 。，乍。) ，这里 噍，( v f ) 2 ( f = 1 ，2 ，歹) 且噍。，( ) = = 噍，( 一，) = 1 o i ：在，( 匕) 、 田中的每个顶点度为1 ( t = l ，2 ，) 。这里 2 g p ，1 i | f ( 曰一1 ) 。 图z 我们对树瓦，做以下变换厂：选择度最大的顶点甜和满足上述条件的顶点 1 ，删去边q ，再用边q 连接顶点材和h ，得到树丁疗，( t = 1 ，2 ，) ，这 t t n 的最大匹配数仍为，由引理3 知，。足l ( 乙，) o 足l ( r 以，) 2 f l ，且瑶兰e c a s e2 ：设_ 勃 ) 中无悬点若在勃 ) 中所有顶点度均等于2 ，这时只要 移树夏，中的一条悬边，连接到乇中的顶点甜，得到树殇，矗 ) 中只有 两个1 度点，这时树易最大匹配数仍为且殇兰e ( n = 2 f l + 1 ) 。若在 毛 ) 中存在有顶点度大于等于3 ，设“。声 ) 且d ) 3 ，这时再做 g 变换，在顶点“上依次移去d 。) 一1 条悬边，连接到夏，中的顶点铭，这时 保持不变，这样d 似) 中有1 度点，可归结到c a s e1 注意到：在上述整个变换过程中最大匹配数保持不变，且由引理3 知，在 整个厂和g 变换过程中顶点度倒数之和不断增大，直到乙兰殇，卢( n = 2 f 1 ) 或乙“z 刀o ( n 2 f 1 ) ，因此，定理2 证毕。 给定匹配数的树的零阶广义r 胁d i c 指标的界 2 2 一类具有最大和最小。心指标的树图( 一l 口 l ，口o ) 引理4 ：设厂( x ) = x a g l 广- ( 2 口- 1 ) ，这里x 为不小于2 的整数，则 i ： 厂( x ) 0 如果0 口 1 i i ：f o ) 0 如果- 1 口 0 证明：显然，如果x = 2 ，则八x ) = 0 。现在我们考虑x 3 ，运用拉格朗日中值 定理，我们可得存在一点磊( x - 1 ，工) ，使得，- ( x 1 ) 口= 簖- 1 ，以及存在 一点色( 1 ，2 ) ，使得( 2 口一1 ) = 蠼- 1 。因此 厂( x ) = x a 一 一1 ) 口- ( 2 口- 1 ) = 口( 畀q 一嚣- 1 ) 。注意到当x 3 时， 0 色 点。再由拉格朗日中值定理，存在一点孝( 磊，缶) ，使得 口( 笄- 1 一嚣- 1 ) = 口( 口一1 ) 尸- 2 ( 磊一彘) 。显然，孝口- 2 和( 磊一磊) 是正数。因此， 如果o 口 1 ，则厂o ) 0 ；如果一1 口 0 。引理4 得证 咖5 町= 号铲一譬m 灿 州) 且刀2 p ，2 ，则 i ：厂( x ) 0 如果0 口 1 i i f ( x ) 0 如果- i 口 0 硼：首先我l f 注蔚，如果舻等棚炒g ) 0 0 现在我们分下面两种情 况考虑： c a s e 1 当o x 可n - 1 则有o 筇- x r t - x - 1 函数m ) 一阶导数百o f ( x ) = - a ( 弋f l - 1 两) ( n - 厂x - 一1 ) a - + 口x 口- l 渤 i 一l 厂 口f ( x 一x ) 口。一( ，l x 一1 ) 口- 1 1 ( 一l 尸- 1 给定匹配数的树的零阶广义 h i l d i c 指标的界 显然，( 夕一l 尸叫是正数，如果口 1 ，( 够一x 广一一伽一x - - 1 ) ”1 也是正数 这样，对o x 可n - 1 ，当o 口 l ，函数f ( x ) 是单调递增的；当 - l a o , 函数f ( x ) 是单调递枞眦对等，当 0 口 1 ，函数厂( x ) o ；当一l 口 0 ，函数厂 ) o 。 c a s e2 当可n - 1 x 刀一l ，则。 刀一x 一1 筇一x ，函数f ( x ) 的 一阶导数掣=-a(fl矿-1)(n-x-1)=q+群以 = 丛望二三芝二生二苎二! 芝! ( 夕一1 ) 口- 显然，( 一1 ) 口。是正数，当口 1 时，( x , o x ) 口一一伽一x 1 ) 口一1 是负数。这 样，当可n - 1 x 刀一l ，如果o a r l , i 霾数似) 为单调递减的；如果 一1 口 o ，函数厂( x ) 为单调递增的。 因此，当等x 刀一l ，如果 0 口 1 ，函数厂( 曲0 ；当一l 口 0 ，函数厂( 功o 。故综合上述两 种情况，引理5 得证。 定义k ( 丁) = d 尸，对任意乙r 一，设l y ( 瓦) l = 刀，为最 大匹配数。通过简单计算，我们有 ，z = i y ( 乙，) l ：兰( d ( 飞) _ 1 ) + + 1 口 = d ( 飞) + 1 即杰d ( 飞) = 刀一1 ，于是我们可得 ( 2 2 1 ) 给定匹配数的树的零阶广义r a n d i c 指标的晃 。r o ( r ，) = 2 + 兰( d ( 飞) 一2 ) + ( 一1 ) 2 口+ 至d ( 飞) 口 = ( n - 1 ) + ( 一1 x 2 口_ 2 ) + 兰d ( 飞尸 现在我们先计算羔d ( 飞) 口的值。 引理6 ：对任意乙ef 厅，卢，则 i ：喜弧邝了p ( n - o 球当o a l 像2 2 ) i i ：喜弧) 口1 f l ( n - - 1 ) 当水口 。 ( 2 2 3 ) 1 5 在( 2 2 2 ) 和( 2 2 3 ) 式中等式成立当且仅吸且霓= 可n - i 证明：先假设0 口 1 ，置厂= 1 - a ，p = 1 a 和q = i y ，使得 1 p + l q = 1 。由h o l d e ri n e q u a l i t y ，我们得到 d ( 飞) 口l ，( d ( 飞尸) i ( 1 ) i = ( d ( 、) ) - 1 ( 1 ) ， 88 l 8 1 88 = ( n - 1 吨= 等 等号成立当且仅当( d ( 飞) 口) p = m 1 9 ，即d ( 飞) = m ，这里m 为常数且 ( 扛1 2 ，鼽自等式( 2 2 1 ) ，我f f 隋也) 州= 等。这样，在( 2 2 2 ) 式中，等号成立当且仅致且后= 可n - 1 不等式( 2 2 3 ) 是( 2 2 2 ) 的一个间接结果。事实上，当口0 ，柯西一许 瓦兹不笺吉建们右 给定匹配数的树的零阶广义p - d u i d i c 指标的界 pil口ipi i i = ( d ( 飞尸) - ( d ( 飞) 一口) j ( d 氓广) _ ( d ( 飞) 一口) i 因此，当一1 口 0 ，由不等式( 2 2 2 ) 则有 和嘉孕2 = 譬 等号成挡且仅当且七= 了n - 1 故棚证靴 定理3 设任意乙c 仍2 ) ，则 。碱班”1 ) + ( 删2 口- 2 ) + 竽揪删 ( 2 2 4 ) u 孙柚堋- 1 ) - 2 ) + 竽兰i - l a o ( 2 2 5 ) 在( 2 2 4 ) 或( 2 2 5 ) 中等式成立当且仅当r 易且七= 等 1 6 证明：对任意乙e ，r o m p = 1m l j t , , 是星图，定理3 显然成立。现在我 n + m - mp 2 ，且对用归纳证明。因为乙e 为树图，于是存在顶点 u y ( 乙，) ，使得n ( u ) = u o ，“l ，u k - 1 ) ( 后2 ) ，d ( u o ) 2 且 d ( ) = 1 ( 1 i k - 1 ) 。先设o 口 1 r d = d ( u o ) 易知，我们选择顶 点扰满足：乙，一u u 0 = ，伊lu 乙，由归纳假设，我们有 。疋( 乙，夕) = o r ( ，户1 ) + 七口+ ( 七一1 ) + d 口+ ( d 1 ) 口 ( n - k - 1 ) + ( 一2 ) ( 2 口一2 ) + 量壁二铲 + 后口+ ( 七- 1 ) + d 口- ( d - 1 ) 口 给定匹配数的树的零阶广义l h l l d i c 指标的界 啪- 1 ) + 胪- 2 ) + 譬一竽 1 7 + ( f l - _ 1 ) 巧( f n - x k - 1 一) 口+ k 口一( 2 口一1 ) + d 口一( d 1 ) 口 一1 ) 、7、7 跏1 ) + ( 纠胆- 2 ) + 竽 由引理4 、引理5 和引理6 知，当0 口 1 ， 。见( u 如- 1 ) + ( 纠) ( 2 口_ 2 ) + 等芒等式成立当且仅当 。七川r 柑胂，d ( u o ) = 2 且七= 等，即当且仅当 r 且后= 可n - 1 用上面类似证明方法，由引理4 、引理5 和引理6 ，当一l 口 2 f 1 ) ，则 + 。足。( ) 百1 5 n + 话9 等式成立当且仅当 且后= 可n - 1 = 4 证明：设瓦e ，户仰2 f 1 ) ，由定理1 ， 。州u 孙叫+ 鲁一警专 这样p + 0 蹦u 孙- 1 ) + 石p 2 一鲁专 f l ( n 4 1 ) 2 1 5 刀9 ( n - 1 ) 161 6 1 5 n9 1 61 6 毗，等式成挡且仅圾且后= 可n - 1 = 4 呱， 对任意给定，我们注意是一化学树集，因此r 满足 i ：s i 4 r ：， i i ：对任意t r ：，声，r u s 1 3 + z r 4 户，这里露( 甜) = 1 ， 呔，( 1 ，) = 3 且y ( 丁) 厂、矿( - s 3 ) = o 。 给定匹配数的树的零阶广义r , m d i e 指标的界 1 9 2 ： 本文得到了给定匹配数具有最大。足l 指标的一类树图与给定匹配数具有最 小心哇口 。) 指标的一类树图是同构的嘲，这类树图均为f i g u r e 1 所示。 参考文献 参考文献 【1 】h w i e n e r , s t r u c t u r a ld e t e r m i n a t i o no fp a r a f f mb o i l i l l gp o i n t s j ，j a m c h e m s o c 6 9 ( 1 ) ( 1 9 4 7 ) 1 7 2 0 【2 】h h o s o y a , an e w l yp r o p o s e dq u a n t i t yc h a r a c t e r i z i n gt o p o l o g i c a ln a t u r o o f s t r u c t u r a li s o m e r so fs a t u r a t e dh y d r o c a r b o n s j ，b u l l c h e m s o c j p n 4 4 ( 1 9 7 1 ) 2 3 3 2 - 2 3 3 9 【3 】m r a n d i c ，o nc h a r a c t e r i z a t i o no f m o l e c u l a rb r a n c h i n g j ，j a m e r c h e m s o c 9 7 ( 1 9 7 5 ) 6 6 0 9 6 6 15 【4 】b b o l l o b a sa n dee r d o s ，g r a p h sw i t he x t r e m a lw e i g h t s j ，a mc o m b i n 5 0 ( 19 9 8 ) 2 2 5 - 2 3 3 【5 】l b k i e r , l h h a l l ，t h en a t u 佗o fs t r u c t u r e a c t i v i t yr e l a t i o n s h i p sa n dt h e i r r e l a t i o nt om o l e c u l a rc o n n e c t i v i t y , e u r o p j m e d c h e m 1 2 ( 1 9 7 7 ) 3 0 7 31 2 【6 】) ( l i ，j z h e n g , au n i f i e da p p r o a c ht ot h ee x t r e m a lt r e e sf o rd i f f e r e n ti n d i c e s ， m a t c h c o m m u n m a t h c o m p u t c h c m 5 4 ( 2 0 0 5 ) 1 9 5 2 0 8 【7 】j a b o n d ya n du s m u r t y , g r a p ht h e o r yw i t ha p p l i c a t i o n s m ，m a c m i l l a n , l o n d o n , 19 7 6 【8 】) 【l ia n di g u t m a a , m a t h e m a t i c a la s p e c t so fr a n d i c - t y p em o l e c u l a rs t t m e a n e d e s c r i p t o r s ，m a t h e m a t i c a lc h e m i s t r ym o n o g r a p h sn o im ，k r a g u j e v a c ，2 0 0 6 【9 】l p a v l o v i c ，m a x i m a lv a l u eo ft h ez e r o t h - o r d e rr a n d i ci n d e x , d i s c r a p p l m a t h 1 2 7 ( 2 0 0 3 ) 6 1 5 6 2 6 【l o 】1 ll a n g , x l i ，s z h a n g , i n v e r s ep r o b l e mf o rz a g r e bi n d e xo f m o l e c u l a rg r a p h s , a p p l m a t h 】c h i n e s eu n i v a i8 ( 2 0 0 3 ) 4 8 7 - 4 9 3 ( i nc h i n e s e ) 【1 l 】xl i ，h z h a o ，t r e e s 晰也t h ef i r s tt h r e es m a l l e s ta n dl a r g e s tg e n e r a l i z e dt o p l o - g i c a li n d e i c e s ，m a t c hc o m m u n m a t h c o m p u t c h e m 5 0 ( 2 0 0 4 ) 5 7 6 2 【12 】h z h a n g ，s z h a n g , u n i c y c l i cg r a p h sw i t ht h ef i r s tt h r e es m a l l e s ta n dl a r g e s tf i r s t g e n e r a lz a g r e bi n d e x ，m a t c hc o m m u n m a t h c o m p u t c h e m 5 5 ( 2 0 0 6 ) 4 2 7 4 3 8 13 】y h u , x l i ，y s h i ，t x 屿i g u t m a n , o nm o l e c u l a rg r a p h s 、) i r i ms m a l l e s ta n d g r e a t e s tz e r o t h - o r d e rg e n e r a lr a m i ei n d e x ，m a t c hc o m m u n m a t h c o m p u t c h e m 5 4 ( 2 0 0 5 ) 4 2 5 - 4 3 4 参考文献 【1 4 】x l i ，h z h a o ，t r e e sw i t ht h ef i r s tt h r e es m a l l e s ta n dl a r g e s tg e n e r a l i z e dt o p o i = o g i c a li n d i c e s ，m a r c hc o m m u n m a t h c o m p u t c h e m 5 0 ( 2 0 0 4 ) 5 7 6 2 15 】m a o u c h i c h ea n dp h a m e n , o nac o n j e c t u r ea b o u tr a n d i ci n d e x j ，d i s c r e t e m a t h ，t oa p p e a r 【1 6 】p a nu p l 3 l e rb o u n do nt h er a n d i 7 ci n d e xo f t r e e s j ，j m a t h s t u d y ( i nc h - i n e s e ) 3 1 ( 1 9 9 8 ) 2 2 5 - 2 3 0 【1 7 yh u , x l