（应用数学专业论文）k悬挂边的树的wiener指标研究.pdf

k 一悬挂边的树的 l ，。e r 指标研究 摘要 一个连通图的i i ，7 i e ? l e r 指标是图中所有无序顶点对之间的距离之和。这个概念 是由化学家w i e n e z 于1 9 4 7 年首次提出的。u7 i e n e ? ，指标在理论化学和通讯网络中 有大量的应用。自二十世纪七十年代以来，p i ，i e l t e r - 指标已得到广泛的研究，并得 到了许多新的结果。其中，给定k 悬挂边的树的i v i v e ，r 指标的极值问题的研究 尤其受到关注，近年来，e n t r i n g e r 得到了下面的结论( 2 】：如果t 是阶数为n ， k - 悬挂边的树， 2 知n ，那么( s ( 扎天) ) s ( ? ) ( d ( 丌，ii ki ，1 j ) 。当 ，兰s ( n ，k ) 时取到下界；当丁垒d ( n ，j i ，嘲) 时取到上界 我们很自然地想了解阶数为n ，k 一悬挂边的树的i e n e r 指标的第二大值问 题。本文作了这方面的研究全文分为三章。第一章，我们给出一些基本概念和 研究进展。第二章，我们从分析树的变换与i e n e r 指标的关系入手，将寻求具有 第二大w i e n e r 指标的树的集合缩z j , n “毛虫”树的范围内讨论。接着，应用分块 计算w i e n e r 指标的方法得出“毛虫”树的一般解析表达式，分析了移边变换时， 树的w i e n e 7 指标的变化规律，进而确定了第二大“7 i e n e ，指标的数值以及达到第 二大w i e n e r 指标的树的结构第三章，我们给出第三大w i e n e r 指标的树的若干 性质以及一些特殊树类依w i e n e 7 - 指标的序关系。 关键词：树，k 一悬挂边，w i e n e r 指标 k 一悬挂边的树的l i ，i c n c r 指标研究 a b s tr a c t l v t h ew i e n e ri n d e xo fag l a p hi sj u s tt h eb u n lo fd i s t a n c e sb e t w e e na l ln n 0 1 d e r e dp a i r so f v e r t i c e so ft h eg r a p ht h i sc o n c e p ti sp u tf o r 、r a r db yt h ec h e m i s tw i e n e ri n1 9 4 7f o rt h ef i r s t t i m e t h ew i e n e ri n d e xi sw i d e l ) ，u s e di nt h ef i e l d so fc h e m i s t r ya n dc o m m u n i e a t i o nr l e t w o l k a n dh a sb e e ne x t e n s i v e l ys t u d i e ds i n c et h em i d d l eo f1 9 7 0 s m a n yn e wr e s u l t sa r eo b t a i n e d i tm a yb ee s p e c i a l l yi n t e i e s t i n gt od e t e r m i n et h et r e ew i t he x t r e m a lw i e n e ri n d e xi na l lk p e n d e n tt r e a s r e c e n t l ye n t r i n g e ro b t a i n e dt h ef o l l o w i n gr e s u l t ：i fti sat r e eo fo r d e rnw i t h kp e n d e n tv e r t i c e s ，2 是n , t h e nw ( s ( n ，是) ) sw ( r ) w ( d ( n ，【钊，f ；1 ) ) t h el o w e r b o u n di sr e a l i z e di fa n d o n l yi ft 兰s ( n ：忌) a n dt h eu p p e ri fa n do n l yi ft 掣d ( 凡，【j ： w ea r en a t u r a l l yc u r i o u st ok n o wt h et r e e ( s ) w i t ht h es e c o n dm a x i m u mw i e n e ri n d e x i n a l ik - r p e n d e n tt r e e s t h ep a p e rc o n t a i n st h r e ec h a p t e r s i nc h a p t e r1 w ei n t r o d u c es o m e n o t a t i o n sa sw e l la ss o m ek n o w nr e s u l t so fw i e n e ri n d e xo ft r e e s i nc h a p t e r2 i no r d e rt o d e t e r m i n et h et r e e ( s ) w i t ht h es e c o n dm a x i m u mw i e n e ri n d e xi na l lk - p e n d e n tt r e e s ，f i r s tw e a n a l y s et h er e l a t i o n sb e t w e e nt h ew i e n e ri n d e xa n dt h et r a n s f o r m a t i o no ft r e e s ，a n dr e d u c e t h es e to ft h et r e e st ot h es e to fc a t e r p i l l a r 。t h e nw ef i n dt h er e e u r s i o no fw i e n e ri n d e xo f c a t e r p i l l a r ，a n da n a l y s et h ec h a n g el a wo ft h ew i e n e ri n d e xo ft h et r e e su n d e re d g e m o v i n g t r a n s f o r m a t i o n t h e r e b yw eo b t a i nt h et r e e ( s ) w i t hk - p e n d e n t ，w h i c hr e a c h ( s ) t h es e c o n d m a x i m u mw i e n e ri n d e x ，i nc h a p t e r3 。w eo b t a i ns o m ep r o p e r t i e so ft r e e sw i t hk p e n d e n t w h o s ew i e n e ri n d e xr e a c ht h et h i r dm a x i m u ma n d8 0 m eo t h e ro r d e r i n gr e l a t i o n s k e y w o r d s ：t r e e ，k - p e n d e n te d g e ，w i e n e ri n d e x 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研 究成果。本人在论文写作中参考的其它个人或集体的研究 成果，均在文中以明确方式标明。本人依法享有和承担由 此论文而产生的权利和责任。 声明人( 签名) ：泄攘埠 9 譬年占月日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部l 、- 1 或其指定机构送交论 文的纸质版和电子版，有权将学位论文用于非赢利目的的 少量复制并允许论文进入学校图书馆被查阅，有权将学位 论文的内容编入有关数据库进行检索，有权将学位论文的 标题和摘要汇编出版。保密的学位论文在解密后适用本规 定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( u ( 请在以上相应括号内打” ” 作者签名：湛夔j i 牟 导师签名： 日期： 日期： ) ov 年占月日 毋年多月占日 是一悬挂边妁树的； i e n e r 指标研究 第一章引言 1 1 分子图与l l j e 能，指标 图论已广泛应用于诸多学科领域，如计算机科学、通讯工程、物理学、工业管 理，心理学及社会学等，但是重要的应用领域应首推化学学科。在化学中，已有的 应用涉及合成化学、聚合化学、量子化学及化学信息的存储和检索等。近年来， 最大量的应用集中在定量结构一活性性质相关性( q s a r q s p r ) 的研究方面。 当今，在生物学，药物学、毒物学和环境科学中个很重要的发展趋势是将分 子生物滑眭性质的定量预测用于分子设计据估计，大约从1 0 0 0 0 个化合物中 才能够筛选出个作为有效药物投入临床使用。以往凭经验由母体化合物衍生同 源化合物的效率很低，因而促使人们去寻找更优的方法和途径来泡制新药与此 类似，在工业和环境科学中，每年要测试( 毒性、致突变、致癌等) 和处理的化合 物多达数十万种，若仅靠实验将耗费极大的人力物力，所以必须有新的方法才能 满足客观需要q s a r q s p r 方法为我们提供了一条可行的途径目前已涌现出 了诸多q s a r q s p r 方法，其中图论方法有其独特的优点，因为这类方法仅依赖 于分子结构，即由结构图就可以直接衍生结构特征拓扑指数就是从化合物的结 构图衍生出来的一种数学不变量。 众所周知，分子是由原子组成的，任何两个原子之间可以形成化学键，也可以 不成键。由于分子l 直在做无规则的运动，如分子的振动，使得分子中原子的位 置会发生变化还有，周围环境的影响，比如温度，压力的变化等也会引起分子 的几何性质发生改变但是，重要的是，分子的内部运动和所受的外部影响并没 有旧键的破坏或新键的形成。换句话说，在这些形变过程中，尽管分子的几何陛 质会发生改变，分子中原子之间的相互关联的性质并没有改变。分子中原子相互 连通的全部信息确定了分子的拓扑性质分子的拓扑性质屉分子在内外因素连续 变化过程中始终保持不变的几何陆质，它是分子的固旮隆质之一f 2 j 2 。 正因为分子具有这种固有的拓扑性质，不同的分子结构对应着不同的拓扑性 质，不同的拓扑性质对应着分子不同的物理化学籽陛。因此，人们就想用图来表 惫悬挂边的树的1 1 。i e r m r 指标研究 2 示分子的拓扑结构，于是，- - l q 新兴的学科 化学图论诞生了。 在化学图论中，我们可以用个图来描述分子的拓扑结构，即用顶点表示原 子，边表示键，该图就称为分子图。分子图表达了分子的拓扑性质，它的结构特 征反映了其相应化合物的结构特征。如果两个分子中的原子之间具有相同的连通 性质，或者说，它们具有相同的分子图，那么就可以说两个分子的拓扑性质是相 同的。我们把在分子图中不依赖于顶点的标号方式的量叫做分子图的不变量。例 如图的顶点数，边数等都可以作为其不变量。分子图的各种不变量不但可以定量 的描述分子的结构，而且可以分析相关分子图的结构与性能之间的关系。通常把 具有这种作用的分子图的不变量l f 做分子图的拓扑指标 化学界经常会遇到计算某分子图的拓扑指标值，从而统计的估计相对应的分 子的某种物理或化学性质。同时也会遇到其逆问题，即想合成具有某种活性的化 合物，我们可以借助图论这个有用的工具，得到相应的分子图，使得分子图的拓 扑指标值为某个具体值或者在某个域内，这就是求给定分子图的拓扑指标值的逆 问题 现在，这种逆间题的研究越来越多，如组合化学的个中心问题就是寻找具有 某种物理或化学陛质的分子。为了得到所期望的分子，首先要得到这种分子的拓 扑指标，然后利用计算机搜索，建立具有这种指标值的分子图的数据库，最后在 库中选择最理想并且能够合成的结构去合成它们。因此，该问题的深入研究对有 目的合成一j 竖分子或药物有指导作用，具有重要的理论价值和应用前景 w i e n e r 指标( 有时也称为w i e n e t 数) 是目前化学界公认的第一个分子拓扑指 标，它由美国化学家w i e n e r 1 3 1 于1 9 4 7 年首次提出，用来估计化合物链烷的沸点。 在【1 3 】中w i e n e r 得到了个依赖于链烷分子图( 即一棵树) 的值，这就是后来的 w f e n e r 指标，并且给出了w 与链烷沸点( b p ) 之间的个关系式： b p n i 矿+ ，p + 1 这里n 3 与7 为经验常数，p 为分子图中距离为3 的顶点对的个数。 此后，”i e n e r 指标就成为化学图论中一个很重要的术语，成为用图的理论建 立分子模型时最频繁使用的概念之一。与之密切相关的另一个慨念 平均距离， 惫悬挂边的树的i i r i 州e r 指标研究 3 表示图中所有无序顶点对之间距离的平均值。这一概念被用于计算机系统连通方 面及通讯网络的分析和设计中。总之，这两个概念作为图的重要参数已得到了广 大图论工作者的重视和广泛研究。 1 2 基本概念与术语 我们在本小节中给出本论文将会用到的术语以及一些重要概念。 一个图是指个有序三元组( 矿( g ) ，e ( g ) ，妒g ) ，其中y ( g ) 是非空的顶点集， e 【g - ) 是不与、7 ( g t ) 相交的边集，而砂g 是关联函数，它使g 的每条边对应于g 的 无序顶点对。若e 是条边，而“和掣是使得抛( e ) = 牡 的顶点，则称边e 连接 顶点和u ，顶点u 和u 称为边e 的端点。 一条边的端点称为与这条边关联，反之亦然与同一条边关联的两个顶点称 为榴邻的；与同一个顶点关联的两条边也称为榴邻的端点重合为点的边称为 环，端点不相同的边就称为连杆 个图称为有限的，如果它的顶点集和边集都有限。只有一个顶点的图称为平 凡图，其它所有的图都称为非平凡图 个图称为简单图，如果它既没有环也没有两条连杆连接同对顶点 对于图g 的两个顶点u 和 ，如果在g 中存在条从u 到t ，的通路，则称 札和掣是连通的如果图g 任意两个顶点都是连通的，则称g 为连通图条通 路t ，。砚的长度为i 2 n 也就是这条通路中边的数目。 设图g 中顶点u 和u 是连通的，则从u 到u 的最短通路的长度就称为豇到 w 的距离，记为d g ( u ，u ) ( 或简记为( f ( u ，口) ) 对连通图g 的两个不相交的顶点集合 a b ，我们定义w ( a ：b ) =d g ( n ，6 ) 。特别地，当a 中只有一个元素n 时， 我们记w ( a 召) 替代w ( 口 ，b ) ，当日中只有一个元素时同样处理。 设口y ( g ) ，则g 一掣表示从g 中删去 及与这个顶点相关联的全部边所得 到的子图。设e e ( g ) ，则g 一。表示从g 中删去边e 所得到的图。 设图g 为顶点数为，t 的连通图，对于任一。专( g ) ，我们称e c ( v ) = ，丸船 如z ) z y ( g ) ) 为顶点u 的离心率。由此我们定义一个连通图g 的半径，( g ) = m 讥 e c ( z 圳 l ，1 7 ( g ) ) ，直径d ( g ) = m a x e c ( 。) lu v ( a ) ) 。 是悬挂边的树的l l i e l e r 指标研究 4 对于r v ( ， ) ，则，在t t 的分枝指的是j ，中包含t 并以其为悬挂点的极大 子树；而分枝b 的重量b i i 了( b ) 指的是b 中的边数；点t 的分枝重量b w r ( v ) 指 的是在掣的各个分支中最大的重量。而一棵树y 的质心( c e n t r o i d ) 则是，中具有 最小分枝权重的点的集合，我们用c ( 丁) 来表示。 给出图g 中的点u ，与其相邻的点集记为n g ( u ) ，顶点的度d g ( t ，) 是指g 中 与u 关联的边的数目。即顶点的度( f g ( u ) = 1 ( 口) l 。度等于1 的顶点称为悬挂点。 树是无圈连通图，树7 的顶点集和边集分别记作y ( t ) 和e ( 丁) ；树r 的顶点 数用，( 丁) 表示，称为丁的阶，即i v ( t ) i = n ( t ) 树有以下固有的性质：i e ( t ) i = 扫( ? ) 一1 阶为n 的树中，至少有两个悬挂点，至多有诧一1 个悬挂点。悬挂点为 2 的树称为路，记为r ；悬挂点为n 一1 的树称为星图，记为岛树r 中，度 大于3 的顶点称为分枝点。路r 是唯一的没有分枝点的树。 我们构造图尾如下： 设一条路p n 一。= u 。可：u 。一， 为一孤立顶点，我们连接顶点u 和顶点( 2s zsn 一2 ) ，由此形成的图，我们称为尾一， 对任意个实数z ，f z 是指不小于z 的最小整数，而m 是指不大于z 的 最大整数。其他未加予说明的术语和符号均引自文献 5 j k 悬挂边的树的t l i e n e r 指标研究 1 ，3 树的1 1 泐e r 指标的极图研究进展及本文主要结果 自从1 9 4 7 年，e r 指标问世之后，它就成为科学家们手中的重要工具。六 十年来，科学家们利用该指标在统计化学、结构化学，有机化学以及药物等方面 的研究活动一直没有停止过。经过长期的研究，科学家们发现很多化合物的物理 和化学性质与它们的拓扑性质密切相关。 w i e n e r 指标就是个与化合物的物理 化学性质密切相关的拓扑指数，所以对这一指标的研究也日趋重视化。数学家对 下面两个问题很感兴趣： ( 1 ) 图的w i e n e r 指标与图的结构究竟是怎样的依赖关系。 ( 2 ) 如何有效的计算图的w i e n e r 指标，尤其是不利用计算机的情况下( 即所 谓的“纸笔方法”) w i e n e r 指标被广泛应用到描述分子结构，其中确定具有最大和最小w i e n e r 指 标的树的研究尤其受到关注。对于给定一些参数的树的w i e n e r 指标极值问题的研 究是个熟点问题【2 0 ，2 2 ，2 3 ，2 4 ，2 5 】，在某些给定的图类中找出具有极端i e n e r 指 标的图的结构问题，在化学上和数学上都有很大的意义，并且在这方面已经有许 多结果1 2 , 3 ，6 ) e n t r i n g e r ，j a c k s o n 和s n y d e r 在【7 】中首次提到关于路r 和星图岛的w i e n e r 指 标的解析表达式： w ( r ) = 碟+ 3 ，仉7 ( 晶) = ( 礼一1 ) 2 并且在同一篇文章中也证 明了在所有阶为n 的树中，w i e n e t 指标最大的是路r ，最小的是星图 定理1 3 1 1 0 】( a ) 如果t 是棵阶为n 的树，那么，对于所有的整数n ( n 之1 ) ， 彤( 咒) sw ( t ) 缈( r ) ( b ) 如果t 矗 又，r ) ，那么，对于所有的整数扎( 扎5 ) ， ， 彤( r ) 彤( r ) l 矿( b ) 但是上述结果是比较平凡的，没有考虑到其他的一些相应条件，并且这个应用 的范围也比较窄，化学家与数学家们对这样的结果并不满意，于是进一步的研究 是很重要的。f i s c h e l = l l | 1 1 h u m n 3 l i n t r a u t e n l j a 。h s z e k e l y 和v o l k m a n n 等人在【8 1 中给 k 一悬挂边的树的i i i e n e 1 r 指标研究 出了另外一个比较重要的结果：在给定树- 阶数 和最大度的条件下，1 1 i e n e r 指标最大和最小的树的形状。而t r i c s c h 在【9 中对上述间题中最小的i i 妇n e r 指标 的树的结构给出了另外一个独立的证明。陈德勤在【1 8 】中对f 3 i n ) 图类w i e n e r 指标的极小值问题进行了研究，给出这一类图的一般构造办法。郭晓峰，董哈微 在文章f 6 1 中定义了缩边增长变换以及移边变换，从而给出了1 对的1 1 7 i e n e r 指标的 一个最小排序，得到了i e r t e7 指标最小的1 5 棵树 6 】。 记顶点数为n 的树的集合为z 。 定义1 3 2 【6 】设t 矗，t 1 3 ，e = “。是树，的非悬挂边，i 一e 的两分 枝分别记为了j ，鲍也m 1 ，可疋。是通过以下方式由z 1 得到的图： ( 1 ) 收缩边e = 1 l - 1 ( 2 ) 在u ( = 掣) 上增加条悬挂边。 过程( 1 ) 和( 2 ) 称为树t 关于边e 的缩边增长变换若t 通过一步缩边增长变换 变为t o ，这个变换记为t 一( 如图1 3 1 所示) 定理1 3 3 【6 】设t 矗，绝之3 ，且设丁至少有条非悬挂边如果树r 通 过步的缩边增长变换变为树，那么w ( i r o ) w ( z 1 ) 缩边增长变换使树，的i e n e r 指标变小，且悬挂边数增加1 ，非悬挂边数 减少了1 它破坏了七一悬挂边的条件。 在一条路r 一。一。上，把n 个独立的顶点邻接到其中一个端点上，把6 个独立 的顶点邻接到这条路的另一个端点，这样得到的图我们记为d ( 亿o ，6 ) ( 如图1 3 2 所示) ；而图s ( n ， ：) 指的是这样的树：它恰好有一个中心不妨设u 有7 n ( 3 曼，n 墨 扎一i ) 个分枝， r 的每一个分枝是长为l j 或f 2 1 的路。在l g g g 年e n t r i n g e r k 一悬挂边的树的i l - i e n e r 指标研究 得到了下面的结论【2 】 7 d ( n ，n ， 图1 3 2 - 定理1 3 4 1 1 ，2 ，3 l 如果t 是阶数为虬 k 悬挂边的树， 2sk n ，那么 w ( s ( n ，惫) ) s 彤( 丁) w ( d ( n ，【j ，f ) ) 。当t 兰s ( n ：七) 时取到下界；当t 竺 d ( n ，l j ， 1 ) 时取到上界。 本文研究的是k 悬挂边的树的w i e e r 指标的极图，树的变换必须保持k 一悬 挂边不变这条件本文采用标准的图论语言对顶点数为n ，悬挂边为是的树的 w i e n e r 指标的极值问题进一步研究在第二章，我们从分析树的变换( 保持k 悬 挂边不变) 与w i e n e r 指标的关系入手，将寻求具有第二大w i e n e r 指标的树的集 合缩小到“毛虫”树的范围内讨论接着，应用分块计算w i e n e r 指标的方法得出 “毛虫”树的般解析表达式，分析了移边变换时，树的w i e n e r 指标的变化规 律，从而给出了树的w i e n e r 指标的第二大值以及达到第二大w i e n e r 指标的树的 结构。在第三章，我们给出第三大 i e n e r 指标的树的若干| 生质以及一些特殊树类 依w i e n e r 指标的序关系。 我们定义图d + ( n ：s ：t ，z ) 如下： 在条路r 州一，上，记路的长f = 钉一1 一s t 一1 ，将路的顶点从左向右重 新标号为仍m ，1 j z 把s 个独立的顶点邻接到这条路的左端点u o 上，把t 个 独立的顶点邻接到这条路的右端点埘，剩下的一个独立的顶点邻接到路中的某一 个顶点f 。( z ( d f ) ) 上，这样得到的图我们记为d ( n s t ：t ) ( 如图1 3 3 所示) ! ：墨堡望! ! 塑! ! ! ! 立翌曼! i i 堡堕窒8 本文的主要结果是； d f r ，5 ，f ，。j 图1 3 3 定理1 3 ，5 设丁是阶数为，t ，k 一悬挂边的树，若k 三1r o o d ( 2 ) ，则阿( 2 1 j 取 到第二大值h ( ? ) = ( 七一1 ) 2 + c f + 2 a + 掣+ 坐弘f + ( 七一1 ) 。2 一地+ 2 当且仅当 t 兰d ( n ，宁- 譬，】) ；若k 兰0r o o d ( 2 ) ，则( 丁) 取到第二大值( t ) = 七2 + ( 譬一 1 ) z + c 冉2 + 七峄当且仅当t2 d ( 竹，鲁+ 1 ，互k 1 ) 或t 星d 。( 九 ， 一1 ，j 1 ) 走悬挂边的树的i e ，l e r 指标研究 9 第二章具有第二大w i e n e r 指标的尼一悬挂边的树 2 1 预备知识 在这一节里，我f 1 首先介绍与本文有关的定义和结论，为后面的讨论作准备 定义2 1 1g 是一个连通图，其中y ( g ) 是图g ! 的非空顶点集，e i g ) 是图g 的边集，则我们定义图g 的w i e n e r 指标为1 1 ( g ) =d a ( u ， ) 。 “，t ，扩( g ) 其中南( 垃，u j 表示连通图g 中两个顶点乜和。之闯的距离，和式取遍g 中所 有的顶点对。 定义2 1 2g 是个连通图，d 为图的直径，丑表示距离为i 的顶点对个数， 则图g 的w i e n e r 指标可表示为w ( g ) = 妻j 韪 设t 是一棵阶为n 的树，e 的两端点为t 和y ， n l ( e ) = l l y ( t ) ，d t ( 掣：z ) d t ( 掣，可) l - 2 ( e ) = i t ，f 妒矿( 丁) ? d t ( 2 ，13 ，) ( 红( 口，工) ) l 1 9 4 7 年，w i e n e r 得到了计算顶点个数为n 的树的w i e n e r 指标的另个较直 观简便的计算公式； 定理2 i 3 6 l 设r 是一棵树，e e ( ? ) ，扎l ( e ) 和扎2 ( e ) = n n l ( e ) 分别是 r e 的两分枝的顶点数，那么( t ) = n l ( e ) n z ( e ) e e ( r ) 从w i e n e r 指标的定义我们可以看出；对于一般图，即使是树来讲，给出w i e n e r 指标的解析表达式是比较困难的，目前人们只给出了少数几个图类的解析表达式， 最著名的有路图r 和星图& ( p n ) = 暖+ 3 ，w ( 既) = ( n 一1 ) 2 本文的研究对象是树t ( t r e e ) ，树中任何一对顶点仅由唯一的路( p a t h ) 所连， 从而可以简化所研究的问题。给定顶点数为悬挂边为惫的树，记非悬挂边数等 于f ，则f _ ( 一1 一惫。排除路图和星图后，f 的取值范围为：f 1 n 一4 j 。阶 为n 的树中，至少有两个悬挂点，至多有，t 一1 个悬挂点。因此， ：的取值范围 为： ：【2 ，t 一1 】当k = 2 时，即悬挂点为2 的树，称为路，即为r ，在同构意 k 悬挂边右寺 树的1 , 1 i e n e r 指标研究l o 义下是唯一的；当k = 一1 时，即悬挂点为n 一1 的树，称为星图，即为s 。，在 同构意义下是唯一的。因此，本文实际所讨论的k 的取值范围为：k f 3 ，”一2 】 我们记顶点数为九，悬挂边为k 的树的集合为= f j 。给定n 和走，由l = ，( t ) 一1 一七，我们可以计算出f 的值。以下，我们依非悬挂边数进行分类讨论。 k 一悬挂边的树的1 1 t i e n 盯指标研究 1 l 2 ，2 七：n 一2 的树 由于1 = n ( = f 1 ) 一i 一 ，当k1 时，k = 竹( r ) 一2 。此时，树的结构如图2 2 1 所示。 砭。 图2 2 1 如果k = 3 ，没有不同构的树。因此，k 之4 而且我们发现，n 6 时，没 有不同构的树，因此。n 6 令z = 1 时的树的集合为t 球1 这里s + l = 砖一2 ， l s ，s 狂一3 我们发现，这种类型的树的w i e n e r 指标很容易计算。 由定理2 1 3 ，有t ) = ( n 一1 ) ( n 一2 ) + ( s + 1 ) ( t + 1 ) 其中，5 + t = i ： 弱( 瓦，) = ( 彀一1 ) ( 丸一2 ) + ( 七一+ 1 ) ( t + 1 ) =( 视一1 ) 一2 ) + k + 1 + k t 一2 = 卜1 ) ( n _ 2 ) + 是+ 1 + 等邓一鲁) ： 由上式可知，在树的悬挂边k ，顶点数扎给定的前提下，彤( 瓦，。) 是关于t 的 二次函数在t 互k 时，彤( 瓦，。) 单调递减。 由以上讨论，我们得到了以下结论 定理2 2 1 设t 砭。，s 斗= k 。如果k 兰1 ( r o o d 2 ) ，则m7 ( ”取到第二大值 缈( r ) = ( n 1 ) ( n 一2 ) + 百k 2 + 后一i 5 当且仅当丁叁砭一1 ，孚+ 2 ；如果七- - 0 ( m 口d 2 ) ， 则( t ) 取到第二大值印1 ) = ( 咒一1 ) ( n 一2 ) + 譬+ 当且仅当t 竺y 善吐鲁+ ， 悬挂边的树的1 1 r i e n e r 指标研究 2 。3 壳：，t 一3 的树 当f ：2 时，_ i = = n ( 一3 。此时，树的结构如图2 3 1 所示。特别地，当s = 0 时，树的结构如图2 3 2 所示， 2 “ 图2 3 1 巧“ 图2 3 2 其中k23 ，n 之6 令f - 2 时的树的集合为碍这里r + s + t = 九一3 。 r t21 , s20 。我们同样发现，这种类型的树的i , v i e n e ，指标很容易计算 由定理2 1 。3 ，我们可得( 譬“) = ( n 一1 ) ( n - 3 ) + ( r + 1 ) ( n - r - 1 ) + ( t + 1 ) ( n - t - 1 ) 在某非悬挂顶点的度给定的条件下，郭晓峰、董哈微得到了蟹。，。依w i e n e r 指标的序关系 定理2 3 1 【6 】当0sss 竹一5 ，叠中依i e n e r 指标的序关系由下式给出： w ( 了z 8 i n i 4 一，) w ( 磋咿一5 s ) ( 停川芈1 ) 定理2 3 2 6 1 当1 曼ts 【鸶，t 2 。中依w i e n e r 指标的序关系由下式给出： 渺( 理。一州t ) 彤( 噬。一5 吒) 彬( 磕1 , n - - 4 - - 2 t , t ) = 彬( 砰一3 _ o ，f ) 矿( 丁) 由推论2 2 4 我们可以知道：取定树的任含有与一度点相邻的非悬挂边口6 ， 将树按图分为a s 和b 两部分，则当i v c a ) 卜l s l i y ( b ) i 时，经上述变换得到 的树的w i e n e r 指标增大 定理2 3 5 设t t 2 则3 t 碍0 ，满足m ( r ) 1 4 ( t 7 ) 证明：我们区分两种情况： 情形一：r + t 为奇数 设，+ t = 2 n + 1 ，这里订n 由定理2 3 1 ，当0 s 钉一5 ，( 霉2 。t ) s ( 霹+ 1 ) ；由定理2 3 2 ，w t ：理扎 ) = w ( t 卅2l 帽o ，。) 取t = z 嚣1 托o ，。即可 情形二：7 十t 为偶数。 设7 - + k2 n ，这里n n 由定理2 3 1 ，当0s5 行一5 ， 缈( t 。2 ，) 渺( 巧2 。) ；记7 b = 7 署，叩，由推 论2 3 ，4 ，w ( t b ) ( i 鲁1 。“。) 由定理2 3 2 ，( = f 等+ 1 川m ) = 彤( y 嚣邮，。) 取t = 砰机吣即可。 定理2 3 6 设t 砰。川如果l r t l 之3 那么在，个顶点“悬挂边的树集 克悬挂边的树的l f t i e n e r 指标研究1 4 中，依w i e n e r 指标排序，1 i 训) 排在第四大及第四大以后的位置上 证明：当i r 一i23 时，由r 和t 的轮换对称1 生，不妨设t = r + 3 。由定理2 3 1 和 定理2 3 3 ，有以下序关系：1 1 r ( 1 o ) 州i 置1 t - i ) i i ( 7 鬈1 1 t 一2 ) ( 丁0 1 1 t ) = ( t l l ，o ”1 ) 综上所述，我们得到了具有第二大w i e n e r 指标的树的极图。 定理2 3 7 设r 叠“，r + 时t = 七，如果k 兰1 ( 研甜2 ) ，则( t ) 取到第二 大值( t ) = 7 1 2 _ 3 n + 3 + n k 一篷笋当且仅当r 皇哗 1 ，孚5 如果南三o ( m 。d 2 ) ， 则( r ) 取到第二大值w ( r ) = n 2 3 n + 3 + 7 l 七一生乒一 当且仅当t 皇嚷+ 1 。，皇一l 或t 兰t 弘2 告一1 = 悬挂边的树的i e n e r 指标研究 2 42 形( f ) 指 观察_ k ：c t 定理，我们发现树由t 到】1 的变换过程中，除子树死，疋外，剩 下的部分并没有发生变化。于是，定理2 4 3 可以进一步简化如下； 图2 4 - 1 k 一悬挂边的树的i i - i e n e r 指标研究 1 8 定理2 4 5 如图2 4 1 i 所示，设f o 是i 2 的顶点，孔，是两棵树。现将怕与 n ，的任意顶点相连，由此得到的树记为? 。设( j f j ) l = n 1 ，f 矿( i 硼= 他， v t t a ) ! = n 3 t 是通过以下变换而得到的树：收缩边e 。，剖分边f 2 。7 1 与，1 的w i e n e l t 指标满足以下关系式： t 4 ( rj l ( r ) = ( 竹2 1 ) ( 对l + 1 一n 3 ) 证明：树7 由t 到t 的变换过程中，子树孔，疋，丁3 的u i e n m 指标保 持不变。记i e n e r 指标不变的部分为，由定理2 1 3 有： w ( t ) =十，1 3 ( n 】+ 孔2 ) + m ( - 3 + r 1 2 ) w i t ) =w o + n l ( 礼2 + n 3 ) + ( ，1 1 + 1 ) ( 竹3 + n 2 一1 ) 仉7 ( 丁) 一w ( t ) =( n l + 1 ) ( 雅3 + 1 2 2 1 ) 一n 3 ( n 1 + 7 2 ) =( n l + 1 ) ( 礼3 + n 2 1 ) 一n 3 ( n l + 1 ) + n 2 1 ) 】 = ( 1 1 1 + 1 ) ( n 2 1 + 1 2 3 ) 一7 1 , 3 ( 1 7 , 1 + 1 ) 一1 1 3 ( 1 1 2 1 ) = ( n 1 + 1 ) ( n 2 一1 ) 一1 2 3 ( 1 n g 一1 ) = ( n 2 一1 ) ( 饥1 + i 一竹3 ) 定理2 4 6 设t 砖将丁依w i e n e r 指标从大到小排列，若研( 排在第 二个位置及第二个位置以恿贝? 一定是”毛虫”树 证明：若丁不是“毛虫”树( e a t e r p i l l a , r ) ，我们将所有的一度点去掉，由此得到 的子树记为，则必存在顶点t o ，满足a l t o ( v o ) = k 3 ，而d r ( v o ) = t k 记n t o ( v o ) = ( 屹，1 j k 去掉点铷，得到k 个连通分枝，即日，碍，q 现将所有一度点还原，并重新命名这七个连通分枝为j ，妃，孔，使得l 矿( 乃) i y ( 仃j ) l i v ( t 1 ) i i v ( t k ) i 令s = n t o t 5u u 巩u ( 坼( t ，o ) n r o ( v o ) ) 则 树t 可看为4 棵子树的并，并且是这4 棵子树的唯一公共点。作变换如下：收 缩边。，剖分边t 2 ，由此得到的树记为? 因为n 3s 恐，根据定理2 2 ，4 和定理1 3 2 ，我们有以下序关系： ( d ( n ，i i ，f 1 ) ) 1 1 ( t ) 州t ) 我f f t g 定理2 4 5 的变换为丁一z ，。 惫悬挂边的树的1 1 i e n e r 指标研究 1 9 推论2 4 7 设树7 1 砭。，将l 甍。中的树依1 1 i e n e r 指标从大到小排列，如果 7 经过 ：次白i = f 1 一t 变换成为“毛虫“树，剥i v ( 7 ) 排在第岛+ 1 ( 不含k + 1 ) 以 后的位置上。 由定理246 ，我们可以知道，要寻求具有第二大1 i i e n e r 指标的树，只须从 “毛虫”树( c a t e r p z l l a ，) 的集合去找进一步地，我们还有： 定理2 4 8 设t 砭k ，且丁是“毛虫”型树，r 的非悬挂边数f _ 竹一1 一太， 我们将树的非悬挂点重新标号为， ，q ，将砭。中的树依w i e n e r 指标从大 到小排列，如果i , i7 ( = f 1 ) 排在第2 个位置上，则非悬挂点q ，肌，至多只能联结 一个悬挂点。并且悬挂点不可能与瑚一：相连。 证明：我们区分两种情形： 情形一：悬挂点与珏，址：相连，由推论2 ，4 4 ，则( 丁) 排在第3 或第3 以 后的位置上 情形二：t 的非悬挂点札m 一。联结两个悬挂点由情形一的讨论，只须证 非悬挂点t ，或一。联结两个悬挂点即可不妨设非悬挂点u 联结两个悬挂点， 由推论2 a 4 ，则( ? ) 排在第3 或第3 以后的位置匕 由以上讨论，我们把寻求具有第二大w i e n e r 指标的树的结构问题进一步缩小 到更小的集合中了 在一条路r 一一，上，记路的长l = n 一1 s t 一1 ，将路的顶点从左向右重 新标号为蜘朋，耽把。个独立的顶点邻接到这条路的左端点如上，把个 独立的顶点邻接到这条路的右端点仇，剩下的个独立的顶点邻接到路中的某一 个顶点( z ( o ? 1 ) ) 上，这样得到的图我们记为d ( 扎，s ，t ，z ) ( 如图2 4 5 所示) d ( ，s ，z ) 图2 4 5 ：悬挂边的树的1 1 i e n e r 指标研究2 0 我们发现，形如d ( n s ，叫的树可以看为三棵子树乃，= f ；，码的并。即 ? j = k 1 ，。， 7 j = c ，( z f o ，f j ) ，l t 3 = k 1 f 。其中，九l = i 1 7 ( y j ) l = 5 + 1 ， n 2 = 1 17 ( i j ) f = f + 2 ， 3 = l v ( i j ) l = t + 1 ，r l l + n 2 + n 3 = n 十2 。 定理2 t 9 如图2 4 暑所示，设t = d 。( m6 ，z ) ，如果卜t 2 ，那么，将邻 接的任一悬挂顶点去掉，加在f l f 上，由此得到的树记为t ，则有w7 ( 丁) w f 丁) 证明：由引理2 4 1 ，有 ( t ) = i i ( ，、) + 1 1 ( ，2 ) - 4 - 1 1 ( ? b ) + ( 7 1 ，2 j ) + i 矿( 疋，了3 ) + i 7 ( 7 1 ，i ) =ii 7 ( n ) + h ( 而) + l l ( 乃) + l l ( 矗，疋) + w ( x ，分) z v 1 ”o u v o + ( 刎) z u v ov 3 ”o =s 2 +