（应用数学专业论文）广义randic指标在树图上的最大化问题.pdf

摘要 摘要 在化学研究中，对碳氢化合物定义某些指标可以简便且直观地反映一些重要 的物理化学性质r a n d i 6 指标就是这样一种指标研究r a n d i 6 指标的极值问题不 仅在数学上有着重要的意义，而且对相关的化学研究也有很大作用和影响 本文主要讨论树图的广义r a n d i 6 指标的最大化问题简单图g 的广义r a n d i 6 指标冗一q ( g ) 则定义为所有边乱秽的权重( d m ) d ) ) - q 之和，o g 是任意实数，d ( u ) 表示点u 的度关于树图的广义r a n d i 6 指标的最大化问题，目前只有当q ( 万1 ，2 ) 时没有解决我们所要讨论的正是这一问题的一部分 第一章简单介绍了研究背景、意义以及目前相关的研究结果 第二章研究了树图的广义r a n d i d 指标r a ( a ( q o ，2 ) ) 的最大值 第三章得到了含有最大广义r a n d i d 指标冗一a ( q ( 1 ，2 ) ) 的树图的一个重要 性质 第四章对全文进行了总结，并给出了关于含有最大广义r a n d i 6 指标尺一q ( o z ( 1 ，2 ) ) 的树图结构的猜想 关键词广义r a n d i 6 指标最大树半树茎叶柄 a b s t r a c t a b s t r a c t i nt h ec h e m i s t r ys t u d y , c e r t a i nd e f i n e di n d i c a t o r so fh y d r o c a r b o n sc o u l dr e f l e c t s o m ei m p o r t a n tp h y s i c a la n dc h e m i c a lp r o p e r t i e se a s i l ya n di n t u i t i v e l y r a n d i 6i n d e x i so n eo fs u c hi n d i c a t o r s t h er e s e a r c ho fe x t r e m a lp r o b l e mo fr a n d i 6i n d e xd o e s n o to m yh a v ei m p o r t a n ts i g n i f i c a n c ei nm a t h e m a t i c s ，b u tp l a y sa l li m p o r t a n tr o l ef o r c h e m i s t r ys t u d y t h i sp a p e ri sa b o u tt h et r e ew i t hm a x i m u m g e n e r a lr a n d i 6i n d e x t h eg e n e r a l r a n d i 6i n d e xr q ( g ) o fas i m p l eg r a p hg ，i sd e f i n e da st h es u mo ft h ew e i g h t s ( d ( 乱) d ( ) ) 一qo fa l le d g e su 口o fg ，w h e r ed ( u ) d e n o t e st h ed e g r e eo fav e r t e xui n g m o s to f t h em a x i m i z a t i o np r o b l e m sa b o u tt r e e sh a v eb e e ns o l v e d , l e f to n l yt h em a x - i m u mv a l u eo fr aw h e n q ( 互1 ，2 ) i su n d e t e r m i n e d ，t h i sp a p e r w i l ld i s c u s ss o m e p a r t o ft h i sp r o b l e m i nc h a p t e r1 ，t h eb a c k g r o u n d ，s i g n i f i c a n c ea n ds o m er e l a t e dr e s u l t ss of a rw i l lb e i n t r o d u c e d i nc h a p t e r2 ，w ew i l ls t u d yt h em a x i m u mv a l u eo ft h eg e n e r a lr a n d i 6i n d e xr q ， w h e r eo t ( o l 0 ，2 ) i nc h a p t e r3 ，w ew i l lp r e s e n ta ni m p o r t a n tp r o p e r t yo f t h em a xt r e ew h i c hh a st h e m a x i m u m g e n e r a lr a n d i 6i n d e xr q ，w h e r eq ( 1 ，2 ) i nc h a p t e r4 ，w ew i l ls u m m a r i z ea l lt h ec o n c l u s i o n sa n dw i l lb r i n gf o r w a r dac o n - j e c t u r eo ft h es t r u c t u r eo ft h em a xt r e e ，b e s i d e sw eg i v eam e t h o dw h i c hm i g h tb e h e l p 允1i nc o m p l e t e l ys o l v i n gt h i sp r o b l e m k e y w o r d s g e n e r a lr a n d i 6i n d e xm a xt r e eh a l f - t r e es t e mp e t i o l e 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 年月日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版：在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： 一一一一。“”一一”一“一”“? t 内部5 年( 最长5 年，可少于5 年)| i 秘密1 0 年( 最长l o 年，可少于1 0 年)l | 机密2 0 年( 最长2 0 年，可少于2 0 年)| 第一章引言 第一章引言弟一早，ii 简单图是指无自环、无多重边的图，一般用g 表示符号v ( a ) 和e ( c ) 分 别表示图g 的顶点集和边集若u y ( g ) ，则d ( u ) 表示与点u 相连的边的数目， 称为顶点让的度，( u ) 表示所有与点u 相邻的点的集合 1 】树图( 简称树) 是 连通且不含圈的简单图一般用t 表示树t 中的1 度点称为叶子路p 是指仅 含有两个叶子的树，星s 是指含有i y ( t ) l 一1 个叶子的树，双星d s 是指有且仅 有l y ( t ) i 一2 个叶子的树，星的重分9 是指在星s 的每一条边上增加一个( 或两 个) 顶点p s ，d s ，s + 如图所示： p d s s 图1 1 路、星、双星和星的重分 对一个图g ，其广义r a n d i 6 指标定义【2 如下： r q ( g ) = ( d ( u ) d ( 口) ) 一q u v e e 其中q 是任意实数 在1 9 7 5 年，化学家m i l a n r a n d i 6 3 提出一对拓扑指标r ( r 一1 和r 一；) ，目的 是为了衡量饱和烃分子的碳原子架的分枝程度，因此，r a n d i 6 把它命名为“分枝指 第一章引言 标”r a n d i 6 意识到他的指标冗与烃的一些物理化学性质之间可以建立很好的 函数关系，这些性质包括：沸点、色谱保留时间、气压安托万方程的系数等等，为 了纪念r a n d i 6 的这一发现，把指标r 称为r a n d i 6 指标最初的研究都只停留在化 学层面上 4 ，5 】，因此研究进度缓慢后来，数学家b o l l o b f i s 和e r d s s 把这个指标 进行了推广【2 ，6 】，将一万1 和一1 替换成任意实数q ，从而得到了广义r a n d i 6 指标 r q 于是激发了人们对这个指标的兴趣关于广义r a n d i 6 指标的研究成为图论 界的一个新热点，每年都有很多新的研究成果问世 7 】人们通常比较关注指标的 极值化问题，并且寻找不同类图形的广义r a n d i 6 指标的极值 8 1 0 】 本文讨论的是当图g 为树图时的广义r a n d i 6 指标的极值问题对这个领域 的研究具有显然的实际意义，因为烃分子的碳原子架本身就是树的结构，通过对树 的广义r a n d i 6 指标极值问题的探讨，可以建立由指标( 代数性质) 到结构( 几何 性质) 的映射，从而对饱和烃的相关物理化学性质的研究提供有价值的理论帮助 含有极大广义r a n d i 6 指标兄一口的树，称为最大( 小) 树关于最小树结构的 研究，已经有了很好的结论【l l 】：当q 0 ，最小树为路；当q 1 ) 的最大树，则有如下结论 ( 1 ) 每个叶子都须与2 度点相连 ( 2 ) 每个2 度点都只存在于悬挂路上 ( 3 ) 所有的悬挂路要么都是2 长的，要么只存在一条是3 长的，其余均为2 长的 由上述引理，很容易知道最大树t 的最大度不小于3 ，换言之，最大树丁的分支 点集合非空用u v ( t ) 表示树t 的最大度点，符号b n ( 0 3 ) 表示与顶点u 相邻 的分支点的数目，则可以得到下面关于最大树的重要性质 引理2 2 存在一个实数q oe ( 1 2 9 6 1 ，1 2 9 6 2 ) ，使得对任意的q 咖，广义r a n d i k 指标r q 的最大树t 的最大度点u 满足b n ( w ) 1 证明反证法假设b n ( z ) 2 ，也就是说至少存在两个分支点u 1 和u 2 与最大度点u 相邻，不妨设d ( u 1 ) = p d ( w 2 ) = q 3 记d ( w ) = ，y t ( z = 1 ，2 ，a - 2 ) n ( w ) u 1 ，0 3 2 ，x l i ( i = 1 ，2 ，p 一1 ) n ( 0 3 1 ) u ，x 2 3 ( j = 1 ，2 ，g 一1 ) n ( 0 3 ) u ) 删掉u 1 和u 2 ，把所有的z “和z 2 j 都连到u 上，再以u 为中心增加一条2 长 悬挂路，通过这些操作，得到了一棵新的树结构t 7 ，而且i y ( r ) i = i y ( t ) i = n ， 5 第二章树的极大广义r a n d i 6 指标 考虑t 和r 的广义r a n d i 6 指标值的差： 冗一q ( 丁) 一r q ( r ) = ( 击一西再 ：f 而) 善a - - 2 赤+ ( 刍一而1 ) p - i 1 矛 + ( 击一志) 霎赤+ h 1 - z ( 嘉+ 击) ( 2 ( 十p + q 一3 ) ) q 2 口 ( 巫1 一两未可) 等+ ( 嘉 + ( 击一两未而) 譬+ 去( 嘉+ 嘉) ( 2 ( + p + q 一3 ) ) q = 去 垡ipf-1-i- - i - a a = 一l 一 2 nl p o = ，( ，p ，g ；q ) ) p 一1 11 f 1 2 口 字+ ( 丢) n ( 嘉+ 击) 一番南一1 我们需要找到对任意的，p ，q 均满足f ( a ，p ，g ；q ) 0 的口，从而得到新树r 比 数t 具有更大的广义r a n d i 6 指标r a 值，这便与t 是最大树产生矛盾 为此令集合a = o i ( i x ，p ，g ；q ) = 0 ，a p q 3 ，a ，p ，q n 定义 q ；= s u po l ，为证明q ；的存在性，分以下两个步骤 ( i ) 证明f ( i ，p ，g ；1 2 9 6 2 ) 0 因为 又注意到当p 6 时 a z ( ，p ) 1 2 9 6 2 a 2 1 2 9 6 2 2 2 9 6 2 1 2 9 6 2 _ 二 2 1 - 2 9 6 2 2 2 9 6 2 1 2 9 6 2 2 1 2 9 6 2 p 2 2 9 6 2 1 2 9 6 2 2 1 - 2 9 6 2 6 p 2 2 9 6 2 0 2 9 6 2 ( 1 + 芸) 2 2 9 6 2 一一02962222 9 6 2 ) 。 、u 严一里旷 丽 蔫器 一 0一翌 助一 印一 6 6 9 9 2 2 一 一 r 一 兰严1 严喾喾 怯丽怯面 l l z 鬻炉 第二章树的极人广义r a n d i 6 指标 因此，当p 6 时有 z ( ，p ) 孢p ) 2 萨j l z ( p ) 这里z ( p ) = 兰竺坚掣一0 2 9 6 2 ( 1 一曲虿) 很容易证明当p 4 时警 o ， 又考虑到z ( 6 ) 0 ，因此当p 6 时，z ( p ) z ( 6 ) 0 即当p 6 时，纂 z ( ，p ) z ( v ，p ) = 南z ( p ) 0 故当p 6 时，l 厂( ，p ，口；1 2 9 6 2 ) 关于p 是单调减少的注意到p 和q 在函数 f ( a ，p ，口；1 2 9 6 2 ) 的对称性，同样的结论适用于口因此，分三种情况加以讨论 情形1 a p2q 6 显然f ( a ，p ，g ；1 2 9 6 2 ) f ( a ，6 ，6 ；1 2 9 6 2 ) 由拉格朗日中值定理得到 堑( 垒! 鱼! 鱼i ! ：兰堑型 d a ：上仁兰! ：兰皇鱼兰( ! 二盟竺2 + ，q ：塑兰一07 9 6 呈) 、 2 1 2 9 6 2 2 2 9 6 2 。( + 9 ) 1 2 9 6 2 1 2 9 6 2 1 2 1 2 9 6 2 ( 1 一( 扩2 9 6 2 )9 1 2 9 6 2 o 2 9 6 2 、 = = ： 一 _-二-=二-r-一 _ 2 1 2 9 6 2 a 2 2 9 6 2 p 9 6 2 ，1 2 9 6 2 2 ( 1 一( ；) l 2 9 6 2 )9 0 2 9 6 2 、 、 2 1 2 9 6 2 a 2 2 9 6 2 ( a + 9 ) 2 - 2 9 6 2 这里( a ，a + 9 ) 很容易验证当a 3 3 ，d r ( a , 6 d , 6 ；1 2 9 6 2 ) 0 ，从而当a 3 3 时，f ( a ，6 ，6 ；1 2 9 6 2 ) f ( 3 3 ，6 ，6 ；1 2 9 6 2 ) 0 对6sa 3 2 ，将每一个值带入f ( a ，6 ，6 ；1 2 9 6 2 ) 检 验，易知同样有f ( a ，6 ，6 ；1 2 9 6 2 ) 0 情形2 a p26 ，3 q 5 由f 关于p 得单调性知f ( a ，p ，口；1 2 9 6 2 ) sf ( a ，6 ，几，1 2 9 6 2 ) 注意到函数弼x - - 1 ( z z + 1 在z 4 时单调递增，而在z 4 时单调递减把不同的g 值带入f ( m ，6 ，q ，1 2 9 6 2 ) 中，以使得f 的每一部分都达到最大，我们得到 f ( a , 6 , q , 1 2 9 6 2 ) 丽1 1 这里z + 表示正整数集 坐a 1 2 9 6 2 + 高+ 4 1 2 9 6 2 + ( 矿9 6 2 + 百压丽+ + 【五j + 击) 一酉两1 丽一1 7 石 胪 f 第二章树的极大广义r a n d i 6 指标 由拉格朗日中值定理得到，当2 3 时， 一d f ( a ) ：一1 2 9 6 2 ，兰二盟= 二盟竺一璺兰9 ：翌、 d a 2 1 2 9 6 2 2 2 9 6 2 2 2 9 6 2 7 1 2 9 6 2 ( 2 1 2 9 6 2 型学一器、) 。 气 五孓面面一一乙至j i 孬i 西西j u 这里( ，+ 8 ) 但是注意到f ( 2 5 ) 0 ，所以我们只能得到当2 5 时，f ( a ，6 ，q ，1 2 9 6 2 ) f ( a ) 0 对于3 2 4 ，将所有的二元组合( ，口) ( 3 2 4 ，3 q 5 ) 带入函 数f ( a ，6 ，q ，1 2 9 6 2 ) 检验，不难证明f ( a ，6 ，q ，1 2 9 6 2 ) 0 情形3 3 q p 5 ，a 6 带入不同的p ，q 值以使得f ( a ，p ，g ；1 2 9 6 2 ) 的每一部分都达到最大，则有 f ( a , p , q ；1 2 9 6 2 ， 击l 篇+ 赫+ 籀+ ( 扩9 6 2 父 志3 一两a 南5 5 1 1 2 9 6 2 ( + + 一3 ) 0 2 9 6 21 j = f ( a 1 由拉格朗日中值定理，有当1 5 时， d f ( a ) 1 2 9 6 2 厂2 ( 1 一( 圹9 6 2 ) 7 0 2 9 6 2 、 d a2 1 2 9 6 2 i 2 2 9 6 2 2 2 9 6 2j 筹( 喾一器) 。 这里( a ，+ 7 ) 但是注意到f ( 6 4 ) 0 ，我们只能得到当a 6 4 时，f ( a ，p ，g ；1 2 9 6 2 ) f ( a ) 0 对没有讨论的情况6 6 3 ，3 q p 5 ，读者可以同样借助m a t h e m a t - i c a 软件计算每一个f ( z x ，p ，g ；1 2 9 6 2 ) 的值进行检验，最终得到f ( a ，p ，g ；1 2 9 6 2 ) 0 同样成立 情形4 3 q p a 5 用m a t h c m a t i c a 直接检验，( ，p ，口；1 2 9 6 2 ) 1 时h ( a ，p ，g ；q ) 是单调递减 这里h ( a ，p ，g ；q ) = a f ( a ，p ，g ；a ) 令8 = + p + q 一3 ，直接对q 求偏导 差= ( 圳( 嘉+ 珈( 丢) 一( 害+ 警) + 万l ns 一( - 2 ) 、下l na 一。- - ，l 矿a p _ ( g - 1 ) 警 注意到p q 3 ，故 ( 训( 嘉+ 珈( 丢) 一，坐p a + 竽) 。 因此只需考虑 矛i ns _ ( - 2 ) 警一_ 1 ) 坐p a 吨_ 1 ) 警 ( 2 1 ) 显然a s 一3 容易证明函数万| 1 1 x 在z 3 时是关于x 单调减少的，因此有 ( 2 1 ) 矛i n8 一( 一2 ) 下l na 一一1 ) 下i na 一( g 一1 ) 石l n a = l 蔷( 、s l n s ( 今) n 山叫) l 凹n a ( s l n i n s a 8 ( s - 1 ) ) 0 知g ( s ) 是凸函数；又注 意到a ( 6 ) 0 且l i mc ( 8 ) = 一o o ，因此有结论g ( s ) 1 时f ( a ，p ，口；q ) 是关于q 单调递减的，而 且f ( a ，p ，g ；1 2 9 6 2 ) 0 ，很容易推断对任意的o 1 2 9 6 2 ，f ( a ，p ，g ；q ) 9 第二章树的极人广义r a n d i 6 指标 i ( a ，p ，g ；1 2 9 6 2 ) 0 ， 因此令o o = n ；，则引理得证 口 上述引理具有极其重要的作用，因为由这个引理容易知道，如果t 是广义 r a n d i 6 指标r q ( o ( n o ，2 ) ) 的最大树，那么显然t 中最多含有一个或两个分 支点，因此需要考虑的问题就大大简化了在接下来的讨论中，q 的范围始终是 ( a o ，2 ) 2 2 最大树的结构 由于最大树t 只有两种情况：仅含一个分支点，仅含两个分支点令丁1 表 示所有仅含一个分支点的n 阶树的集合，于表示所有仅含两个分支点的n 阶树 的集合我们的思路是分别找到丁1 和严中的“最大树“，然后加以比较，最终 得到最大树的结构 情况1 t 1 中的最大树 这个情况相对比较容易，利用引理2 1 ，很容易得到最大树的结构只可能是单中 心树( 正则或奇异) ，因此我们有如下定理： 定理2 3 当n 为奇数时，矿中的最大树为正则单中心树死d ，i 当n 为偶数时，矿 中的最大树为奇异单中心树只廿 2 情况2 7 - 2 中的最大树 由于任意的树t 严均含有两个分支点，不妨设为u 和，而且d ) ：a d ( w 1 ) = m 3 显然由引理2 1 ，可知任意的t 于均满足i y ( t ) i = 咒1 0 当n 为偶数时，由引理2 1 可知，最大树结构只可能是正则双中心树；而当 n 为奇数时，同样由引理2 1 ，可能成为最大树的结构中必然存在一条3 长的悬挂 路，注意到无论这条3 长的悬挂路以u 还是以u 1 为中心，其广义r a n d i 6 指标的 值是不变的，因此，不是一般性，我们总是设3 长悬挂路以u 1 为中心，这样能成 1 0 第二章树的极人广义r a n d i 6 指标 为最大树结构的只有奇异双中心树 了解到最大树的可能结构是双中心树后，我们需要知道d ) 和d 1 ) 到底是 多少，从而确定最大树结构因此，考察下面的差： r q ( 昆，m ) 一r a ( 珏，m 一) 2 = ( 每一砸) 一( 茄斋一舔) + ( 丽1 r i m ) 一硒可南哥)( 口 ( ( + 1 ) ( m 一1 ) ) n = 夕( ，m ；a ) 于是，我们有下面的重要的引理： 引理2 4 当q ( q o ，2 ) 时，如果，m 满足下面的条件之一，则g ( n ，m ；o ) 丽1，因此只要g ( n ，m ；q ) 0 就能保证9 ( ，m ；q ) f ( 已；q ) = f ( m 一1 ；a ) 一f ( m 一2 ；q ) 这里矗( a 一1 ，) 且已( m 一2 ，m 一1 ) ，因此有a ( n ，m ；q ) 0 第二章树的极大广义r a n d i 6 指标 因而 如果m = 8 ，注意到8 ，也就是说 f ( 一1 ；o t ) 一f ( ；q ) f ( 7 ；q ) 一f ( 8 ；q ) a ( a ，8 ；q ) f ( 7 ；q ) 一f ( 8 ；o t ) 一f ( 6 ；q ) + f ( 7 ；o t ) = 芸一击一击= a ( q ) - 一。一， 1 6 a1 8 q1 4 q 1 、一7 我们需要证明s 1 ( q ) 0 考虑到& ( a ) 0 是一个超越不等式，因此，借助数学软件m a t h e m a t i c a ， 我们可以画出s l ( a ) 在区间( 1 ，2 ) 上的图像，如图所示2 3 两 图2 3 是( q ) 的图像 显然在( 1 ，2 ) 区间上s l ( a ) = 0 只有一个根，又& ( 1 2 9 6 1 ) 0 且 s a ( 2 ) 0 ，由函数的连续性我们得到s l ( a ) 0 是成立的，当q ( q o ，2 ) c ( 1 2 9 6 1 ，2 ) 这种证明超越不等式的方法我们称之为图像法从而有当28 时，a ( n ，8 ；q ) 0 ( 2 ) 8 ，m = 7 当a 1 0 时， ，7；q)面9一面10一去+一6g(a o 1 4 = 岛( q )，7 ；q ) 面一面一面+ 一= 岛( q ) 与证明研o r ) 0 的方法类似，我们首先画出岛o ) 在区间( 1 ，2 ) 上 的图像，得知足( q ) 在这个区间上仅有一个根然后计算昆( 1 2 9 6 1 ) 0 且 & ( 2 ) 0 ，由连续性知岛( q ) 0 成立，当q ( o o ，2 ) c ( 1 2 9 6 1 ，2 ) 从而当 1 0 时，g ( a ，7 ；口) 0 当a = 8 ，9 时，直接将a 的值带入g ( a ，7 ；q ) ，可 以得到同样用图像法证明g ( a ，7 ；a ) 0 1 2 第二章树的极大广义r a n d i 6 指标 ( 3 ) a 1 1 ，m = 6 当a 1 4 时， a ( a 6 q ) 芸一盖一斋+ 去= & ( q ) 与证明& ( 乜) 0 的方法类似，我们首先画出岛( q ) 在区间( 1 ，2 ) 上的 图像，并得知岛( 口) 在这个区间上仅有一个根，再计算& ( 1 2 9 6 1 ) 0 和 昆( 2 ) 0 ，由连续性可知岛( q ) 0 成立，当q ( o z 0 ，2 ) c ( 1 2 9 6 1 ，2 ) 因而， 当a 1 4 时，a ( a ，6 ；q ) 0 用同样的方法，当a = 1 1 ，1 2 ，1 3 时，易验证 g ( a ，6 ；q ) 0 成立 ( 4 ) a 6 8 ，m = 5 当a 9 6 时， a ( a ，5 ；q ) 面9 5 一画9 6 一未+ 去= & ( q ) 与证明s l ( a ) 0 的方法类似，我们首先画出& ( q ) 在区间( 1 ，2 ) 上的图 像，并得知& ( q ) 在这个区间上仅有一个根，再计算& ( 1 2 9 6 1 ) 0 和& ( 2 ) 0 ，由函数连续性我们可得到& ( q ) 0 成立，当a ( a o ，2 ) c ( 1 2 9 6 1 ，2 ) 从 而当9 6 时，g ( a ，5 ；q ) 0 对6 8 a 9 5 的情况，可以用同样的方法 证明g ( a ，5 ；q ) 0 引理的证明到此完成，但是需要说明一点，9 ( 7 ，7 ；q ) 、当6 a 1 0 时的 g ( a ，6 ；q ) 、当5 a 6 7 时的g ( a ，5 ；q ) 以及g ( a ，4 ；q ) 和夕( ，3 ；q ) 的符号是 无法确定的，因为它们与q 的具体取值有关系口 有了上述引理，我们就可以得到于中的最大树结构了 定理2 5 当n 为偶数时，铲中的最大树为正则双中心树，具体情况如下： 礓+ - 一m ，m ) t , 4 m ，m 】 礓+ ，一m ，m ) 礓+ 一m ，m ) 1 0 n 3 0 ，几2 6 n = 2 6 3 2 n 1 4 4 1 3 邻一酊一妯一“一 a n a n a n a n l 7 l r l r l r mm坳m蜘一m一 ，iii_-，、_i-【 第二章树的极大广义r a n d i 6 指标 当死为奇数时，于中的最大树为正则双中心树，具体情况如下： m a x 3 m 6 m a x 3 m 7 哗哪m 毪一m ，m ) z + 1 半一m ，m r + 1 气f m ，仇 1 1 n 3 1 ，扎2 7 咒= 2 7 3 3 扎1 4 3 咒1 4 5 证明首先考虑几为偶数，则很显然对正则双中心树珏m 有等式+ r n = 詈+ 1 我们已经知道最大树结构只可能是正则双中心树珏m ，又注意到有引理2 4 ， 当a m 8 ，有g ( a ，仇；q ) 0 则于中的最大树一定在珏，m ( 3 m 7 ) 中 因此，分几种情况讨论 ( 1 ) 1 0 n 3 0 ，礼2 6 因为6 a + m 1 6 ，+ m 1 4 ，因此当m = 7 时有8 9 由引理 2 4 ，得知勉，7 不可能是最大树而当m = 6 ，有6 1 0 ，m 8 考虑到 当1 0 时，函数g ( x ，6 ；o l ) 的符号没有确定，因此我们无法说明弘6 是否 是最大树同样弘，m ( 3 m 5 ) 也无法被排除在外 ( 2 ) n = 2 6 与上面的情况相比较，这里只有一处不同即弘，7 是可能的最大树，因为9 ( 7 ，7 ；q ) 的符号不确定 ( 3 ) 3 2 他1 4 2 注意到1 7 + m 7 2 ，则当m = 6 时有a 1 1 ，由引理2 4 知g ( ，6 ；a ) 0 ，所以死6 不会是最大树 ( 4 ) 几1 4 4 显然+ m 7 3 ，因此当m = 5 时，有6 8 ，也就是说夕( ，5 ；q ) 0 ( 由 引理2 4 ) 因此死5 不可能是最大树 综上结论，引理对n 为偶数的情况是成立的n 为奇数时的情况也类似可证 口 1 4 硒一 “一 m m 埝m 埘k 一 埘k 一 第二章树的极大广义r a n d i 6 指标 2 3 树的广义r a n d i 6 指标的极大值 现在我们可以通过比较矿和于中最大树的广义r a n d i d 指标值，来最终确 定当q ( a o ，2 ) 时，树的广义r a n d i d 指标的极大值记 ( 珏) = 衙a + 会 兄一a ( 黠) = 志+ 会+ 石1 如( 珏，m ) = 衙a - 1 + 丽m - 1 + 丽1 + 半 下面是本文的主要定理之一： 定理2 6 对任意的q ( c t 0 ，2 ) ，阶数n 7 的树的最大广义r a n d i 5 指标的极大 兄一q ( 写) m a x m a x m a x m a x n l a x maxrn(礓3m 6 、 、 o m a x 兄一a ( 丑4 3 m 7 、 。 m a x 3 ra(礓m6 、 z max冗一a(礓3 一m 一5 。 、2 max兄一a(礓3m 4 、 、o + 一m ，m ) ) ，r q 一仇，m ) ) ，r a ( 磁 + - 一m ，m ) ) ，r q + - m ，m ) ) + _ m ，仇) ) 佗= 8 1 0 n 2 4 n = 2 6 2 8 死 3 0 3 2 害，所以 船( 佗，q ) 塑+ 去一击一石2 = s ( q ) 与证明引理2 4 中的研( o l ) 0 且s ( 2 ) 0 ， 由函数连续性知s ( q ) 0 成立，当q ( q o ，2 ) c ( 1 2 9 6 1 ，2 ) 从而当扎1 3 时，p 3n ，q ) s ( q ) 0 对于n = 1 1 ，可以用同样的方法证明p 3 ( 1 l ，q ) 0 因 而当几为奇数而且扎1 1 时，正则单中心树足尝比奇异双中心树露士。，。具有 更大的广义r a n d i 6 指标类似地，我们可以得到当m = 4 ，5 ，6 ，7 时，p m ( n ，o g ) 0 因而，当礼为奇数时，正则单中心树b 巫是最大树，而它的广义r a n d i 6 指标值 即为极大值 情况2 当钆为偶数 在这种条件下，当n = 8 时，最大树的可能结构只有奇异单中心树霉而当n 1 0 时，最大树的结构随o t 的变化而变化，因此无法给出广义r a n d i d 指标极大值的 统一形式 口 虽然当佗1 0 为偶数时，无法给出极大广义r a n d i d 指标的统一形式，但是 当n 1 4 4 时，我们可以定义两个q 的界：n ；( 佗) 和q ；( 几) 它们把区间( q o ，2 ) 划 分为三个部分，而在每一部分，我们可以给出极大广义r a n d i 6 指标的统一形式 1 6 第二章树的极大广义r a n d i 6 指标 对礓一和礓一2 ，3 ，我们有： q l ( n ，q ) = r q ( 礓一t ) 一r a ( 礓- 2 3 ) o = 三( 丢杀( 凡一4 ) ”1) + 丽1 - - ( 2 ) a + 去一吾 方程g l ( + ，q ) = 石1 一雨2 = 0 有一个根l o g 2 另一方面，记方程q l ( 1 4 4 ，q ) = 0 的根为q 1 ，容易知道q 1 l o g 墨2 则 由q l ( n ，q ) 的连续性，我们得知q ；( 几) 属于区间( 1 0 9 害2 ，q 1 1 而当q 口：( n ) ，结果相反 对礓_ 2 3 和礓_ 3 ，4 ： q 2 ( n ，q ) = r q ( 礓- 2 3 ) 一r a ( 7 - _ 。- 3 4 ) 1 = 2( 面 1 4 1 a 一1 2 3 + 万一豇 1 ( 几一6 ) q _ 1) + 藩一器 方程9 2 ( + ，q ) = 丽2 一万3 = 0 有根l o g 互3 ；此外，令方程q 2 ( 1 4 4 ，q ) = 0 的根为 0 2 ，容易知道q 2 l o g ；因此q ；( 佗) ( 1 0 9 ；，q 2 i 而且当q 口；( 佗) 时，结果相反 再有，很容易计算出q 2 ；( 扎) 因此，作为上 述讨论的总结，下面给出一个表格： q q o q q ；( n )q ；( n ) q 口i ( 几)q ：( 佗) o t 0 时，函数，( z ) = ；而1 一面酽1 关于z 单调递减，又d 4 ， 1 9 第三章含最大广义r a n d i 6 指标的树图结构 凼此 r q ( t ) - - r _ a ( r ) 击( 否石1 一万干b 石) + 萨2 一万1 = 去( 5 ( 三) a 廿一4 ) = 面1 如， 考虑到夕7 ( q ) = 5 ( ；) qi n 百4 3 ql n3 ，令9 ( q ) = 0 得到q 7 = 苹 1 ，而夕7 ( 1 ) 0 ， 故夕( q ) 在( 1 ，2 ) 上单调递减又因夕( 1 ) 0 ，因此夕( a ) 9 ( 1 4 ) o (