（应用数学专业论文）k悬挂点树关于连通度指标的极值问题研究.pdf

五悬挂点树关于连通度指标的极值问题研究 摘要 分子的拓扑指标可以统计地反映分子的物理和化学性质不同的分子拓扑指 标反映的是该分子的不同性质，它们在q s p r ( q u a n t i t a t i v es t r u c t u r e - p r o p e r t yr e l a - t i o n s ) 和q s a r ( q u a n t i t a t i v es t r u c t u r e - a c t i v i t yr e l a t i o n s ) 中有着重要的作用为了 利用数学方法研究分子结构与化学物理i 生质之间的关系，人们提出些相关的分 子图的拓扑指标【1 4 ，1 5 】最著名的拓扑指标有w i e n e r 指标、h o s o y a 指标和r a n d i 6 指标 个分子结构可以表示为个图g = ( v ，e ) ，其拓朴指标与相应的图的不变量对 应图g 的r a n d i 6 指标定义为 肚郴) 2 善丽1 ，u v 、一、 其中d g ( u ) 是图g 中的顶点仳的度，和式遍历g 中所有的相邻点对。 1 9 7 5 年，为了研究有机分子尤其是烷烃的碳原子骨架的分支程度，m i l a nr a n d i 6 提出了“分支指标”【1 6 r = r ( c ) r 值对q s p r 和q s a r 的研究有着巨大的作 用，它的广泛应用远远超出当初r a n d i 6 提出这个指标的最初目的( 即用数量测定 “分支”的思想 1 7 ，1 8 ，1 9 ，2 0 】) r a n d i 6 已经注意到r 和烷烃的物理化学性质有着 很大的联系。在研究烷烃中，r a n d i 6 引进了r ( g ) ，后来人们称为r a n d i 6 指标他 指出如果g 凰计：按r ( g ) 递减排序，则它们的分支程度是增加的【1 ，1 6 r a n d i 6 指标可用来衡量碳原子结构的分支程度，这个特征关系到分子的表面积，分子的 表面积则相当大地影响有机分子的物理化学性质 从数学的角度，我们首先关心的问题就是在类图中，r a n d i 6 指标的极值是多 少? 达到极值的极图是哪些图? 这两个问题远远没有想象的那么简单，而且往往 极图的结构都是非常有意思的图。许多化学家和数学家都致力研究r a n d i 6 指标的 极值和刻画它的极图，因为这些问题的解决具有很强的应用背景。近几年，r a n d i d 指标在医药方面的应用也层出不穷。 k 悬挂点树关于连通度指标的极值问题研究 本文考虑的是k 悬挂点树关于连通度指标的极值问题在k 悬挂点的n 阶树 中，对于n 3 k 一2 ，这类图的极值与极图已被刻画【1 1 本文主要研究当n 3 k 一2 的具有最大r a n d i 6 指标的极图。我们通过寻找适当的变换研究扎个顶点膏个悬挂 点的树类中，在几 3 k 一2 的条件下，r a n d i 6 指标的极大值和极大图结构。利用我 们所得的性质来逼近极大图的结构特征，可以把一些具有最大的r a n d i 6 指标且有 个悬挂点的n 阶树缩小在惭艮小的集合中，再通过比较将具有最大的r a n d i 6 指标且有七个悬挂点的几阶树找出来 关键词：k 悬挂点树，r a n d i 6 指标，极大树 k 悬挂点树关于连通度指标的极值问题研究 v a b s t r a c t s o m et o p o l o g i ci n d i c e so fam o l e c u l a rs t r u c t u r ec a nr e f l e c ti t sp a y s i c o - c h e m i c a lp r o p e r - t i e s d i f f e r e n tt o p o l o g i ci n d e xr e f l e c t sd i f f e r e n tp r o p e r t i e s t h e ym a k eg r e a tc o n t r i b u t i o n s t ot h es t u d yo fq s p r ( q u a n t i t a t i v es t r u c t u r e - p r o p e r t yr e l a t i o n s ) a n dq s a r ( q u a n t i t a t i v e s t r u c t u r e a c t i v i t yr e l a t i o n s ) t or e s e a r c hi n t ot h er e l a t i o n s h i pb e t w e e nt h es t r u c t u r eo fa m o l e c u l ea n di t sp h y s i c o - c h e m i c a lp r o p e r t i e sb ym a t h e m a t i c a lm e t h o d s ，r e s e a r c h e r sp u tf o r - w a r dt os o m et o p o l o g i c a li n d i c e so fm o l e c u l a rs t r u c t u r ew h i c hr e l a t et oi t sp a y s i c o - c h e m i c a l p r o p e r t i e s t h em o s tw e l l k n o w na r ew i e n e ri n d e x ，h o s o y ai n d e xa n dr a n d i di n d e x am o l e c u l a rs t r u c t u r ec a nb er e g a r da sag r a p hg r a n d i 6i n d e xi sag r a p hi n v a r i a n t d e f i n e da s r = r ( g ) = t 钉 1 w h e r ed a ( u ) d e n o t e st h ed e g r e eo fav e r t e xui nt h eg r a p hg ，a n dt h es u m m a t i o ng o e so v e r a l lp a i r so fa d j a c e n tv e r t i c e so fg i n1 9 7 5 ，i ns t u d y i n gt h ee x t 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 d h y d r o c a r b o n s m i l a nr a n d i 6p r o p o s e da ni m p o r t a n tm 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 g i n d e x t h eq u a n t i t yri 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 s i c o - c h e m i c a lp r o p e r t i e so f m o l e c u l e ，a n dm a k e sg r e a tc o n t r i b u t i o n st ot h es t d u yo fq s p ra n dq s a r r a n d i 5n o t e d t h a tri sw e l lc o r r e l a t e dw i t hav a r i e t yo fp a y s i c o - c h e m i c a lp r o p e r t i e so fa l c a n e s r a n d i 6 f o u n dw h e ng 4 2 n + 2i sd e c r e a s i n gb yr ( g ) ，t h e i re x t e n t so fb r a n c h i n gi si n c r e a s i n g t h e r a n d i 6i n d e xc a nm e a s u r et h ee x t e n to fb r a n c h i n go ft h ec a r b o n - a t o m t h i si n f l u e n c e st h e p h y s i c o - c h e m i c a lp r o p e r t i e so fm o l e c u l e f r o mam a t h e m a t i c a lp o i n to fv i e w ，t h ef i r s tq u e s t i o nt ob ea s k e di sw h i c ha r et h e e x t r e m a lr v a l u e si nc l a s s e so fg r a p l l s ，a n dw h i c ha r et h eg r 印h sf r o mt h e s ec l a s s e sw i t h e x t r e m a lr f i n d i n gt h ea n s w e r si sn o te a s y , a n ds o m e t i m e st h ee x t r e m a lg r a p h sh a v e q u i t eu n u s u a la n di n t e r e s t i n gs t r u c t u r e s m a n yc h e m i s t sa n dm a t h e m a t i c i a n sa r ed o i n gr e - k 悬挂点树关于连通度指标的极值问题研究 s e a r c h e si nf i n d i n gt h ea n s w e r s ，b e c a u s et h e yn o t i c e dt h a tt h e r ei sag o o dc o r r e l a t i o nb e t w e e n t h er a n d i 6i n d e xra n ds e v e r a lp h y s i c o - c h e m i c a lp r o p e r t i e so fam o l e c u l e i ns u b s e q u e n t y e a r sc o u n t l e s sa p p l i c a t i o n so frw e r er e p o r t e d ，m o s to ft h e mc o n c e r n e dw i t hm e d i c i n a la n d p h a r m a c o l o g i c a li s s u e s i nt h i st h e s i s ，w es t u d yt h ee x t r e m a lp r o b l e mo fi n d e xi nt r e e sw i t hkp e n d a n tv e r t i c e s t h et r e e so fo r d e r 礼w i t hkp e n d a n tv e r t i c e sw h i c hh a v em a x i m u mr a n d i 6i n d e xi nt h ec a s e n 3 k 一2w e r ec h a r a c t e r i z e di n 【1 1 w es t u d yt h ec a s en 3 k 2 w eu s es o m ep r o p e r t r a n s f o r m a t i o n st os t u d yt h ep r o b l e mo fe x t r e m a lv a l u e so ft h er a n d i 6i n d e xo ft r e e sw i t h no r d e ra n dkp e n d a n tv e r t i c e s ( n d 产6 ( g ) 且a i = n 定义度序列为d ( g ) = 【d 1 1 ，d ；2 ，舻 ，若口产1 ，为方面起 2 k 悬挂点树关于连通度指标的极值问题研究 见，用d i 代替露通常用t 来表示棵树，即无圈的连通图t 中度为1 的顶 点称为t 悬挂点，连有悬挂点的边称为悬挂边路r 是只有两个悬挂点的n 阶 树星图& 表示有礼一1 个悬挂点的树。彗星是由个星图和条悬挂路组成 对于任意n 且2 n 。n 一1 ，记c s ( n ，n ，) 表示有n ，个悬挂点的有礼个顶点的彗 星即由路r 一。，与n ，+ 1 阶的星图& ，+ 。组成，其中r 一。，的个端点与品，+ 。 的个悬挂点相同。 h a n s e n 和m d l o t 2 ，8 ，2 7 证明了定理1 1 定理1 1 【2 , 8 ，2 7 在有n 1 个悬挂点的礼( n 3 ) 阶树中，若n 1 n 一1 ，则c s ( 2 ，n 1 ) 具有最小r a n d i 6 指标。 给定顶点数和悬挂点数的树类是树中重要的类图定理1 1 实际上证明了该 类树中具有最小的r a n d i d 指标的树。2 0 0 4 年，李学良等 9 给出次小r a n d i 6 指标 及相应极图吴小霞等【1 0 给出了第三小的r a n d i 6 指标及相应极图而对于最大 的r a n d i 6 指标，张莲珠等在【1 1 在礼3 k 一2 ，k 3 ( k 指悬挂点数) 的条件下，用 图的运算和比较的方法确定了r a n d i 6 指标的上确界及相应极图。而在n 3 k 一2 的化学树中，张莲珠等【2 8 也给出了具有最大r a n d i 6 指标的极图与极值。 定理1 2 2 , 9 ，2 7 】令t 是有n 1 个悬挂点的n ( n 3 ) 的树。若n 。 礼一2 并且 t 喾c s ( n ，n 1 ) ，则 即) 瓜+ ( 讵- 2 ) 击+ 竿+ 厄 当且仅当t 是由条长为n 一礼1 + 1 的路v l 坛川“一。，+ 1 v 。一。，+ 2 与个以仇( 任 意i = 3 柚一n ，) 为中心的星图& 1 _ 1 连接而成。 定理1 3 1 0 ，2 7 在有n 。个悬挂点的n 阶树中，由一条长为几一n ，一1 的路 在个端点加上两条悬挂边，另一端点加上n 。一2 个悬挂边组成的树具有第三小 r a n d i 6 指标。 记兀，七= t ：t 是有k 个悬挂点的礼阶树】若树r 有k 个悬挂点且对于 y ( t ) ( t ) 中的任意顶点口，d t ( u ) = 3 ，则称t 为( 后，3 ) 一正则图令露七一 口：t 是在( 七，3 ) 一正则图的每个悬挂边至少加个新的顶点，并且新的顶点数 3 k 悬挂点树关于连通度指标的极值问题研究 4 为n 一2 kq - 2 的图) 定理1 4 【1 1 】对于任意t 兀，k 并且n 3 k 一2 ，k 3 ，有 r ( t ) 互n + 堡堕堡掣 等式成立当且仅当t 譬七 定理1 5 【2 8 若t 是具有k 个悬挂点的礼阶化学树( 4 ) 且钆 3 k 一2 若墅手呈礼 3 k 一2 且k = 4 p + r ( 1 r 4 ) 8 ，贝0 f r ( 丁) 【 费+ 等旁+ 舞+ 呈学+ 专卷+ 面n - - 1 ， 2 n 3 一k o ； 兹+ 譬旁+ 学+ 号手+ 号妾+ 专杀， 等+ 巫矛+ 号岔+ 专杀， 在【2 8 】中也给出了相应的极图，这里不详述。 2 n 3 一k 0 ，n 2 0 ； 2 n 3 一k 0 n 2 = 0 对于r a n d i d 指标，研究的图类还有给定顶点数 2 , 3 ，5 ，9 ，2 7 ，3 0 ，3 1 】，给定顶点数 与边数 3 2 ，3 3 】，单圈图 2 , 5 ，2 7 ，2 9 ，3 2 ，双圈图 2 , 5 ，2 7 ，三圈图 2 , 5 ，2 7 等等。b o l l o b d s 和e r d s s 3 】证明了定理1 6 定理1 6 【2 , 3 ，2 7 令g 是r l , 阶图并且不包含孤立点则 等号当且仅当g 是星图。 n ( a ) “i 1 定理1 6 显然对树也同样成立 定理1 7 【2 ，4 ，5 ，2 7 】令t 是一棵凡阶树，则 r ( t ) 生丝2 二! 且等式当且仅当t 是条路。 定理1 7 是喻平第个证明的随后c a p o r o s s i 等人用另外一种方法也证明了 定理1 。7 ，并且确定了具有第二大r a n d i d 指标的树f 2 , 5 ，2 7 】。 k 悬挂点树关于连通度指标的极值问题研究 定理1 8 【2 , 5 ，2 7 在有n ( n 7 ) 个顶点的树中，度序列为 3 ，2 n ，1 3 】的树具有 第二大r a n d i 6 指标的树 定理1 9 【2 9 】在所有礼( 礼3 ) 阶单圈图中，黠具有最小的r a n d i 6 指标其 中，黠是指在星图& 的两个悬挂点上加一条边得到的图。 定理1 1 0 【5 在n 阶单圈图中，圈瓯具有最大的r a n d i 6 指标。 本文考虑的是k 悬挂点树关于连通度指标的极值问题在k 悬挂点的n 阶树 中，对于礼 3 k 一2 的具有最大r a n d i 6 指标的极图情况复杂，我们从本文第三章 所给的例子就可以看出。本文通过寻找适当的变换研究n 个顶点k 个悬挂点的树 类中，在n 3 k 一2 的条件下，r a n d i 6 指标的极大值和极大图结构性质利用我 们所得的性质来逼近极大图的结构特征，可以把一些具有最大的r a n d i 6 指标且有 k 个悬挂点的n 阶树缩小在个彳艮小的集合中，再通过比较将具有最大的r a n d i 6 指标且有k 个悬挂点的n 阶树找出来 5 k 悬挂点树关于连通度指标的极值问题研究 6 第二章k 悬挂点树关于r a n d i 6 指标的极大图性质 2 1 预备知识 在这一节里，我们首先介绍与本文有关的基本概念、符号和结论，为后面的定 理做准备。以下一些名词和记号参考了【2 , 1 1 ，1 2 ，2 5 ，2 6 】 个图g 是指个有序三元组( y ( g ) ，e ( g ) ，抛) ，其中v ( c ) 是非空的顶点集， e ( g ) 是不与y ( c ) 相交的边集，而惦是关联函数，它使g 的每条边对应于g 的 无序顶点对( 不必相异) 若e 是葫毛边，而u 和v 是使得砂g ( e ) = u i ) 的顶点，则 称e 连接u 和u ；顶点u 和u 称为e 的端点条边的端点称为与这条边关联； 与同一条边关联的两个顶点称为相邻的 g 的顶点u 的度d g ( u ) 是指g 中与仙关联的边的数目 表示g 的顶点的最大度 n c ( u ) 表示由g 中所有与“相邻的顶点组成的集合 k ( g ) = t ，：v y ( g ) ，d g ( v ) = i ) ，n i ( g ) = l k ( g ) 1 e i j ( g ) = e ：e = u e ( g ) ，d g ( u ) = i , d g ( v ) = j i 通常用t 来表示棵树，即无圈的连通图。丁中度为1 的顶点称为t 的悬挂 点，连有悬挂点的边称为悬挂边。 令p 8 = 1 5 0 7 2 1 u 。是t 中的条路，其中d r ( u 1 ) = = d t ( u 。一1 ) = 2 ( 除非s = 1 ) 。若d t ( u o ) = 1 且如( 扎。) 3 ，那么称只是丁的条悬挂链；若d t ( u o ) ，d t ( u 。) 3 ， 那么称只是t 的条内部链 磊，k = t ：t 是有k 个悬挂点的n 阶树) 磊 t = t ：t 是有k 个悬挂点且a = t 的扎阶树) - 树t 的r a n d i 指标定义为冗= r ( 丁) 。三了丽丽1 r t ( ) = 。番丽l ，r m 。z ( 磊，七) = 仇。z r ( f ) ：t 瓦七) k 悬挂点树关于连通度指标的极值问题研究 2 2 七悬挂点树关于l ：t a n d i 6 指标的极大图性质 在本节中，如无特别说明，均大于4 定理2 2 1 1 1 2 】假设t 磊，七并且r ( t ) = 。佤，七) 则2 度点都在悬挂链 上 在【1 2 】中的定理1 证明了：假设丁是k 悬挂点的n 阶化学树，耳具有最大的 r a n d i 指标，则2 度点都在悬挂链上在证明过程中并没有用到t 是化学树这一 条件，因此利用相同的证明可以证得定理2 2 1 定理2 2 2 假设t 瓦，七并且r ( t ) = r 。( 兀，奄) 如果p = u l u 2 一1 是t 中的一条路并且如( u 1 ) = i ，d t ( 岫) = j ，3sj i a ，那么对于任意的l 惫sl ，有 j d 丁( 。七) a 证明：假设u k p ( 2 知f 一1 ) ，d t ( w 七) j ，我们可从p 中选取段路- p = u p u p + 1 u 舢1 w z ( p 1 ) 使得d t ( u p ) j ，d t ( w p + 1 ) r ( t ) 与我们已知的r ( t ) = r 。( 磊，k ) 矛盾 定理2 2 3 假设t 兀，k 并且r ( t ) = j h 。( 瓦，奄) 则或者e 2 2 ( 丁) = d 或者 e 1 3 ( t ) u e l 4 ( t ) u u e l a ( t ) = 0 证明：若e 2 2 ( r ) 彷并且e 1 3 ( 丁) ue 1 4 p ) u ue 1 ( 丁) 仍假设e 易2 ，若 e 1 3 u u e l d ，那么我们可以找到条边u v e 1 3 u u e l ，d t ( u ) = 1 ，d t ( 口) 23 。 7 k 悬挂点树关于连通度指标的极值问题研究 令亍是由t 收缩边e 且在“上加嚎边得到的，这样亍兀m 并且 r ( 亍) 一即) = 一志一丽1 + 丽1 + 砚1 = c 去一南m 一去，2 【砺一丽八1 。砺 0 因此r ( 亍) r ( t ) 与我们已知的r ( t ) = r t l r l 。7 ( 兀，k ) 矛盾 定理2 2 4 假设t 兀，奄并且r ( t ) = r 。( 兀，奄) 则或者岛f ( ? ) = 谚，或者 e 巧( t ) = d ，( 1 t i ，3si j fsa ，t ，i ，歹z + ) 证明：假设e a ( t ) 0 且( t ) 0 ( 1 t r ( t ) 与我们已知的r ( t ) _ j h 。( 兀，凫) 矛盾 定理2 2 5 假设t 兀，七并且r ( f ) = 兄。( 磊，七) 则或者e 1 t ( ? ) = 毋或者 e 2 3 ( t ) u e 2 4 ( t ) u ue 2 ( 一1 ) ( t ) u e 2 t ( t ) = o ( 5 t z x ) 。 证明：假设e 1 t ( t ) 仍且e 2 3 ( t ) u 易4 ( t ) u ue 2 ( t - 1 ) ( t ) u 易t ( 丁) 0 则或者 e 1 ( t ) 0 且e 2 3 ( t ) ue 2 4 ( t ) u ue 2 ( t - i ) ( t ) d ；或者e l t ( t ) 仍且e 2 t ( t ) 0 ( 1 ) ：若e 1 ( t ) 0 且e 2 3 ( t ) ue 2 4 ( t ) u ue 2 c t - 1 ) ( t ) 谚 假设u o u l e 1 f ( 丁) ，d t ( u o ) = t ，d r ( u 1 ) = l ，r o y l e 2 3 ( t ) u u 易( 一1 ) ( 丁) ，d t ( v o ) = 2 ，d t ( v 1 ) _ i ( 3 i t 一1 ) ，n t ( v o ) u 1 ) = 仙 令亍是由r 收缩边u u o 且在u l 上 8 k 悬挂点树关于连通度指标的极值问题研究 加条边得到的这样亍瓦k 且 r ( - ) 一r ( t ) = 一诱1 一而1 一万1 + 砺1 + 孺1 + 访1 = ( 丧v 一1 ) ( 击一去v zv z 0 因此r ( _ ) r ( t ) 与我们已知的r ( t ) = r 。( 磊，k ) 矛盾 ( 2 ) ：若e 2 3 ( t ) u u e 2 ( t - 1 ) ( t ) = 0 ，那么e 2 t 仍。注意到t 的r a n d i d 指标只与t 的边的端点的度有关，因此可以对t 做适当变换变成死使得r ( t ) = r ) ，7 1 瓦m 并且由定理2 2 2 ，五存在顶点u ，屯( u ) = t ，u 1 ，0 j 2 n t l ( u ) ，虹( i z ) 1 ) = 1 ，d 乃( u 2 ) = 2 ，且u 最多只有个邻点的度大于t 一1 令亍，= 7 1 一 u u l ) + u ，u 2 ) ， 这样亍1 兀k 且 令 其中 r ( 亍- ) - r ( 乃) = 一砺1 一蕴1 一丽1 一丽1 ( r t l ( u ) 一1 一去) + 丽2 + 而高+ 击( r 乃( u ) 一1 一击+ 丽+ 了丐丽+ 而( r 乃【u ) 一1 一砺 = ( 丽1 一击) ( 冗n ( 叫) - 1 - - 砺1 ) + 去 1111 + 丽萨荀一砺一面一玩 ( 志一击) ( 祷+ 蕴1 ) + 丽2 111l + ：虿而了主一了秀一丽 m ) = ( 志一去) ( 游+ 蕴1 ) + 丽2 + 而与一砺1 一而1 一万1 = ( t ) 4 - 尼( ) ， = ( 考与一击) ( 嘉砉+ 去) ， = 丽2 + 丽击萄一砺1 一孺1 一丽1 我们知道对于v t z + 0 3 ) 有 ，- ( t ) = ( 了丽1 一丽1 ) ( 了t 丽- 3 + 蕴1 ) 0 9 k 悬挂点树关于连通度指标的极值问题研究 我们有当t 4 时 以( t ) = ( 2 ) 一量+ 互1 一鲁一3 ( 3 t 一3 ) 一鲁 o 那么当t 4 时f 2 ( t ) 是关于t 单调递增的，这样当t 6 时， ，2 ( t ) ，2 ( 6 ) = 丽2 + 击毛一砺1 一去一丽1 。 所以当t 6 时，f ( t ) = ( t ) + ，2 ( ) 0 而当t = 5 时，我们有 ，( 5 ) = 丽1 一丽1 ) 丽2 + 讴1 ) + 丽2 + 丽与一砺1 一砺毛一孺1 。 所以当t 5 时， 邢) = ( 考刍一去) ( 嘉砉+ 蕴1 ) + 丽2 + 丽击面一砺1 一而1 一丽1 。 这样 r ( 亍- ) 一冗( n ) 2 万与一去) ( 去鲁+ 蕴1 ) + 丽2 + 丽击面一砺1 一孺1 一丽1 。 因此r ( 亍，) r ( 乃) 与我们已知的r ( 乃) = r ( t ) = r 。( 瓦，缸) 矛盾。 推论2 2 5 1 假设t 磊，七并且r ( t ) = r m a = ( 兀，k ) ( 5 童7 ) 。则或者e 1 4 口) = o 或者励3 ( t ) u 邑4 ( t ) = 毋 证明：由定理2 2 5 的证明，若t = 4 ，要使得 r ( 亍) 一r ( 乃) 丽1 一丽1 ) 丽1 + 蕴1 ) + 丽2 + 了蓊1一砺1 一万丢一丽1 。， 需7 ，则推论2 2 5 1 得证。 推论2 2 5 2 假设t 兀，知并且兄( t ) = j k 。( 兀，k ) 则或者e 1 a ( t ) = 仍或者 ( t ) = d 证明：由定理2 2 5 ，若t = a ，则或者e 1 ( t ) = 0 或者易3 ( t ) u ue v , = 0 ， 因此推论2 2 5 2 得证。 定理2 2 6 假设t 兀，七并且r ( t ) = r 。( 兀，知) 则或者易。( t ) = o 或者 e i ( t 一1 ) ( 丁) = o ( t 6 ) 1 0 墨墨蕉! 垒煎羞主垄堕蕉! 量叠鱼丝笪塑塑翌窒 1 1 证明：假设易。( t ) 0 且e ，”。) ( t ) d 。注意到t 的r a n d i d 指标只与t 的边的端点 的度有关，因此我们可以通过适当变换将丁变换为死使得r ( t ) = r ( 乃) ，7 1 兀，k ， 并且由定理2 2 2 存在喇t l o 钉l e ( t 1 ) ，血( u o ) = 1 ，d r , ( v 1 ) = t 一1 且u 1 最多只 有个邻点大于t 一2 由于e ，( ) ( t ) 0 ，则由定理2 2 3 可知e 2 2 = 0 ，那么存 在条边u o u l e ( 孔) ，d t , ( u o ) = 2 ，d t , ( u 1 ) = t ，n t l ( u o ) u 1 】= u ) ，d t , ( u ) = 1 令 虿1 = 正一 口o t ，1 + 铷u o ) ，这样芋1 瓦，k 且 令 其中 1111 r ( 一t 1 ) 一r ( t 1 ) 一壶一去一赤一赤( r n ( u 1 ) 。) + 丽2 + 孺1 + 了萄1 ( r 乃( u ，) 一1 )+ 丽+ 了磊+ 而( r 乃( u 1 ) 一1 ) = ( 志一而1 ) ( 兄拍) - 1 ) + 丽2 + 孺12 【了亍三乏一而八“乃【u 1 ) 一1 ) 十丽十了翥 11 1 以届厅 ( 了亍1 三芎一而1 ) 了t 亍- 三3 乏+ 了1 云) + 了2 亏+ 了1 磊( 了亍三芎一而h 了亍三乏+ 了云) + 了亏+ 了磊 111 万丙、厄= 1 。 ，( ) = 丽1 一而1 ) 而t - 3 + 了1 云) + 了2 亏+ 了1 磊一了1 i 一了1 磊一了三彳 = ( ) + 尼( t ) ， 胁( 志一南) ( 满+ 去) 删= 丽2 + 蕊1 一砺1 一瓦1 一击 我们知道对于v t z + o 3 ) ，有 我们有当t 1 时 ( t ) = ( 了前1 一了丽1 ) ( 了t 西- 3 + 诟1 ) 。 尼 ) = ( 2 ) 一吾+ 互1 ( 一1 ) 一量一兰( 3 ) 一耋 o 因此当1 时，如( t ) 是关于单调递增的，所以当t 8 时， 厶( f ) 止( 8 ) = 丽2 + 丽去一历1 一砺丢一万1 。 k 悬挂点树关于连通度指标的极值问题研究 所以当t 8 时，( t ) = ( t ) + 厶( t ) 0 当= 6 ，7 ，我们有 ，( 6 ) = 丽1 一孺1 ) 丽3 + 蕴1 ) + 丽2 + 丽丢一砺1 一砺丢 印) = 丽1 一丽1 ) 孺4 + 蕴1 ) + 丽2 + 丽与一砺1 一高 这样当t 6 时， ) = 而1 一丽1 ) 面t - 3 + 蕴1 ) + 丽2 + 孺1 一砺1 一而1 一志 。 那么 r ( 亍) 一r ( 乃) ( 了弱1 一万1 i ) ( 了t 西- 3 + 蕴1 ) + 丽2 + 孺1 111 以屈师 0 因此r ( t 1 ) r m ) 与我们已知的r ( 冗) = r ( t ) = r m a = ( 兀，七) 矛盾 推论2 2 6 1 ：假设t 兀k ( 5 1 3 ) 且r ( t ) = r 。( 兀，k ) 那么或者 e 2 5 ( t ) = 国或者e 1 4 ( 丁) = 0 。 证明：假设易5 口) d 且e ，4 ( t ) 0 注意到t 的r a n d i 6 指标只与丁的边的 端点的度有关，因此可以通过适当变换将t 变成乃使得r ( t ) = r ( 矸) ，7 1 磊m 并且由定理2 2 2 存在条边v 0 u 1 e ( 噩) ，电( 如) = l ，d n ( 口1 ) = 4 且u 1 最多只 有个邻点大于3 。因为e 。4 ( t ) 仍，有定理2 2 3 可知e 2 2 = 谚存在条边 u o u l e ( 乃) ，d t ，( u o ) = 2 ，d 乃( 乱1 ) = 5 ，矗( “o ) 【u 1 ) = u ) ，d n ( u ) = 1 令t 1 = 乃一 加口1 】+ 舢“o ) ，这样亍1 兀，k 且 r ( t t ) 一r ( n ) 1 以 2 撕 = ( 去一击) ( r n ( 一1 ) + 万2 + 丽毛 l11 一了互一了趸亏焉一丽 丽1 一丽1 ) 万2 + 蕴1 ) + 丽2 + 志 111 一了季一了丽一了i 1 2 o 0 一| 据土厢 一 一 k 悬挂点树关于连通度指标的极值问题研究 注意到1 3 ，所以 r ( 亍) 一兄( 乃) 丽1 一丽1 ) 丽2 + 而1 ) + 丽2 + 丽丢一万1 一志一丽1 。 因此r ( t 1 ) 冗( 乃) 与我们已知的r ( t 1 ) = 兄( r ) = 。( 瓦，k ) 矛盾 推论2 2 6 2 假设t 兀，j c 并且r ( t ) = 碥。( 瓦，七) 则或者易( t ) = d 或者 e l ( a l 】( 丁) = 0 证明：由定理2 2 6 可知，当芝6 时，令t = a ，则有或者如( t ) = o 或者 e l ( 一1 ) ( t ) = 毋当a = 5 时，由推论2 2 6 1 可得易5 ( t ) = 0 或者e 1 4 ( t ) = 0 所 以，当5 时，推论2 2 6 2 得证 定理2 2 7 假设t 兀，七且r ( t ) = r 。( 兀，七) 则或者易。( t ) = 0 或者 e 2 ( t 一1 ) ( t ) = 0 ，( t 6 ) 证明：假设e 2 t ( ? ) 谚且e 2 ( t _ 1 ) ( r ) 0 由定理2 2 4 可知e i ( t - 1 ) ( t ) = 0 ( 3 i t 一1 ) 。由定理2 2 6 ，e l ( t - 1 ) ( t ) = 0 注意到t 的r a n d i 6 指标只与t 的边的端点的 度有关，因此我们可以通过适当变换将t 变换为孔使得r ( t ) = r ( 孔) ，乃兀m 并且由定理2 2 2 存在条边铷分1 e ( 乃) ，电( 哟) = 2 ，d 死( 秽1 ) = t 一1 ，且移1 最多只 有个邻点度大于t 一2 ，其余的邻点度都为2 存在二条边u o u 。e ( 乃) ，d t l ( u 。) = 2 ，电( u 1 ) = t ，地( “o ) 札1 ) = u ) ，d 乃( u ) 2 令亍1 = 噩一 u o 1 】+ o u o 】_ ，这样 一t 1 兀崩且 r ( 一t 1 ) 一r ( 孔) = 一面1 一丽1 一而与一击( r 拍，) 一砺1 ) + 丽1 + 志+ 去+ 志( r 拍) 一砺1 )+ 了焉丽+ 了虿茇专+ 了磊+ 而( r n ( 1 ) 一了重) = ( 志一而1 ) ( r 拍，) 一万1 ) + 志+ 去 11 ，11 、 1 俪钜矿面、以瓶7 狮习可 丽1 一而1 ) 【t 了- f 3 + 了1 云) + 了害告亏+ 去 11 ，11 、 一而一历菥面叫硫一丽卜 1 3 墨墨叁! 鱼塑苤主垒鎏蕉! 量叠盟壑焦塑整翌窒 1 4 令 m ) = ( 志一了丽1 ) 万t - 3 + 蕴1 ) + = f l ( t ) + f 2 ( t ) ， 其中 1 111 1 1 了虿专亏十了蚕一了秀一了趸丽一了雹十丽 ( t ) = ( 了萄1 一了丽1 ) 【t 万- 3 + 蕊1 ) ，丘( t ) = 我们知道对于v t z + ( t 3 ) 1 111 1 1 丽俪俪以矿可以。怕 ( t ) = ( 了前1 一了丽1 ) ( 万t - 3 + 蕴1 ) 。 我们有 疋o ) ：( 2 t ) 一墨+ ( 2 ( 一1 ) ) 一墨一昙( 3 t ) 一墨 o ( t 3 ) 则尼( t ) ( 3 ) 是关于t 单调递增的，所以当t 1 0 时， 丘丘( 1 。) = 志+ 万杀+ 丽1 一砺1 一万杀一志 。 因此当t 1 0 时， f ( t ) = f l ( t ) + 屯( t ) 0 而当t ：6 ，7 ，8 ，9 ，我们有 邢) = ( 丽1 一丽1 ) ( 砺3 + 蕴1 ) + ，( 7 ) = ( 孺1 一丽1 ) ( 砺4 + 诟1 ) + m ) - ( 丽1 一砺1 ) ( 砺5 + 蕴1 ) + ，( 9 ) = ( 砺1 一丽1 ) ( 砺6 + 蕴1 ) + 这样我们就有当t 之6 时 丽+ 而一而 1 一上上 佣网网 1 1 上 佣佣厕 1 l 上 万巧。狮汉百万巧 一了蒸1 一砺1 + 丽1 o ，厕以。锈7 一了丽1 一砺1 + 丽1 。，厕以。锈7 一7 丽1 一万1 + 丽1 。，网讵+ 怕7 一万1 袁一砺1 + 丽1 8 。 、2 、2、3 仲h 志一击，c 蔷+ 去，+ 志+ 去一去一志一砺1 + 矿1 。 k 悬挂点树关于连通度指标的极值问题研究 所以 r ( 亍) 一r ( 乃) 而1 一丽1 ) 万t - 3 + 蕴1 ) + 志+ 去 1 1 r 1 1 、 屈讵矿可、以砺 0 因此兄( 亍，) 冗( 乃) 与我们已知的r ( 乃) = r ( t ) = r 。( 兀，七) 矛盾。 推论2 2 7 1 假设t 兀，七( 1 0 ) 且r ( t ) = r 。( 兀，七) 则或者e 2 5 ( t ) = 0 或者e 2 4 ( t ) = 0 证明：假设忍5 ( t ) 9 且玩( t ) 谚由定理2 2 4 可知晟4 = 0 ( 3 i 4 ) 由定理 2 2 6 1 ，e 1 4 ( t ) 0 注意到丁的r a n d i d 指标只与t 的边的端点的度有关，因此我们 可以通过适当变换将t 变换为乃使得r ( t ) = r ( n ) ，乃磊m 并且由定理2 2 2 存 在条边u o u ，e ( t 1 ) ，d 乃( 如) = 2 ，d t , ( u ，) = 4 ，且 1 最多只有个邻点度大于3 ，其 余邻点度都为2 存在一条边t t o u l e ( 乃) ，d n ( u o ) = 2 ，d t , ( u 1 ) = 5 ，n t , ( t t o ) u 1 】= u ) ，d n ( u ) 2 令亍1 = t 1 一 u o u l ) + v o u o ) ，这样亍1 瓦，七，且 砸) 一r ( 乃) = 一志一丽1 一志一击( r 巾，) 一去) + 丽1 + 志+ 志+ 击( r 拍) 一砺1 ) + 了丐丽+ 了丽+ 了亏更亏+ 丽( r 乃( u 1 ) 一砺 = ( 去一击肥n ( 一砺1 ) + 砺+ 考专 1 1 ，1 1 、一1 揶网、讵锯7 “i 丽 丽1 一丽1 ) 砺2 + 蕴1 ) + 志+ 志 一志一志一c 击一知、厮、厢、以瓶门 注意到a 1 0 ，所以 r ( _ 1 ) 一r ( 乃) 万1 一丽1 )