上海交通大学 硕士学位论文 给定度序列维纳指数的研究 姓名：向其远 申请学位级别：硕士 专业：图论 指导教师：张晓东 20080101 上海交通大学硕士论文 给定度序列时树维纳指数的研究给定度序列时树维纳指数的研究 摘 要 图的维纳指数表示图中所有顶点之间距离之和。在这篇文章中，我们将会研究 在确定树的顶点个数以及顶点度的树的集合中，维纳指数最小树的性质。进一步， 我们可以利用此结论，研究在具有某些特定性质的树的集合中维纳指数最小与最大 树的性质,其中包括给定顶点个数及最大顶点度的树的集合； 给定顶点个数及度为 1 的顶点个数等等。进一步，我们可以研究给定顶点个数及最大顶点度时维纳指数最 大树的结构，并且可以得出在给定度序列时（度类型小于 4） ，维纳指数最大树的结 构。根据此结论，我们给出了在任意度序列下维纳指数最大树结构的猜想。 关键词：维纳指数，树，度序列，距离，优超 上海交通大学硕士论文 THE WIENER INDEX OF TREES WITH GIVEN DEGREE SEQUENCES ABSTRACT The Wiener index is the sum of topological distance between all pairs of vertices in an acyclic graph(tree) representing the structural formula of a molecule.Firstly,we investigate some properties of the partial ordered set of all vectors whose component corresponding to each vertex of a rooted tree is equal to the number of its vertex and its successors with respect to majorization. Then these results are used to characterize the trees which minimize the Wiener index among all trees with given degree sequence.Consequently,all extremal trees with the maximum degree,the leave number and the matching number respectively.Further，using similar method,we characterize trees which maximize the Wiener index with maximum degree，as well as given degree sequence with degree types less than 4. Base on the conclusion,we could suppose the structure of tree which maximize the Wiener index with given degree sequence. KEY WORDS: Wiener index,Tree,Degree sequence,distance,majorization 上海交通大学硕士论文 图片目录 图1 树 * T，(4,4,3,3,3,3,2,1,1,1,1,1,1,1,1,1,1)=5 图2 树T，(4,4,3,3,3,3,2,1,1,1,1,1,1,1,1,1,1)=6 图3 T，(4,2,2,2,2,2,1,1,1,1)=24 图4 T，4,4,4,4,4,3,3,3,3,1,1,1=?27 图5 维纳指数最大树29 上海交通大学硕士论文 上海交通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本文郑重声明：所呈交的学位论文，是本人在导师指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：向其远 日期：2008 年 2 月 20 日 上海交通大学硕士论文 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文 的规定，同意学校保留并向国家有关部门或机构送交论文的的 复印件和电子版，允许论文被查阅和借阅。本人授权上海交通 大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。 保密保密，在年解密后适用本授权书 本学位论文属于 不保密 不保密 （请在以上方框内打“” ） 学位论文作者签名：向其远 指导教师签名：张晓东 日期：2008 年 2 月 20 日 日期：2008 年 2 月 20 日 上海交通大学硕士论文 1 1 背景介绍 1.1 维纳指数的由来 分子及分子化合物的结构往往是以分子图的形式来表示。对分子图的拓扑结构 研究是分子结构最广泛的研究手段，其中对分子图维纳指数的研究是最为广泛的方 法之一。 “维纳”这个名词首先是以化学家维纳来命名，他首先提出了“维纳”这个 概念。在化学上，维纳指数理论应用最为广泛的是对无环有机分子结构的研究，它 的分子拓扑结构在数学上对应的是连通无圈图树。化学家们常常会对某些特定 的树的维纳指数感兴趣，因为它们是分子实际结构理想模型。在数学界，Entringer 是最早开始研究维纳指数性质的人。 1.2 维纳指数的定义 G=(V,E)表示以 12n V(G)v ,v,v =?为顶点E(G)为边的简单图。( ) Gi dv表示顶 点 i v的度。顶点 i v到 j v的距离表示 i v与 j v之间最少的边的条数，我们用( ,) Tij dv v表 示，维纳指数的定义为： , () ( )( , ) T u vV G W Gdu v = 同时我们还记 2 ( ) ( ) n W G G C = 表示图G的平均距离。 Entringer 在其著作中已经证明在顶点个数为 n 的所有树中， 1,1n K 和 n P分别具 有最小及最大的维纳指数。最近，Fischermann 在其著作中证明了在给定树的顶点 个数以及最大度的情况下，维纳指数最小树的结构。 上海交通大学硕士论文 2 1.3 给定度序列时维纳指数最小的树 定理定理 1.1 给定树的顶点个数及度序列 01,1 (,) n d dd =?，集合 ( )= |TT TT是顶点个数为n的树, 的度序列为 那么 * T (其定义见第2章)是( )T中唯一的维纳指数最小的树。 定理1.1是这篇文章中最重要的定理，我们将在第2章与第3章给出证明，在 第4章中给出了该定理一些主要的应用。 上海交通大学硕士论文 3 2 理论基础 2.1 树 * T的定义 对于给定的树的度序列 01,1 (,) n d dd =?(其中3n )，其中 011n ddd ?， ( )= |TT TT是顶点个数为n树, 的度序列为 我们利用breadth-first法在( )T定义树 * T。假设1 m d， 11 1 mn dd + =?，其中 11mn 我们构造序列 (1)(1)(1) 1011 (,) n ddd =?， 当,ip q时， (1) ii dd=； (1) 1 pp dd=， (1) 1 qq dd=+。 序列 1 中的元素按递增排列， 且 1 ， 同时序列 1 满足成为树的度序列的条件： (1)(1)(1) 011011 2(1) nn ddddddn +=+=? 按照类似的方法可以依次出构造度序列 23 , k ?满足题设条件。 定理 4.2定理 4.2 r是树T的根， 11 ( ,) , k P w uw uu=?与 110 ( ,) , k P w vw vv v=?是T 中的两条路， 其中 11 ,()( ),( )( ),(1, ) TTTiTi kl dudvfufvik=?，T是以r为根的树， 上海交通大学硕士论文 17 且 0 10 1 TTv vv u=+，那么有如下结论： （1） 若与分别为T与T的度序列，那么 ，且与中仅有 2 元素 相差 1，其余元素相同。 （2）( )( ) w f Tf T （3）如果 r还是T与T的质心，那么( )( )W TW T，由定义有， ( ) ( ) TiTi fufub=+，其中1,ik=?， ( ) ( ) TiTi fvfvb=，其中1,il=?，同时对任意 11 ( ) , kl uV Tuu vv?有 ( )( ) TT fufu= 又因为( )( ),(1, ) TiTi fufvik=?，可以得到 1111 (),(),( ),( )(),(),( ),( ) w TTkTTlTTkTTl fufufvfvfufufvfv? 所以有 ( )( ) w f Tf T 由定理 3.4 及（2）的结论可知（3）成立。 4.1.2 不同度序列下 * T树的性质 定理 4.3 定理 4.3 与均为树的度序列，记 *( ) T与 *( ) T分别为( )T与( )T中维 纳指数最小的树。如果 ，则 * ( )( )W TW T 当且仅当=时等号成立。 证明：由定理 4.1，不失一般性，假定 011011 (,),(,) nn d ddd dd =?， (, ),1,1 iippqq dd ip q dddd=+， 其中01pqn使 * ( ) qk v vE T,现构造一个以 0 v为根的 树 * 1 ( ) qkpk TTv vv v=+。根据 *( ) T的构造，容易知道它满足定理 4.2 的条件， 上海交通大学硕士论文 18 所以由定理 4.2 的结论（2）可知 * 1 ( )( ) w f Tf T 并且 1 ( )TT,所以由定理 1.1 可知 * 1 ( )( ) w f Tf T 所以 * ( )( ) w f Tf T，由定理 3.4 * ( )( )W TW T 4.2 维纳指数最小数的应用 利用以上定理我们可以推导出某类树集合中的维纳指数最小树的性质。例 如, (1) ,n s T表示顶点个数为n，叶子结点个数为s的树的集合； (2)