（运筹学与控制论专业论文）关于树的wiener+polarity指数的最大值.pdf

摘要 图的w i e n e rp o l a r i t y 指数是指该图中两个顶点的距离恰好为3 的无序 点对的数目。本文研究了树以及化学树的w i e n e rp o l a r i t y 指数的最大值及 其极图的特征，主要证明了： ( 1 ) 在所有具有直径d ( d 5 ) 的n 阶树中，w i e n e rp o l a r i t y 指数的最大 值为： ( t ) 一- 【掣j 掣1 + ( 2 n - - d 一4 ) 并刻画了其对应极图的特征5 ( 2 ) 在所有具有k 个悬挂点的n 阶树中，w i e n e rp o l a r i t y 指数的最大 值为： f o ，肛1 ； ( t ) 一= 【孚j 孚 ， k + 2 礼2 k ； 【k 2 - 3 k + n - 1 ，n 2 k + 1 并刻画了其对应极图的特征； ( 3 ) 在所有具有k 个悬挂点的佗7 阶化学树中，w i e n e rp o l a r i t y 指数 的最大值为： ( r ) = n 一3 n 一1 n + 5 k 一1 7 ， 3 n 一1 5 几+ 5 k 一1 8 ， 3 n 一1 6 ， 3 n 一1 5 k = 2 ： k = 3 ： k 是偶数且4 ks ；( n + 1 ) ； k 是偶数且k m a x 4 ，；( 礼+ 1 ) ) ； k 是奇数且5 k 2 n + ； k 是奇数且k = ；他+ i 5 ； k 是奇数且k m a x 5 ，i n + 1 】 关键词：树，化学树，w i e n e rp o l a r i t y 指数，距离 a b s t r a c t t h ew i e n e rp o l a r i t yi n d e x 坼( g ) o fag r a p hg = ( v e ) i st h en u m b e ro f u n o r d e r e dp a i r so fv e r t i c e sm ， o fgs u c ht h a tt h ed i s t a n c ed c ( u ，秽) b e t w e e nu a n d 钞i s3 i nt h i sp a p e r ，t h em a x i m a lw i e n e rp o l a r i t yi n d i c e so fa nt r e e so rc h e m i c a l t r e e so i ls o m es i t u a t i o n sa r eg i v e n ： ( 1 ) i fti sat r e ew i t ho r d e r 礼a n dd i a m e t e rd ( 矗5 ) ，t h e n w p ( t ) 【 佗一d 一1 ，n d 一1 2 “ 2 + ( 2 n d 一4 ) w i t he q u a l i t yi fa n do n l yi fti sa c a p i l l a r yt r e ec 死( 0 ，0 ，x i ，x i + i ，x i + 2 ，0 ，0 ) a n d1 i d 一5 ，x i + x i + i + x i + 2 = 扎一d 一1 ，x i 0 ，x i + 2 0 ，x i + 1 = o rr - d - 1 1 i 丝= 垡= ! i l 2 j ( 2 ) a m o n ga l lt r e e sw i t h 绍v e r t i c e sa n d 后p e n d a n t s t h em a x i m u mw i e n e r p o l a r i t yi n d e xi s = 0 ， 【孚j 孚1 ， 七2 3 k + n 一1 礼= 惫+ 1 ： 七+ 2 n 2 k ； 佗2 k + 1 ( 3 ) a m o n ga l lc h e m i c a lt r e e sw i t hn 7v e r t i c e sa n d 七2p e n d a n t s ，t h e m a x i m u mw i e n e rp o l a r i t yi n d e xi s ( t ) = n 一3 铭一1 n + 5 k 一1 7 3 n 一1 5 n + 5 k 一1 8 3 n 一1 6 3 n 一1 5 ， 七= 2 ； 七= 3 ： 七i se v e na n d4 尼 ( n + 1 ) ； 忌i se v e na n d 七m a x 4 ，；( n + 1 ) ) ； 七i so d da n d5 七；礼+ ； 七i so d da n d 七= ；礼+ ；5 ； 七i so d da n d 七m a x 5 ，i n + 1 ) k e y w o r d s ：t r e e ，c h e m i c a lt r e e ，w i e n e rp o l a r i t yi n d e x ，d i s t a n c e i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识 到本声明的法律后果由本人承担 学位论文作者签名： 萨 f 。寸月够日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权属湖南师范大学，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内容编 人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文 本学位论文属于 作者签名： 1 、保密口， 2 、不保密 年解密后适用本授权书 ( 请在以上相应方框内打“ ”) 胳 导师签名：殳p 双乙 b 淞时影塘 日期：办幻年f 月z ，日 关于树的w i e n e rp o l a r i t y 指数的最大值 1 1基本概念 1 引言 本节给出一些图论的基本术语与符号用g = ( ve ) 表示一个无向 图，其中y 是一个有限集合，e 是y 中元素的某些无序对的集合y 中 的元素称为图g 的顶点，e 中元素称为g 的边通常用y ( g ) ，e ( g ) 分别 表示图g 的顶点集合和边集合，简记为k e m ，吲分别表示图g 的点 数( 又称阶数) 和边数没有重边和环的图叫做简单图本文涉及的图都 是简单图 设u v ，在图g 中与u 相邻的顶点的全体叫做u 的邻域，记作n o ( u ) 称i n o ( u ) i 为点u 的度数。度数为1 的顶点称为悬挂点若在图g 中顶点 u ，v 是连通的，则u ，口之间的距离d g ( u ，口) 是g 中最短( 扎，u ) 路的长g 的 直径是指g 的顶点之间距离的最大值，并记为d i a m ( g ) 。一个图的w i e n e r p o l a r i t y 指数是指该图中两个顶点的距离恰好为3 的无序点对的数目。 不含圈的图称为无圈图，连通的无圈图称为树每个顶点的度数至多 为4 的树叫做化学树。兀表示所有礼阶树的集合，兀，知表示所有具有k 个 悬挂点的佗阶树的集合。厶表示所有佗阶化学树的集合，厶七表示所有具 有k 个悬挂点的n 阶化学树的集合 在一棵树t 的一条路p 中，若其两个端点度数分别为1 和i 3 且其 内部顶点均为2 度点，则称p 为i 度悬挂链；特别地，当p 是一条边时， 称其为i 度悬挂边如果一棵树r 中除一个顶点外，其余顶点的度均为1 或2 ，则称t 为似星树 本文中其它未给出的术语和符号请参阅所引文献，或在使用时会予 以阐述。 硕士学位论文 1 2w i e n e rp o l a r i t y 指数的研究概括 1 9 4 7 年h a r o l dw i e n e r 1 】为了研究无圈分子图给出了w i e n e rp o l a r i t y 指 数的定义，即：一个图g 的w i e n e rp o l a r i t y 指数( g ) 指的是该图中所有 距离恰好为3 的无序点对的数目。在这篇文章中，他还引入了关于无圈 分子图的另一个指数一w i e n e r 指数，即 w ( g ) = d g ( u ，口) ”) y 在 1 】中，w i e n e r 利用一个有关( g ) 和w ( v ) 的线性公式计算出了石蜡的 沸点，由此可见，w i e n e rp o l a r i t y 指数和w i e n e r 指数之间有着很大的联系 关于w i e n e r 指数学者们已经得到了研究结果，比如参考文献【2 - 1 0 ， 1 3 - 1 7 但关于w i e n e rp o l a r i t y 指数 1 8 2 0 】，已有的结果却很少，主要有下面三个 结论： 定理1 1 i n ：对于一棵树t ，有： w p c t ) = ( 如( u ) 一1 ) ( 如( 口) 一1 ) 伽e 定理1 2 【1 1 】：在所有礼阶树中，w i e n e rp o l a r i t y 指数的最大值为 ( t ) 一= 【字j 字1 定理1 3 【1 2 】：在所有n m 7 ) 阶化学树中，w i e n e rp o l a r i t y 指数的最大值 为 ( t ) = 3 n 1 5 本文对树以及化学树的w i e n e rp o l a r i t y 指数做了进一步的研究，得到 了以下结果： ( 1 ) 在所有具有直径d ( d 5 ) 的n 阶树中，w i e n e rp o l a r i t y 指数的最大 2 关于树的w i e n e rp o l a r i t y 指数的最大值 值为： ( r ) 叫掣儿掣 + ( 2 n d 一4 ) ， 并刻画了其对应极图的特征； ( 2 ) 在所有具有k 个悬挂点的死阶树中，w i e n e rp o l a r i t y 指数的最大 值为： f o ，n - - - 一+ 1 ( t ) = 【孚j 孚1 k + 2 几2 k ； ik 2 3 k + n 一1 ，n 2 k + 1 并刻画了其对应极图的特征； ( 3 ) 在所有具有k 个悬挂点的n 之7 阶化学树中，w i e n e rp o l a r i t y 指数 的最大值为： ( t ) 一= n 一3 n 一1 n + 5 k 1 7 3 n 一1 5 佗+ 5 k 一1 8 ， 3 n 一1 6 3 n 一1 5 k = 2 ： k = 3 ： k 是偶数且4 k ；( 佗+ 1 ) ； k 是偶数且k 之m a x 4 ，；( n + 1 ) ； k 是奇数r 5 k 百2 n + ； k 是奇数r k = 2 n + i 5 ； k 是奇数且k m a x 5 ，2 n + l 3 2 具有给定直径的树的w i e n e rp o l a r i t y 指数的最大值 文献【1 1 】中，给出了直径为3 ，4 的扎阶树的w i e n e rp o l a r i t y 指数的最 大值。在这一节，我们将研究具有直径d ( d 5 ) 的礼阶树的w i e n e rp o l a r i t y 指数的最大值，并刻画其极图的特征 定理2 1 若丁是一棵仡阶树，直径为d i a m ( t ) = d 5 ，则 w p ( t ) 【掣j 掣1 + ( 2 r e - - d 一4 ) 等号成立当且仅当t 是一棵毛毛虫树c t ( o ，0 ，戤，z m ，z m ，0 ，0 ) 且 1 i d 一5 ，翰+ x i + i + x i + 2 = 佗一d 一1 ，x i 0 ，x i + 2 0 ，x i + l = 【n - 丁d - i j 或 一, - 2 d - t1 i 为了证明定理2 1 ，我们利用【1 1 】中的一个变换：若t 是一棵t t 阶树， 直径为d i a m ( t ) = d 4 ，p l ( t ) = 1 3 0 y l v 2 v 3 v 4 是r 中一条最长路，则 tov o 表示在丁的基础上去掉边v o v - 并添加边v 0 1 3 3 得到的一棵新树，如 图2 1 所示： 咖u l现 兄( t ) v 0 p l ( t ) 在tov o 中 引理2 1 1 1 1 】若r 是一棵扎阶树，p l ( r ) = r o y l v 2 v 3 v a v d 是? 中一条 最长路，则 ( i ) 当d 5 时，( 丁) w p ( tov o ) ； ( i i ) 当d = 4 时，w p ( t ) w p ( tov o ) 5 一抛 鳓 硕士学位论文 引理2 2 对任意一棵扎阶树t ，若d i a m ( t ) = d 5 ，则一定存在一棵 直径为d 的毛毛虫树r = c 死( z 1 ，z 。，x d 一3 ) ，使得w p ( t ) w p ( t ) ，等号 成立当且仅当t 是一棵类似于t 7 的毛毛虫树，t 如图2 2 所示： x lx 2 - 一、- x d - 4 l - 一 - 。， x d - 3 l ，一一、- 口0u 1耽 铂v d 一3抛一2抛一l 抛 t 7 = c t ( z l ，x 2 ，x d 一3 ) 图2 2 证明：( 1 ) 若r 是一棵n 阶树，兄( t ) = v o v l v 2 v 3 v 4 抛是t 中一条最长 路，如图2 3 所示，设仉= 俐z y ( t ) 一 如，抛) ，d t ( x ，) = d 或由( z ，v o ) = d ) = 缸l ，z 2 ，) d ，令乃= to 仉= ( ( ( t oz 1 ) oz 2 ) ) o 岛，由引理 2 1 ，易证( t ) ) 且d i a m ( t 1 ) = d 咖口l忱 图2 3 一棵直 一2 抛一l 抛 t 径为d 的n 阶树t 广一一一一一一一一一一一一一 v 0 ：口1忱 一一一一一一一一一一1 i l 一一一- 一一一一一一一一一一一一一一一- 一一j 乃 图2 4 乃= to 巩 6 关于树的w i e n e rp o l a r i t y 指数的最大值 ( 2 ) 令而= 矸一【铷，抛) ，如图2 4 所示若d i a m ( t 2 ) = d 一2 5 ，设 u 2 = z i z v ( t 2 ) 一n ( v 2 ) un ( v d 一2 ) ，d t ( x ，v d 1 ) = d 一2 或d t ( x ， 1 ) = d 一2 ， n ( v 2 ) 和n ( v a 一2 ) 分别为忱和抛一2 的邻域令g = t 2ou 2 ，t 3 是在五的 基础上用g 取代正得到若u 2 0 ，由引理2 1 ，易得( t 2 ) 0 因此，m ) w p m ) ，且d i a m ( t 3 ) = d i 可一一? - 广一一一一一一一一一一一一一1 l 蜘：口l 巴一一二一一一一 l 一一一一一一一一一一一一一一一一一一一一一一一一j 乃 图2 5 树码 ( 3 ) 令乃是死的子树，如图2 5 所示，若d i a m ( t 4 ) = d 一4 5 ，对瓦 继续做类似于( 2 ) 中对乃的变换，则最后存在一棵直径为d 的佗阶树使 得其w i e n e rp o l a r i t y 指数大于( 死) ，这样我们就得到了： v 0v lv 2 x l勋 ，- 一 _ i ，、， z d 一4 _ _ z 玉3 _ _ ，- t d 一1 v d v ov lv 2v 3v d 3u d 2v d 1v d = c 瓦( x l ，x 2 ，z d 一3 ) 图2 6 树死和死 7 硕士学位论文 ( i ) 若d 为奇数，则存在一棵类似于死的毛毛虫树，如图2 6 所示，使 得( t ) w p ( t 6 ) ，且z 1 + x 2 + + x d 一3 = n d 一1 ( i i ) 若d 为偶数，则存在一棵树死使得( t ) 0 即( 忍) ( 罨) 而是也是一棵类似于磊的毛毛虫树 下面我们只需研究在所有毛毛虫树c t ( x t ，x 2 ，x d - 3 ) ，( x 。+ z 。+ + z d 一3 = n d 一1 ) 中具有最大w i e n e rp o l a r i t y 指数的树 引理2 3 ：若t = c t ( x 。，z 2 ，x d 一3 ) 是一棵如图2 6 中珏所示的毛 毛虫树，其中z 1 + z 2 + + x d 一3 = 佗一d 一1 ( i ) 若存在i ，j 满足1 z 0 则( t ) 0 ，奶 0 ，x j + l2 = x d 一3 = 0 层pt = c 露( o ，o ，z ，z i + l ，巧，0 ，o ) ，贝0v ( t ) 0 所以，w ；( t ) 0 所以，( t ) 0 ，除了n = d + 1 且 9 硕士学位论文 w p ( t + ) = ( x i + 1 ) + ( 反+ 1 ) ( z 件l + ( z 讳2 + 1 ) + ( d 一6 ) + 1 ) + ( x i + 1 + 1 ) ( x i + 2 + 1 ) = z i x i + l + x i + l x i + 2 + 2 ( 戤+ x i + l + z t + 2 ) + d 一2 = x i + i ( x i + x i + 2 ) + 2 ( n d 一1 ) + d 一2 = g g i + l ( n d 一1 一瓤+ 1 ) + ( 2 n d 一4 ) l 丝= 堡= ! i l2j i 丝= 生= 三i l 2 j ( 礼一d 一1 一【n - 2 d - l j | ) + ( 2 n d 一4 ) n - 可d - 一1 1 + ( 2 仡一d 一4 ) 等号成立当且仅当x i + - = 【t n - d - 1 j 或t n - d - 1 1 ，即p 为一棵毛毛虫树 c 死( 0 ，0 ，x i ，x i + l ，x i + 2 ，0 ，0 ) ， 其中1 i d - 5 ，戤+ z 件1 + z 件2 = n d 一1 ，娩0 ，z 件2 0 和+ 1 ： 或f n - 2 d - 1 1 i 1 0 i 丝= 垡= 三i l 2 j 关于树的w i e n e rp o l a r i t y 指数的最大值 3 具有给定悬挂点数的n 阶树的w i e n e rp o l a r i t y 指数的最 大值 在这一节，我们将研究具有给定悬挂点数的n 阶树的w i e n e rp o l a r i t y 指数的最大值，得到了下面的结论： 定理3 1 若r 是一棵具有k 个悬挂点的几阶树，则 f o ，铊= 砖+ l ； ( t ) = 【孚j 孚 ， k + 2 n 2 k ； i k 2 3 k - 4 - n 一1 ，礼2 k - 4 - 1 首先我们介绍两个在本节中用的比较多的图运算： 若图中的一条边e = t r y 被一条长度为2 的路取代，则称之为将边e 剖 分，此过程中新增了一个二度点w ；其逆过程称之为将二度点w 抹平。如 图3 1 所示： 将w 抹平 图3 1 引理3 1 ：若t 磊，e = t | u 是t 中一条边，且d t ( u ) d t ( v ) ，在t 的 基础上将e 剖分得到r ，则 ( r ) 一( t ) = d t ( v ) - - 1 , 白白如白 硕士学位论文 证明： ( r ) 一( t ) = d t ( u ) 一1 + d t ( v ) 一1 一( 曲( 让) 一i ) ( d r ( v ) 一1 ) 因为d r ( v ) 出( 让) ，引理3 1 易得证 类似地，我们有： 引理3 2 ：若t 五，加是t 中的一个2 度点，设与其相邻的顶点u ，秽 满足d t ( u ) 如( 口) ，在t 的基础上将w 抹平，得到r ，则 唧卜唧，群 出 而 面 d t 引理3 3 ：若t 瓦，e = 钍钞是t 中一条边，且d t ( u ) = p + l 3 ，d t ( y ) = q + 1 3 ，若t ，- 吖e 是将t 中的边e 收缩得到( 如图3 2 所示) 若与 牡， 相邻的顶点的度数均至少为2 ，则( t ) ( r ) 证明：令x = 坼( 钍) 一 口) ，y = 坼( u ) 一 让) 贝0 ( r ) 一( t ) = ( d t ( z ) 一1 ) 0 十q 一1 ) + ( d t ( 耖) 一1 ) 0 + q 一1 ) x e x y e y 一( 如( z ) 一t ) p 一( 白( 剪) 一1 ) q 一触 x e x y e y = ( d r ( z ) 一1 ) ( g 一1 ) + ( d r ( y ) 一1 ) ( p 一1 ) 一粥 x e x y e y ( q 一1 ) p + 0 1 ) q 一加 = p q p q 0 1 2 关于树的w i e n e rp o l a r i t y 指数的最大值 tr = t e 图3 2 下面我们开始讨论含k 个悬挂点的佗阶树的w i e n e rp o l a r i t y 指数的最 大值情况，首先看几种特殊情况： 令t 兀，d i a m ( t ) = d 若k = 2 ，则t 是一条路r ，对于佗4 有( r ) = 佗一3 ，或对于 扎= 2 ，3 ，有( r ) = 0 若k = n 一1 即d = 2 ，则t 是一个星图& ，有( r ) = 0 若k = r t 一2 即d = 3 ，则z 是一个双星图，有w p ( t ) 【譬jf 孚 等号 成立当且仅当t 是一个在两个星图s t - 詈j 与s r - 量 的中心之间连一条边得到 的双星图。 接下来我们只需考虑3 k n 一3 且d 4 的情形，分两种情况讨论： 情形i - k + 3 n 2 k 若t 瓦，且d i a m ( t ) = 4 ，由【1 可知，t 的结构可由仇+ 3 个整数 k l ，k 2 ，乜，1 1 ，z 2 ，l 。表示出来，其中o ( i = 1 ，2 ，3 ) ，m 0 ，如1 ( 1 j m ) ，m 1 ，且 七1 + 乜+ 乜+ f 1 + 1 2 + + z m = n m 一5 1 3 硕士学位论文 结论1 若t 磊，知( 忌+ 3 n 2 k ) 且d i a m ( t ) = 4 ，则 咿， 蒌二搿孺萋； 等号成立当且仅当如= k + 1 一【詈j 或k 2 = k + 1 一墨 证明：由f 1 】1 可知， ( t ) = ( m - 1 - k 2 j r1 ) ( ( 忌1 + 1 + l l + f m + ( 乜- t - 1 ) ) = 【m + 乜+ 1 ) ( 七一晚) = ( 佗一2 一k + k 2 ) ( k 一乜) 因为k + 1 n 2 k ，0 七+ 1 一【鸶j k + 1 一詈 佗一5 ，所以 ( r ) 【孚j 孚 即 c t ， 萋二： ：舅霜萋； 等号成立当且仅当k 2 = 七+ 1 一【詈j 或k 2 = k + 1 一f 詈 结论2 若t 兀，知( 七+ 3 n 2 k ) 且d i a m ( t ) 5 ，则w p ( t ) 了n 2 一佗+ i 证明：由定理2 1 ，易知 w p ( t ) 【兰二 兰j 兰二号兰 + ( 2 礼一d 一4 ) = ，( d ) 朋，= 罱! 嚣：冀二：二三二蠕釜 且，( 5 ) = - 譬- - n - - o r 譬一佗因为，是递减函数，所以，( d ) ，( 5 ) w p ( t ) + ( d t ( z ) 一1 ) ( 如( ) 一1 ) 一( ( 如 ) 一1 ) + ( 出 ) 一1 ) ) + 西( u ) 一1 w p ( t ) + ( ( 出( z ) 一1 ) 一1 ) ( d r ( 可) 一1 ) + ( ( 西( 秒) 一1 ) 一1 ) ( 而( z ) 一1 ) ) + d t ( u ) 一1 w p ( t ) + d t ( 缸) 一1 ( r ) + l ， 矛盾 ( i i ) 若丁中含i 度悬挂边( i 3 ) ，则t 中所有悬挂链的长度至多为2 否则，假设t 中存在一条长度z 3 的悬挂链q ，和i 度悬挂边q 2 ， i 3 将q 。中的一个2 度顶点抹平同时将q 2 中的悬挂边剖分，得到 t 3 五，k 由引理3 2 和引理3 3 可知，( 乃) = ( t ) 一1 + ( i 一1 ) ( t ) ， 矛盾 ( i i i ) t 是一棵记阶似星树且其每条悬挂链的长度至少为2 设n 。= n 。( t ) 表示t 中所有2 度顶点的数目 若n 2 ( ? ) 在丑中 有+ k n 2 1 ) 一2 k = 扎一k n 2 1 条边其两端点度数均大于2 ，将 这些边收缩得到死，则t 5 正七+ 1 知是一个2 七+ 1 阶似星图。由引理3 4 知( 死) 芝) 再将n 一( 2 k + 1 ) 个顶点逐步嵌入死的一条边中得到 死，则t 6 磊，k 为一个礼阶似星树由引理3 2 知m ) w ；( 死) ，因此 ( 死) ( t ) ，矛盾 若n 2 k ，由( i ) 和( i i ) 知t 中所以悬挂链的长度至少为2 若t 不是一 棵似星树，设r 表示t 中两端点度数均大于2 的边的数目，则，- 1 将t 中这r 条边收缩得到乃，则t 7 磊1 七为一个n r 阶似星树由引理3 3 知 ( 码) 1 ( r ) 在乃的一条边中逐步嵌入t 个顶点得到噩，则t s 兀， 1 6 关于树的w i e n e rp o l a r i t y 指数的最大值 为一个n 阶似星树。由引理3 2 知( t s ) ( 乃) ，因此( t s ) ( t ) ， 矛盾故结论4 得证 由结论3 ，结论4 可得本节开头的定理3 1 1 7 4 具有给定悬挂点数的佗阶化学树的w i e n e rp o l a r i t y 指数 的最大值 本节，我们研究具有给定悬挂点数的n 阶化学树中w i e n e rp o l a r i t y 指 数的最大值，用厶表示所有扎阶化学树的集合，厶，七表示所有具有南个 悬挂点的n 阶化学树的集合 若t 厶，具有度序列( r i l l n 2 ，1 2 3 ，佗4 ) ，其中m 表示t 中度为i 的顶点 的个数。因为 佗l + 抛+ n 3 + n 4 = n ，t l l + 2 n 2 + 3 n a + 4 n 4 = 2 n 一2 所以n 3 + 2 n 4 + 2 = n 1 ，因此礼= 2 + t 2 + 2 n 3 + 3 n 4 设蛳表示t 中两端点度数分别为i ，j 的所有边的数目，可知 w p ( t ) = ( 曲( u ) 一1 ) ( d t ( u ) 一1 ) = ( i 1 ) o 一1 ) m 巧 u v e e ( t 1 1 i s j s n 一1 若r 是一棵化学树，则 ( t ) = m 2 2 + 2 m 2 3 + 3 m 2 4 + 4 m a a + 6 m a a + 9 m 4 4 定理4 1 在所有具有七个悬挂点的n 7 阶化学树中，其w i e n e rp o l a r i t y 指数的最大值为 ( t ) = 佗一3 n 一1 n + 5 k 一1 7 3 n 一1 5 n + 5 k 一1 8 。 3 n 一1 6 3 n 一1 5 k = 2 ： k = 3 ： 七是偶数且4 k ；( n + 1 ) ； 后是偶数且k m a x 4 ，； + 1 ) ) ； 堤奇数且5 k ；扎+ ； 七是奇数且k = 亏2 n + i25 ； 忌是奇数且忌m a x 5 ，。2 n + 1 1 1 9 硕士学位论文 为了证明定理4 1 ，首先介绍下面几个引理，其中引理4 1 和引理4 2 的证明类似于引理3 3 引理4 1 若t 厶，e = u v 是r 中一条边，且d t ( u ) d t ( v ) 在t 的 基础上将e 剖分得到r ，则 w a t ) 一w p ( t ) = l ，白( 乱) = 1 ，d t ( v ) = 2 ； 2 ，如( u ) = 1 ，由( 移) = 3 ； 3 ，如( u ) = 1 ，d r ( 口) = 4 ； 1 ，d r ( ) = 2 ，如( 口) = 2 ，3 ，4 ； 0 ，西( 让) = 3 ，d r ( u ) = 3 ； 一1 ，西( u ) = 3 ，d r ( u ) = 4 ； - 3 ，d t ( u ) = 4 ，d r ( v ) = 4 ； 引理4 2 若t 厶，w 是r 中的一个2 度点，且与其相邻的顶点分别 为u ，口，满足如( 乱) 曲( ”) 在t 的基础上将顶点w 抹平得到t ，则 ( r ) 一( t ) = 一1 ，幻( 让) = 1 ，白( u ) = 2 ； 一2 ，如( u ) = 1 ，如( 钉) = 3 ； 一3 ，西( 让) ；1 ，由( 口) = 4 ； 一1 ，如( 乱) = 2 ，d t ( u ) = 2 ，3 ，4 ； 0 ， d r ( u ) = 3 ，d t ( 口) = 3 ； 1 ，如( 让) = 3 ，d r ( u ) = 4 ； 3 ，出( u ) = 4 ，d t ( 口) = 4 ； 引理4 3 设t 厶，七7 ) 具有度序列( t t l ，n 2 ，礼3 ，n 4 ) ，若7 , 3 2 ，且t 中所有的2 度点都在悬挂链中，则存在r 厶，知具有度序列( n ，n 2 + 1 ，n 3 2 ，n 4 + 1 ) 使得( r ) w p ( t ) 证明：因为所有的2 度点都在悬挂链中，所以我们可以选取。，y y ( t ) ，满足d t ( x ) = d r ( y ) = 3 ，且这两点之间不再存在3 度顶点和2 度 顶点设r = t x a + y a ，如图4 1 所示，易得t 厶，七且具有度序列 ( 佗1 n 2 + 1 ，n 3 2 ，佗4 + 1 ) 2 0 关于树的w i e n e rp o l a r i t y 指数的最大值 ( i ) 若x y e ( t ) ，如图4 1 0 ) ，不失一般性，假设d r ( a ) d r ( b ) ，且 d t ( a ) + d r ( b ) d t ( c ) + d r ( d ) ，则 w p ( t 7 ) 一( t ) = 3 ( d ta ) 一1 ) + ( d r ( b ) 一1 ) + 3 + 3 ( d t ( c ) 一1 ) + 3 ( 曲( d ) 一1 ) 】 - 2 ( d r ( n ) 一1 ) + 2 ( d r ( b ) 一1 ) + 4 + 2 ( d r ( c ) 一1 ) + 2 ( d t ( d ) 一1 ) 】 = ( d t ( a ) 一1 ) 一( d t ( b ) 一1 ) 一1 + ( d t ( c ) 一1 ) + ( d r ( d ) 一1 ) = ( d t ( 口) 一出( 6 ) ) + ( 白( c ) + 由( d ) 一3 ) 若d r ( a ) 1 ，则曲( c ) + d r ( d ) 曲( o ) + d t ( b ) 3 ，因此( r ) ( t ) ；若 d t ( a ) = 1 ，因为d r ( a ) d r ( b ) ，n 之7 则白( c ) + d r ( d ) 3 因此( r ) w p ( t ) ( i i ) 否则，我们可选取x ，y ，如图4 a ( i i ) ，注意到z 1 = y 。也有可能出现， 不失一般性，假设d t ( a ) d r ( b ) ，则 ( r ) 一( t ) = 3 ( d r ( 口) 一a ) + ( d r ( 6 ) 一1 ) + 3 + 9 + 3 ( 出( c ) 一1 ) + 3 ( d t ( d ) 一1 ) 】 一 2 ( 靠( 口) 一1 ) + 2 ( 出( 6 ) 一1 ) + 6 + 6 + 2 ( d r ( c ) 一1 ) + 2 ( d r ( d ) 一1 ) 】 = ( d t ( 口) 一1 ) 一( d t ( 6 ) 一1 ) + ( d r ( c ) 一1 ) + ( d r ( d ) 一1 ) = ( d t ( 口) 一曲( 6 ) ) + ( d r ( c ) + d r ( d ) 一2 ) 0 f i g u r e4 1 2 1 硕士学位论文 下面我们开始讨论含k 个悬挂点的n 阶化学树的w i e n e rp o l a r i t y 指数 的最大值 首先看几种特殊情况，令t 厶h 若k = 2 ，则t 是一条长为n 一1 的路r ，因此( b ) = 0 ，当佗3 时 ( r ) = 孔一3 若k = 3 ，贝0n 3 = 1 ，n 4 = 0 且m 1 4 = m 2 4 = m 3 3 = 仇3 4 = m 4 4 = 0 ，0 m 2 3 3 因为m l j = 佗1 = k ，m i j = n 一1 ，m 2 2 + r n 2 3 = n 一1 一k = n 一4 j - - 1i = 1 j = i 所以 c t ，= m 沈+ 2 m = n 一4 + m 妻一1 ， 等号成立当且仅当t 是下图4 2 之一： ll n = 4n = 5 上 扎= 6 竹= 4 ： n = 5 ： n = 6 ； 佗 7 a ) cb 叁j 二苎 图4 2 若k = 4 且n = 5 ，则t 是一个5 阶星图，因此( t ) = 0 若k = 4 且 礼= 6 ，则含4 个悬挂点的6 阶化学树只有两个。易证它们的w i e n e rp o l a r i t y 指数( 丁) = 3 或( t ) = 4 下面我们只需考虑k 4 且n 7 的情况 令g ，奄表示所有具有k 个悬挂点且满足下列条件的佗阶化学树的集 合： 2 2 关于树的w i e n e rp o l a r i t y 指数的最大值 ( i ) t 中至多有一个3 度点； ( i i ) t 中所有2 度点均在悬挂链中； ( i i i ) 若尸是r 中一条两端点均为4 度点的路，则其内部所有顶点均为 4 度点； ( i v ) 若n 2 k ，则t 中既没有4 度悬挂边也没有3 度悬挂边 设t g 具有度序列( 佗1 ，n 2 ，n 3 ，舰) ( i ) 若k 为偶数，则珊= 0 ，由t 中4 度点生成的子图r 也是一棵树， 且m 4 4 = n 4 1 。由 七k + + n 2 砌2 + + n 4 4 n = 。：n2 佗一2 易得砌= n + 1 2 忌，即n 4 = 七一1 ( i ) 若佗2 k ，即k ；( 他+ 1 ) ，则仇2 4 = n 2 ，r n 2 2 = 0 ，且 ( t ) = 3 m 2 4 + 9 m “= 3 h a + 9 ( n 4 一1 ) = 3 n 一1 5 ( i i ) 若勉k ，即尼s ；( 佗+ 1 ) ，则m 2 4 = k ，m 2 2 = 扎一1 一( 七+ m 2 4 + m 4 4 ) = n + 1 一弘因此 坼( r ) = m 2 2 + 3 仇2 4 + 9 仇4 4 = 礼+ 5 k 一1 7 ( i i ) 若k 为奇数，则t 中只含有一个3 度点移，即扎3 = 1 由r 中所有 的3 度点，4 度点生成的子图t 7 也是一棵树且u 是t 中的一个悬挂点， 因此m 4 4 = 绍4 1 ，m 3 4 = 1 ，m 3 3 = 0 由 jk + n 2 + n 3 + 扎唾= k + 砌+ 1 + r t 4 = n 【k + 2 砌+ 3 n 3 + 4 心= k + 2 您+ 3 + 4 佗4 = 2 n 一2 易得n z = 佗+ 一；尼，即毗= 七一i 硕士学位论文 ( i ) 若n 2 k 一2 ，即k i 礼+ 1 ，贝4m 2 4 = 他，m 2 3 = m 2 2 = 0 因此 ( t ) = 3 m 2 4 + 6 m 3 4 + 9 m 4 4 = 3 砌+ 6 + 9 ( n 4 1 ) = 3 n 一1 5 ( i i ) 若n 2 = k 一1 ，即k = i n + ；，则m 2 3 = 1 ，m 2 4 = n 2 1 = k 一2 ，m 2 2 = 0 因此 ( t ) = 2 m 2 3 + 3 m 2 4 + 6 m 3 4 + 9 m 4 4 = 3 n 一1 6 ( i i i ) 若n 2 k ，即k 百2 n + 亏1 ，贝0m 2 3 = 2 ，m 2 4 = k 一2 ，m 2 2 = 佗一1 一( 七+ m 2 3 - _ l - m 2 4 + m 3 4 + m “) = n + 1 一；k 因此 ( t ) = m 2 2 + 2 m 2 3 + 3 m 2 4 + 6 m 3 4 + 9 m 4 4 = 佗+ 5 k 一1 8 综上所述，我们可以得到下面这个定理： 定理4 2 对任意的t g 七( 七4 ，n 7 ) 唧，售： 毙为偶数r 4 ks ；+ 1 ) ； k 为偶数且忌m a x 4 ，；( n + 1 ) ) ； k 为奇数r 5 k 2 n + ； k 为奇数r k = ；n + i 5 ； k 为奇数r k m a x 5 ，i 2 扎+ 1 ) 定理4 3 对任意的t 厶，七，都存在p g 七使得( p ) w p ( t ) 。 证明：( i ) 若t 中存在2 度点不在悬挂链中，令q 表示t 中所有非悬 挂链中的2 度点的集合在t 的基础上将q 中的顶点全部抹平得到丑， 则由引理4 2 可知m ) 一( t ) 一i q i 在乃的基础上将一条悬挂边逐 步剖分俐次得到乃，则t 2 厶，七由引理4 1 可知( 乃) 一( t 1 ) 蚓 因此( t 2 ) w p ( t ) ，即存在t 2 厶，k 满足所有2 度点均在悬挂链中，且 w r p ( t 2 ) ( t ) ( i i ) 若疋中至少存在两个3 度点，则有引理4 3 可知存在t 3 厶，七至 关于树的w i e n e rp o l a r i t y 指数的最大值 多只有一个3 度点且满足( t 3 ) w p ( t ) 。多次利用步骤( i ) 我们可以保 证乃中所有的2 度点均在悬挂链中且不改变其度序列 ( i i i ) 若t 3 厶，七恰好含一个3 度点且所有2 度点均在悬挂链中如果 乃中存在一条路p 其两端均为4 度点，且一个内部顶点为3 度点，如图所 示，令电( 口) = 3 不妨假设p 是最长的一条路，因为v 是唯一的一个3 度 点，则电( 口) ，电( 6 ) ，电( c ) 0 即( t 4 ) ( 乃) ( 1 ) t 3 珊越 图4 3 ( 2 ) t 4 ( i v ) 最后，若n 2 k ，在乃中存在一个i ( i = 3 或4 ) 度悬挂边e ，则存 在一条长度至少为3 的悬挂链p 。在五的基础上，将p 中所有的2 度点 抹平同时将边e 剖分得到死由引理4 1 ，引理4 2 可知( t 5 ) ( 乃) 因此，对任意的t 厶，知，存在p g m 满足( r ) w p ( t ) 由定理4 2 和定理4 3 可得本节开头的定理4 1 2 5 参考文献 【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