（应用数学专业论文）具有最小广义randic指标的共轭树.pdf

摘要 为了研究饱和碳氢化合物的碳原子骨架的分支程度，著名化学家m r a n d i d 于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 d 指 标，它与分子的物理化学性质有着非常紧密的关系接着在1 9 9 8 年， b b o u o b 矗s 和p e r d s s 提出了广义r a n d i d 指标的概念，引起了更多数学家和 理论化学家的关注和重视 目前，对广义r a n d i d 指标的研究主要集中在极值问题上，即：在某个 图类中，什么样的图具有最大( 或最小) 的广义r a n d i d 指标? 本文研究共轭树( 即具有完美匹配的树) 的广义r a n d i d 指标的极值问 题当q - 1 时，我们确定了共轭树的广义r a n d i d 指标的最小值以及达 到最小值的极值图( 类) 有趣的是，这些极值图( 类) 都是共轭的化学树， 即最大度不超过3 且具有完美匹配的树这一类树与无环烯烃分子的碳原子 骨架是一致的，因而具有很强的物理和化学背景 关键词：共轭树，最小广义r a n d i d 指标 a b s tr a c t i ns t u d y i n gt h ee = 吼e n to fb r a n c h i n go ft h ec a r b o n a t o ms k e l e t o no fs a t - u r a t e dh y d r o c a r b o n s ，m r a n d i 6 ，af a m o u sc h e m i s t ，p r o p o s e da ni m p o r t a n t m o l e c u l a rt o p o l o g i c a li n d e x - - b r a n c h i n gi n d e xi n1 9 7 5 b r a n c h i n gi n d e xi s a l s oc a l l e dt h ec o n n e c t i v i t yi n d e xo rr a n d i 6i n d e x a sd e m o n s t r a t e db ym r a n d i 6h i m s e l f , t h i si n d e xi sw e l lc o r r e l a t e dw i t hav a r i e t yo fp h y r s i c o - c h e m i c a l p r o p e r t i e so fa l c a n e s l a t e ri n1 9 9 8 ，t h i si n d e xw a se x t e n d e db yb b o l l o b 五s a n dp e r d s st ob eam o r eg e n e r a lf o r m - - g e n e r a lr a n d i 6i n d e x ，w h i c hi s e x t e n s i v e l ys t u d i e db yb o t hm a t h e m a t i c i a n sa n dt h e o r e t i c a lc h e m i s t s s of a r ，r e s e a r c h e so ng e n e r a lr a n d i 6i n d e xm a i n l yf o c u so ni t se x t r e m a l p r o b l e m s ，e g ，w h i c hg r a p hh a st h el a r g e s to rs m a l l e s tg e n e r a lr a n d i 6i n d e x ( i nag i v e nc l a s so fg r a p h s ) ? i nt h i sp a p e r ，w es t u d yt h ee x t r e m a lp r o b l e m so fg e n e r a lr a n d i di n d e x f o rc o n j u g a t e dt r e e s f o ra n yr e a ln u m b e rq - 1 ，t h em i n i m u mg e n e r a l r a n d i 6i n d e xo v e ra l lt h ec o n j u g a t e dt r e e si sc o m p l e t e l yd e t e r m i n e da n dt h e c o r r e s p o n d i n ge x t r e m a lc o n j u g a t e dt r e e ( s ) i s ( a r e ) c h a r a c t e r i z e d m o v e o v e r ， i t i si n t e r e s t i n gt on o t et h a tt h e s et r e e sa r ea l s oe x t r e m a lo v e ra l lt h ec o n j u g a t e dc h e m i c a lt r e e s ，i e ，t r e e sp o s s e s s i n gap e r f e c tm a t c h i n gw i t hn ov e r t e x h a v i n gd e g r e eg r e a t e rt h a n3 k e yw o r d s ：c o n j u g a t e dt r e e s ，m i n i m u mg e n e r a lr a n d i 6i n d e x 1 1 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的 研究成果本人在论文写作中参考的其它个人或集体的研 究成果，均在文中以明确方式标明。本人依法享有和承担 由此论文而产生的权利和责任。 责任人，( 签名) ：限心村 知矿- 7 年月1 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规 定厦门大学有权保留并向国家主管部门或其指定机构送 交论文的纸质版和电子版，有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆被查阅，有权将 学位论文的内容编入有关数据库进行检索，有权将学位论 文的标题和摘要汇编出版。保密的学位论文在解密后适用 本规定 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 作者签名：脉。、) 、门日期：易哕年f 月f 日 导师签名：獭建1 翅日期：加产令月尹日 第1 章引言 第1 章引言 1 图论是一门有趣而且应用性很强的学科从历史上看，它的每一次重要 的进步都离不开对实际问题的解答尝试，如欧拉和哥尼斯堡七桥问题、凯莱 和化学中同分异构体的计数问题以及基尔霍夫在电网络上所做的工作等等 现代图论随着生产管理、军事、交通运输、计算机和通讯网络等领域中许多 离散问题的出现而得到了长足的发展，产生了很多分支其中组合化学是比 较活跃的个分支，它在药理学( 药物设计) 、医药化学、结构化学、有机化 学以及环境科学等方面有着非常重要的应用 1 1 分子图和分子拓扑指标 众所周知，分子是由原子组成的，任何两个原子之间可以形成化学键，也 可以不成键，这是可以分辨的尽管分子的几何参数，如分子之间的距离、键 角等是可以测量的，但是由于存在着各种分子内的运动，如分子的振动，内 转动等，从而使得分子中原子的位置是不固定的另外，分子的几何性质也 会随着周围环境的影响，比如温度，压力等而发生改变由分子内部的运动 和各种外部的影响所引起的分子几何性质的改变可以看成是连续的形变，或 拓扑变形，因为没有键的破坏和形成尽管在这种形变的过程中分子的若干 几何性质发生了改变，但分子中原子之间相互关联的性质保持不变，而分子 中原子相互连通的全部信息确定了分子的拓扑性质 在组合化学中，我们用图来描述分子的拓扑结构我们用顶点代表分子 中的原子，用边代表原子之间形成的化学键，这种图被称为分子图在考虑 饱和以及共轭的碳氢化合物时，顶点只代表碳原子而略去氢原子，边只代表 碳碳原子之间的化学键，这种图叫做分子的骨架图，也称为隐氢图，如图 1 所示分子图不仅是分子拓扑结构的直观表达形式，而且表达了分子的拓 第1 章引言 2 扑性质如果两个分子中的原子之间具有相同的连通性质，或者说，它们具 有相同的分子图，那么就可以说这两个分子的拓扑性质是相同 丫 r丫7 打一c c c c 一| e ，啼 iiii hhhh f i 爪 ：a h 图1 ：分子和分子的骨架图 一般来说，我们把在分子图或其矩阵表示中不依赖于顶点的标号方式而 改变的量叫做分子图的拓扑不变量例如，分子图的不变量可以是顶点的数 目、边的数目、等长度路径的数目、邻接矩阵的顶点度和距离矩阵的距离度 等等另外，分子图的特征多项式以及图谱也都是分子图的不变量 虽然分子的拓扑性质可以用分子图来表达，但是从本质上来看，分子图 是个非数值的数学对象而在实际的应用中，分子的各种可以测量的物理化 学性质通常都是用数值来表达的，因此为了把分子的拓扑性质与分子的各种 可以测量的物理化学性质联系起来，必须首先把从分子图中所获得的信息转 变为一种能用数值表达的量经研究发现，分子图的各种不变量就是能够起 到这种作用的量也就是说，分子图的不变量不但可以定量地表达分子的结 构，而且还可以用来表示相关分子的结构与性能之间的关系，通常把具有这 种作用的分子图的不变量叫做分子拓扑指标分子拓扑指标在化学中的应用 已经成为当前信息化学的重要内容 当今组合化学的一个中心问题就是寻找具有某种物理或化学性质的分 子因为分子的拓扑指标可以统计地反映分子的物理和化学性质，因此为了 得到所期望的分子，首先就要得到这种分子的拓扑指标，然后利用计算机搜 索，建立具有这种指标值的分子图数据库，最后在库中选择理想并且能够合 第1 章引言 3 成的结构去合成它们这一过程的关键在于建立具有某拓扑指标值的分子图 数据库，而建立这个数据库所要解决的问题就是求给定分子图的拓扑指标的 逆问题，即求出相应的分子图，使得该分子图的拓扑指标值等于预先设定的 某个具体值或者在预先设定的某个范围内该问题的深入研究对有目的合成 一些分子或药物具有非常重要的理论价值和应用背景 极值问题是组合化学中另一个有趣而且有应用背景的研究分支，它本身 也是极值图论的一个典型的应用什么样的分子结构具有大的拓扑指标值， 什么样的分子结构具有小的拓扑指标值，以及由此衍生而来的某类分子结构 的拓扑指标值界( 上界或下界) 的确定，都可以用来帮助建立分子图数据库 1 2 几种重要的分子拓扑指标 自美国化学家h w i e n e r l l 】在1 9 4 7 年提出目前在化学界公认的第一个 分子拓扑指标一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 d 指标 w i e n e r 指标 w i e n e r 指标最初定义为路径和【1 j 即在一个分子中所有原子之间的键 的个数之和后来在1 9 7 1 年，日本化学家h h o s o y a n 给出了基于距离矩 阵d 的新定义；距离矩阵d 的上三角或下三角的元素值之和，即 w = w ( g ) = 专， ( 1 1 ) _ 0 时，是路r ；当a 0 时，是星图兔而对具 有最大风指标的树的结构的刻画则没有这么简单，其中- 2 q 0 时，x l i 和j z h e n g l 4 2 l 确定了具有最小和最大r 口指标的化学树 第j 章引言 8 m 匹配树t 4 3 是指t 中至少有一个m 一匹配，且可能还有比1 7 匹配 大的匹配如果n = 2 m ，则称丁为完美匹配树( 又称共轭树1 4 9 1 ) m l u 等人【4 3 l 首先在m 匹配树中研究r a n d i d 指标，他们证明了 r 丁m ) = 磊等+ 而m 葡- 1 + 百r a - i ，( 1 7 ) 且等式成立当且仅当t = 瑶m 其中震。是在星图b - m + 1 的m 一1 个 悬挂点上各连一条悬挂边所得到的树显然，碍m 是一棵m 一匹配树，而 7 。则是一棵2 m 阶的完美匹配树( 如图3 所示) r m 一1j 【 图3 ：碥，m 和磋。 1 玎一2 m + 1 j x p a n 等人在【4 4 】中对7 7 t - 匹配树的广义r a n d i d 指标进行研究，推广 了m l u 等人的结论，证明了当一；冬q 0 的情况，当2 m n 3 r a + 1 时，他们确定了m 匹配树的广义r a n d i d 指标的下界，并刻画了达到这些 下界的极值图( 类) 本文在m l u 等人【删和x p a n 等人研究的基础上，对共轭树的广 义r a n d i d 指标进行了进一步的研究对q 一1 的情况，我们确定了共轭 树的广义r a n d i d 指标的最小值以及达到最小值的极值图( 类) 有趣的是， 这些极值图( 类) 都是共轭的化学树，即最大度不超过3 且具有完美匹配的 第l 章引言 9 树这一类树与无环烯烃分子的碳原子骨架是一致的，因而具有很强的物理 和化学背景 为方便起见，下面我们称具有最小r a n d i 6 指标的共轭树为最小共轭树 第2 章q - 1 时的最小共轭树 第2 章q 一1 时的最小共轭树 2 1 预备知识 在本节中，我们将给出本章所特有的一些定义、术语和记号，以及证明 我们结论需要用到的一些引理和推论 引理1 函数，( z ) = 铲( 0 1 ) 2 口+ 1 ) 如果q 一1 ，那么当z 2 时，f ( x ) 一，( z 一1 ) 是单调递增的 证明：函数f ( x ) 的二阶导数为 气d 2 f r ( x ) = q 矿一2 ( 2 口( q + 1 ) x + 2 a ( 1 - q ) + q 一1 ) 考虑函数9 ( z ) = 2 a ( 乜+ 1 ) x + 2 口( 1 一q ) + q 一1 因为q - 1 ，所以 业d z = 2 。( q + 1 ) 0 因此 2 。( 口+ 1 ) x + 2 。( 1 一q ) + q 一1s2 。( a + 1 ) 2 + 2 。( 1 一q ) + a 一1 = 2 a ( 3 + 口) + 口一1 - 1 0 ，即，( z ) 一，( z 一1 ) 是单调递增的 引理证毕 口 引理2 方程4 善一3 霉+ 2 ( 6 z 一9 z ) = 0 ，2x4 z 一3 霉一酽= 0 和 3 4 z 一3 z 一2 6 。= 0 有且仅有一个负根，分别记为历一1 3 8 6 7 ， 侥一2 0 6 8 4 和风- 3 0 8 1 6 ( 见图4 ) ，而且 ( i ) 当风 q o ；当q 历时， 4 q 一3 0 + 2x ( 6 0 一9 0 ) 0 ( i i ) 当侥 口 o ；当q 仍时， 2 4 口一3 口一9 n 0 第2 章o 一1 时的最小共轭树 1 1 ( i i i ) 当风 q 0 ；当q 0 ：以工) = 4 j 一3 l + 2 矿 一妒i ( b 如) 、? 1 人工) = 2 4 。一3 。一旷 ( d ：期 、 x ) ：3 4 r 一3 一2 膏6 。； ， ( p ， 夕，7 图4 ：一些指数函数的曲线图 证明：我们考虑函数f ( z ) = 矿，其中z 0 ，所以它的一阶导数，7 ( z ) 是单调递增的再由拉 格朗日中值定理，我们知道必存在唯一的个( 3 ，4 ) ，使得 4 2 3 。= f ( 4 ) 一f ( a ) = ，k ) = z r 同理，必存在唯一的一个叩( 6 ，9 ) ，使得 9 z 一6 。= f ( 9 ) 一f ( 6 ) = 3 f 7 ( 叩) = 3 z 矿一1 第2 章q 一1 时的最小共轭树 1 2 结合方程4 一扩+ 2 ( 6 霉一旷) = 0 ，我们有 4 霉一3 2 + 2 ( 6 z 一9 z ) = z 一1 2x3 z 矿一1 = 0 于是，方程4 z 一3 王+ 2x ( 6 2 一旷) = 0 的负根为。 俄= 簧等 。 由于和口都是唯一的，因此伪也是唯一的用m a t l a b 我们可以很容易 算出；侥- 1 3 8 6 7 同理，我们可以证明侥和岛分别是方程2 4 牙一3 霉一旷= 0 和 3x 铲一3 z 一2x6 王= 0 唯一的负根由图4 我们知道，( a ) ，( b ) ，( c ) 和( d ) 显然是成立的引理证毕 口 下面我们所考虑的树都是共轭树令m 是个正整数，我们记所有2 m 阶的共轭树的集合为玩m 因为当m = 1 ，2 时，结论是平凡的，所以我们 通常假设m 3 定义1 在路尸m = u l t 2 u 。的每个顶点u i 上各连一条悬挂边u i v i 所得到的图称为梳子图( 如图5 所示) ，记为c k ( 0 ) 定义2 由梳子图c 2 ( m + k ) ( o ) 删去k 对悬挂点 仉。，忱。+ 1 ) ， 饥：，y i ：+ 1 ) ， ， ，v i k + 1 ) 后所得到的由顶点导出的一个图类记为c 2 。( 七) ，其中 如果0 k 罟1 2 ，那么i l 3 ，i 七m + k 一3 ，而且对任意的j 1 ，2 ，k 一1 ) ，都有i j + 2 巧+ l ； 如果f 罟1 2 k m 一2 ，那么i l = 2 或i 1 = 3 ，i 七= m + k 一3 或 i k = m + k 一2 ，而且对任意的歹 1 ，2 ，k 一1 ) ，都有i j + l = i j + 2 或0 + 1 = i j + 3 成立 由定义1 和定义2 ，我们知道岛m ( 七) 玩m ，而且 岛m ( o ) = c k ( o ) ) ，c 2 m ( m 一2 ) = 恳。) ； 第2 章q 一1 时的最小共轭树 1 3 如果m 为奇数，则已m ( 旦学一2 ) 中恰好只有一棵树； 如果7 n 为偶数，则岛。( 罟一2 ) 是由那些恰好只有两个连续的3 度点 的树组成的；而c 2 m ( 罟一1 ) 则是由满足以下这些条件的树组成的： ( i ) i l = 2 ，i 七= m + k 一3 同时对任意的j ( 1 ，2 ，k 1 ) ，都有 i 件l = i j 十3 或( i i ) i l = 3 ，i k = m + k 一2 同时对任意的j 1 ，2 ，k 一1 ，都有i j + l = i j + 3 或( i i i ) i z = 3 ，i k = m + k 一3 而且恰好只有一个整数h 1 ，2 ，k 一1 ) ，使得i h + l = i h + 2 同时 对任意的j 1 ，2 ，k 一1 】 ) ，都有i j + l = i j + 3 我们在图5 具体给出了岛m ( 后) 中的一些树，其中c 锄( 尼) 表示c 2 m ( 七) 中的任意一棵树 “i_ 2- 。 n 门 y 吒叱 c ：( 0 ) 兀邗 c 。：( 1 ) _ 九1 广 g ( o )g ( 1 )c 。( 2 ) 九n 九1 c ：( 2 ) c ，：( 2 ) 几广九 c 。( 2 ) r l j 门 c 。( 3 ) 图5 ：c 2 。( 七) 中的一些树 我们定义两个图类如下： 岛m = u 岛m ( 七) 和= u ( 七) k = 0 1 ，r - t 一2七= 【署j l ，m 一2 而且我们可以很容易验证，玩= c d o ) ，c 8 ( 1 ) = p o ，c 6 = g ( o ) ) ，c 占= g ( o ) ，r ) 且3 8 = c 8 ( o ) ，c s ( 1 ) ，g ( 2 ) = p 8 ，f s ，露) ，c 8 = g ( o ) ) ，g = c s ( 1 ) ，p s ) ，其中晶和露如图6 所示 第2 章o t 一1 时的最小共轭树1 4 图6 ：f 8 和露 由引理2 ，我们可以直接得到以下推论： 推论3 ( i ) 如果尾 q - 1 ，则r ( c d o ) ) 凡( r ) ；凡( g ( o ) ) 耽( c s ( 1 ) ) ，r q ( 尽) ；兄( 岛( 1 ) ) 凡( b ) ，心( 露) ( i i ) 如果q 仍，则见( g ( 1 ) ) 风( g ( o ) ) ，r o ( 日) ；心( g ( o ) ) 或( r ) ( i i i ) 如果q = 岛，则r ( g ( o ) ) = 风( g ( 1 ) ) 见( b ) ，兄( 晶) ，凡( 露) 2 2 主要结果 我们令 庐o 1 咖2 m m m 3 。+ ( m 一3 ) 9 。+ 2 。+ 1 + 2 6 。； x3 n + 字x4 a + ( m 一1 ) x6 口+ 2 口+ 1 ， m 为奇数； 3 a + 字x4 a + ( m 一2 ) 6 a + 2 口+ 1 + 9 a ，m 为偶数 3 口+ 字x4 q + ( m 一1 ) 6 a + 2 叶1 ， m 为奇数； x3 a + 罟x4 a + ( m 一2 ) x6 a + 2 口+ 1 ， m 为偶数 p ( m ) = ( 2 m 一3 ) x4 口+ 2 q + 1 由岛m ( 忌) 的定义，我们知道对任意一棵树t c 2 。( 后) ，都有 冗。( t ) ： 加( m ) + 七( 4 。一3 。+ 2 ( 6 口一9 。) ) ，0 七f 零1 2 ；，( 2 1 ) 【p ( m ) + ( 仇一k 一2 ) ( 3 a + 2 6 n 一3 4 a ) ，【等j 一1 k m 一2 我们的主要结果如下 定理如果o t 一1 ，则共轭树的广义r a n d i d 指标的最小值及相应的极 值图( 类) 如下表所示； q 孚弘孚宁 0，j、i，j 1 - ， = = i i 第2 章q - 1 时的最小共轭树 1 5 表1 共轭树的广义r a n d i d 指标的最小值及相应的极值图( 类) q 最小值极值图( 类) 胁 qs - 1o ( m )g m ( 0 ) p 1咖o ( m ) ( = ( m ) )c 2 m 仍 q 历矽( m ) c j 。( f 罟1 2 ) 侥- ( m ) ( = 砂2 ( m ) ) c j m ( 等1 2 ) u c 奎。( 【号j 一1 ) 岛 q 侥砂2 ( m ) c j 。( 【罟j 一1 ) 风 也( 仇) ( = p ( m ) ) 。 一。 2 口+ 6 a 一2 3 a 0 ， 这和t 最小是矛盾的命题1 成立 在下面的证明中，由命题l ，当d 3 时，不失一般性，我们通常假设 出( 1 ) = 1 和出( 钝) = 2 ，i = 2 ，3 ，d 一2 令r = t t 1 一u 2 ，则 t 另( m 1 ) ，而且 d-2 r 口( r ) = 耽( r ) + 2 a + ( 2 d ) a + ( d 口一( d - 1 ) a ) ( d t c u d a - 1 - d t ( u 4 ) 。) i = 1 ： 蹦+ 2 q ( 2 d 尸“d 口- ( d _ l 尸) ( 1 + 2 a ( d - 3 ) + d t ( t t 4 ) a ) d 3 ( 2 2 ) i ( r ) + 垆+ 4 口+ ( 2 a 一1 ) d t ( t 4 ) 口，d = 2 下面我们根据d 的值分三种情形进行讨论： 情形1d = 2 因为d t ( u 4 ) 2 且q 一1 ，所以由( 2 2 ) 式我们有 r 口( t ) r a ( r ) + 2 4 a ， 等式成立当且仅当d t ( t 4 ) = 2 情形2d = 3 由( 2 2 ) 式，如果t i t ( u 4 ) 3 ，则 r a ( t ) = 吼( ，) + 2 q + 6 a + ( 3 n 一2 。) ( 1 + 如( u 4 ) 。) r a ( t 7 ) + 3 0 + 9 口， ( 2 3 ) ( 2 4 ) 第2 章o l 一1 时的最小共轭树 1 7 等式成立当且仅当d t ( u 4 ) = 3 如果d r ( u 4 ) = 2 ，令r = r v l t , 3 ，则t 玩( m 一2 ) ，而且 凰( t ) = 吼( r ) + 炉+ 3 0 + 2 6 口+ ( 严一1 ) x 如( t 5 ) o 如果仇25 ，则如( 乱5 ) 2 ，于是 忍( 丁) r 口( ，) + 3 a + 4 。+ 2x6 0 ，( 2 5 ) 等式成立当且仅当如( u 5 ) = 2 情形3d 4 令函数，( z ) = 铲( 一1 ) 2 a + 1 ) ，由引理1 ，我们知道i ( d ) 一f ( d - 1 ) 2 ，( 4 ) 一，( 3 ) 于是由( 2 2 ) 式，我们有 冗a ( t )r a ( r ) + 2 0 + 矿( ( d 一1 ) 2 a + 1 ) 一( d 一1 ) ax ( ( d 一2 ) 2 0 + 1 ) = r 。( t ) + 2 d + ，( d ) 一，( d 一1 ) r 口( r ) + 2 n + ，( 4 ) 一f ( 3 ) = r 口( r ) + 2 0 + 4 0 + 3 x8 0 一3 0 一2 6 0 ( 2 6 ) 命题2 如果伤 如( 乃。) ， 这和t 最小是矛盾的命题2 成立 由命题2 我们知道，如果5 2 q 一1 ，则t c 2 。假设t c 2 。( 七) ， 其中0 七5 等1 2 当历 0 因为t 是一棵最小的共轭树，所以根据( 2 1 ) 式，我们有七= 0 ，即t = ( o ) 类似地，当侥 q 历时，由引理2 ( i ) 我们知道4 a 一3 0 + 2 ( 6 n 一旷) 0 ，再根据( 2 1 ) 式我们有七= f 罟1 2 ， 即t c 2 。( f 罟1 2 ) 注意到c 2 m ( 罟 一2 ) 中的每一棵树都具有相同的广 义r a n d i d 指标，这就意味着t 是最小的当且仅当t c 2 m ( f 罟1 2 ) 当 q = 历时，4 a 一3 q + 2 ( 6 a 一9 口) = 0 ，由( 2 1 ) 式我们知道，c 2 m 中的每一 棵树都具有相同的吼，也就是说这个时候c 2 m 中的每一棵树都是最小的于 是。我们就证明了定理在陵 qs 一1 时是成立的 命题3 如果a 伪，则t c 主m 用归纳法对仇进行归纳证明当m = 3 时，因为磊= c 苫，所以命题3 显 然成立当7 t t = 4 时，因为t 是最小的，所以由推论3 ( i i ) ，我们有t = q ( 1 ) 或t = 角，命题3 也成立现在我们来证明m 之5 的情况 由归纳假设。总是存在一棵2 ( m 1 ) 阶的最小树7 2 ( m 一1 ) c ；( m 1 ) ，使得 凡( r ) 风( t 2 ( m 一1 ) ) ，而且如果等号成立，则t c + 2 ( m 一1 ) 我们在t 2 ( 。一1 ) 中任取个和2 度点相邻的悬挂点，在它和路p 2 的个顶点之间连一条边， 这样得到的树记为乃m 显然t 2 。c ；m ，而且 r a ( 乃。) = r 口( 孔( m 一1 ) ) + 2 4 a ( 2 9 ) 第2 章q 冬一1 时的最小共轭树 2 0 情形1d = 2 由( 2 3 ) 和( 2 9 ) 式，我们有 ( t ) 2 ( 死( m 一1 ) ) + 2 4 a = r q ( 噩m ) 如果等式成立，则t 呸细一1 ) 且d t ( u 4 ) = 2 ，即t 情形2d = 3 注意到0 l ( ) ， 这和t 最小是矛盾的 如果d r ( - 4 ) = 2 ，那么由归纳假设。总是存在一棵2 ( m 一2 ) 阶的最小 树t 2 一2 ) 矿2 帆一2 ) ，使得吼( r ) ( 正仲一2 ) ) ，而且如果等式成立，则 r 2 一2 ) 我们在t 2 。一2 ) 中任取个与2 度点相邻的悬挂点，在它和路 只的一个2 度点之间连一条边，这样得到的树记为乃m 根据c 2 m 的定义， 我们知道t 2 m c 2 。，而且类似于命题2 的证明，我们有吼( t ) 2r 。( t 2 。) ， 且如果等式成立，则r 喏( m 一2 ) 且d t ( - 5 ) = 2 ，即t c ；m 情形3d 之4 因为q r 口( 死。) ， 第2 章q 一1 时的最小共轭树 2 1 这和t 最小是矛盾的命题3 成立 由命题3 我们知道，如果a 仍，则t c 假设t c 2 。( 七) ，其 中l 罟j 一1 k m 一2 由引理2 ( i i i ) 我们知道，当风 a 阮时， 3 n + 2x6 口一3x4 q 0 因为t 是一棵最小的共轭树，所以根据( 2 1 ) 式， 我们有k = 【i 7 n j 一1 ，即t c 2 m ( 【罟j 一1 ) 注意到c 赫( 等1 2 ) 中的每一棵 树也都具有相同r 口，于是，t 是最小的当且仅当t c 2 。( i 罟i 一1 ) 类似 地，根据引理2 ( i i i ) 和( 2 1 ) 式，当a 0 ，则 k = m 一2 ，即t = 恳仇；当q = 岛时，因为3 a + 2 6 0 一3 4 口= 0 ，所以 c 中的每棵树都是最小的这样就证明了定理在q 伤时也是成立的 命题4 如果q = 陡，则t c 2 。( 罟 一2 ) uc 2 m ( 【罟j 一1 ) 用归纳法对m 进行归纳证明根据推论3 ，我们可以很容易验证命题4 在m = 3 ，4 时是成立的现在我们来证明m 5 的情况 首先假设m 为奇数这个时候我们注意到罟 一2 = 【罟j 一1 ，而且 c 拥( 警1 2 ) 中恰好只有一棵树c 2 仇( 等1 2 ) 于是我们只需要证明对任意 的一棵树t 玩m ，都有风( t ) r q ( e 2 。( f 等1 2 ) ) ，而且如果等式成立，则 t = q m ( 罟1 2 ) 由归纳假设我们知道，总是存在一棵2 ( m 一1 ) 阶的最小树疋( 仇一1 ) 岛( m 一1 ) ( 旦 一2 ) l 仲一1 ) ( 【旦铲j 一1 ) ，使得吼( r ) 吼( 疋( 。一1 ) ) ，而且如果 等式成立，则r c 2 ( m 一1 ) ( 学1 2 ) uc 2 一1 ) ( 【孚j 一1 ) 由引理2 ( i i ) 我 们知道，如果口= 侥，则r 。( 乃m 1 1 ) ；砂1 ( m 一1 ) = 咖( m 一1 ) 于是我们可 ； 以得到 。 r a ( c 2 。( f 筹1 2 ) ) 一吼( 而( m 一1 ) ) = ( m ) 一赴( m 一1 ) = 3 口+ 2 6 口一4 a ( 2 1 0 ) 情形1d = 2 第2 章q - 1 时的最小共轭树 2 2 因为角 也( 乃m ) ， 这和t 最小是矛盾的于是当m 是偶数时，我们也证明了命题4 是成立的 当q = 岛时，由( 2 1 ) 式和引理2 ，- i r k 验证c 2 m ( f 罟1 2 ) uc 2 。( 【罟j 一1 ) 中的每一棵树都具有相同的广义r a n d i 6 指标吼= l ( m ) = 如( m ) 于是由 命题4 我们知道，t 是最小的当且仅当t 岛。( f 予1 2 ) u 岛m ( 1 罟j 一1 ) 定理证毕 口 2 3 注记 到目前为止，对一1 a 一 的情况，刻画具有最小r a n d i d 指标的共 轭树的结构还是一个尚待解决的问题 事实上，我们用【4 3 】中的方法可以很容易证明，当肺q 0 时， 砭n m ( 如图3 所示) 具有最小的r a n d i d 指标，其中阮( 一0 6 7 0 5 ) 是方程 ( 4 + 2 x ) 铲+ z 一1j ，0 唯一的一个负根，这部分地推广了阻】中的结论 然而对于一1 a o 【j 】，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 6 ( 2 0 0 6 ) 5 5 7 - 5 7 0 【2 3 】h l i ua n dq h u a n g ，b i c y c l i cg r a p h sw i t hm i n i m u mg e n e r a lr a n d i d i n d e x j ，j x i n j i a n gu n i v n a t s c i ( i nc h i n e s e ) 2 3 ( 1 ) ( 2 0 0 6 ) 1 6 - 1 9 2 4 】c d e l o r m e ，o f a v a r o