（应用数学专业论文）具有最小和最大wienerhosoya指标的树.pdf

摘要 为研究分子的结构与其化学性质( 如稳定性，沸点等) 之 间的联系，化学家引入了许多与分子的拓朴结构密切相关的 指标其中w i e n e ri n d e x 和h o s o y ai n d e x 就是较具代表性的 两个指标结合这两个指标各自的特点，m r a n d i d 在文 2 】中引 入了w i e n e r h o s o y a 指标，以期进一步揭示分子的结构与其化 学性质之间的联系。本文主要研究具有最大和最小 w i e n e r h o s o y a 指标的树。第二章确定了给定顶点数和直径 的具有最小w i e n e r h o s o y a 指标的树，并对给定顶点数的第 一小到第十六小的w i e n e r h o s o y a 指标的树进行了排序。第 三章确定了当n 三1 7 时，具有最大的w i e n e r h o s o y a 指标的树。 关键词：最小的，最大的，w i e n e r h o s o y a 指标，树 a b s t r a c t w i e n e rn u m b e rwi st h es u mo fd i s t a n c e so fa n yc a r b o n a t o m si nt h em o l e c u l a r h o s o y at o p o l o g i c a li n d e xzc o u n t st h ek d i s j o i n te d g e si nt h er e l e v a n tg r a p hf o rl f 0 ，1 ，2 ，w i e n e rn u m b e r a n dh o s o y ai n d e xa r et w ow i l d l yu s e dm o l e c u l a rd e s c r i p t i o n si n s t r u c t u r e - - - p r o p e r t y a c t i v i t ys t u d i e s t h ew i e n e rn u m b e r i st h ef i r s t n o n t r i v i a lm o l e c u l a rd e s c r i p t o ri nc o m b i n a t i o nw i t hp a t h so fl e n g t h t h r e ef o rs t r u c t u r e - p r o p e r t yc o r r e l a t i o n s ；t h eh o s o y ai n d e xi st h ef i r s t m o l e c u l a ri n v a r i a n tw h i c hi sf o u n du s e f u li ns i m p l er e g r e s s i o n s w i e n e r - h o s o y ai n d e xw a sf i r s t l yi n t r o d u c e db ym r a n d i d i n 2 】，w h i c hi se x p e c t e dt or e v e a ls o m ef u r t h e rp r o p e r t i e so f m o l e c u l a r t h i sp a p e rd e a l sw i t ht h em i n i m u ma n dm a x i m u mt r e e s w i t hr e s p e c tt ow i e n e r - h o s o y ai n d e x i nc h a p t e r2 ，t h em i n i m u m t r e ew i t hg i v e no r d e r sa n dd i a m e t e r sa r ed e t e r m i n e da n dt h ef i r s t16 m i n i m u mt r e e sw i mg i v e no r d e r sa r el i s t e dw h i c ha r es h o w n r o u g h l y s p e a k i n g ，t ob eo fs m a l l e rd i a m e t e r i nc h a p t e r3 ，t h em a x i m a lt r e e s ( n _ 17 ) w i t hr e s p e c tt ow i e n e r - h o s o y a i n d e xa r ea l s od e t e r m i n e d k e yw o r d s ：m i n i m u mt r e e ，m a x i m u mt r e e ，w i e n e r - h o s o y ai n d e x 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：乏为建，定 d 易年易月l - o 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打“”) 作者签名：焉建、艇 导师签名： 日期： 汐6 年5 月汐日 日期：年月日 具有晟小和摄大w i e n e r - h o s o y a 指标的树 第一章引言 为研究分子的结构与其化学性质( 如稳定性，沸点等) 之 间的联系，化学家引入了许多与分子的拓朴结构密切相关的 指标。其中最著名的就是w i e n e r 指标w 1 、h o s o y a t o p o l o g i c a l 指标z 【2 】和c o n n e c t i v i t y 指标x 3 】，这三个指标 都是从数学的观点来研究分子结构和性质的。例如，w i e n e r 指标w 可以定义为距离矩阵上三角主对角线的和 2 】，另外 它也可从l a p l a c i a n 矩阵的根中去获得 4 。h o s o y a t o p o l o g i c a l 指标z 是联系特征多项式的一个数【5 】，而 c o n n e c t i v i t y 指标x 最近被下定义在原子结构 6 和正规的 l a p l a c e 矩阵上 7 。人们对这三个指标有着相当多的研究， 其中有着最重要和最广泛应用的就是w i e n e r 指标w ，它是 第一个用来描述路长为3 的分子的结构和性质的指 标；h o s o y a 指标z 是第一个在分子简单回归问题上发现的不 变量，而c o n n e c t i v i t y 指标x 是第一个用来描述分子结构 和性质关系的指标。为了更进一步研究分子的沸点 8 ，空 间结构 9 ，平均信息量 1 0 】，平均半径 1 1 】，蒸发作用 1 2 】 等性质时，m i l a nr a n d i c 又定义了w i e n e r h o s o y a 指标， 以期更准确地描述分子之间的一些性质和特性。 w i e n e r 指标形也可描述为分子中任意两个碳原子之间 的距离的和，而在计算时我们常用公式 具有最小和最大w i e n e r - h o s o y a 指标的树 w 2 形( p ) 来表示，这里e 是指所有连接碳碳原子的键，w ( e ) 是指e 两边 碳原子个数的乘积。h o s o y a 指标z 是计算图中所有匹配的数 目。h o s o y a 【1 3 发现了计算z 的一个优美组合原理【1 5 】，它 可以表示成 z ( g ) = z ( g e ) + z ( g e e ) 这里g e 是指图g 中删去一条边e 所得的图，g e e 是指g 中删去边e 以及和它所有相连的边所得的图，这个组合原理 可以把一个很大的分子分解成很多小的部分。 设e 是树t 的一条边，我们用h t ( e ) 表示t _ e 时每一部 分顶点个数的乘积，用h t e 表示t - ( u ，v ) 后各部分顶点个数 的乘积，这里f u ，v ) 是指边e 的两个顶点。对任意的树t ，m r a n d i 6 介绍了一个新的图论描述符号一一w i e n e r - h o s o y a 指 标，它可以定义为 h ( t ) = ( ( p ) + h e l e e e l r ) 如果e 是悬挂边，那么h e 】就认为是0 1 4 】。正如r a n d i 6 他 自己指出的一样，w i e n e r h o s o y a 指标能够用上面组合原理 来表示，我们是去计算w i e n e r 指标w 而不是去计算h o s o y a t o p o l o g i c a l 指标z 。w i e n e r - h o s o y a 指标比很多简单的拓扑指 标有明显的退化，它可以更准确地描述庚烷、辛烷和癸烷等 的同分异构体的性质特征 9 】。 本文第二章主要研究对于给定的顶点n 和直径d 时， 只有屉小和最人w i e n e r - h o s o y a 指标的树 具有第一到第十六小的树。利用2 1 中给出引理的刻画了具 有最小w i e n e r - h o s o y a 指标的树；进一步地，对第一到第十六 小的树进行了排序。第三章主要研究给定顶点数时，具有最 大的w i e n e r h o s o y a 指标的树。利用3 1 的四个引理，证明 了任意一棵树都会小于某个腿长为2 或3 的s p i d e r ，在此基础 上确定了具有最大w i e n e r h o s o y a 指标的树。 肄有最小和最人w l e n e r - h o s o y a 指标的树 第二章给定顶点数和直径的最小树 2 1引理 首先来证明一个很重要的引理 引理1 对任意的树r ，下图1 中的两个操作后w i e n e 卜h o s o v a 指标不会增加，这里t i + ( i - l ，2 ，f ) 是至少有三个顶点的树。即 当硷2 时 ( 力五( r j ) ， 师 ：彳踩! 蟛飞 r u 2 2 露- f v71 印 k z 2。弋j f t j k = 1 图1 ：两个操作使得w i e n e r h o s o y a 指标减少 证明：由定义容易得出下列等式： 厅r ( e o ) = ( 后+ 1 ) ( 聆一k i ) ，h ( e o ) = 2 ( n 一2 ) ，h 疋( g o ) = 玎一1 ； h r e o = f 木( 掰) ，h r 。 p o = t + ( 甜) ，h r ： g o 】= 0 ； h r 【p f _ ( 七+ 0 t 4 ( “，v ，) ，h l k = 2 t + ( 甜，1 ，) ，h r 2 k 】= t + ( 甜，v f ) ，i = l ，2 ，t ， 这里f 8 ( “) ( 相应地f + ( i , 1 ，v i ) ) 是指t * - 甜) ( 相应地：t * - “，v f ) ) 时各部分顶点个数的乘积。显然 具有最小和最大w i e n c r - h o s o y a 指标的树 且 局，( e 。) + 五r p 。】 h r l ( p 。) + 厅r 【q ，后2 h r ( p 。) + 厶r 【8 ， h r ：( e 。) + ，：【e ；】，k 2 i = 1f = l 另一方面，我们很容易检验出，对任何不在上面所列出的边 e 的h r ( 8 ) ，h ( p ) ，h 疋( p ) ( 或h r p 】，h “p 】，h d e ) ，我们都有 h r ( p ) = h r 。( p ) ，珏( p ) 2 k ( p ) ( 或m = b y , 【p 】，h r m 2 m ) 证毕。 具有最小和昂大w e n e 卜h o s o y a 指标的树 第三章具有最大的w i e n e r - h o s o y a 指标的树 3 1 引理 ，t、缪，f7夸强，) ”象：r ：| ；f j 摹。 r j|：i t l 、7 藤芋、， 。皇? 。、。 三夕7 b ：】- 。= 国：， 力7 1 ：b 】_ ( + 1 ) 卉j = l 研= ：2 h t , f 。 = 冉s ，= 缈：，h t 2 f 。】= z 垂j ，2 国。2 具有最小和最大w l e n e r - h o s o y a 指标的树 l 陟， = 沏+ 3 ) 痧，丞， 办，：w = zm + 1 ) 痧，船，= ； 这里，= h ”厂i j ( 下面矽。同此意) ， 很容易我们可以得到壹缈；一杰国： 0 另一方面，所有不在上面列出的边，我们都可以很容易得出 h y 。0 ) = h r ：( d j l h r 。k 】= h r ：k 】 所以显然有 矗口：) 一 盱骖0 类似的我们也可以证明 。) 一h ( y 骖0 证毕。 引理3t 1 和t 2 是有n ( n l7 ) 个顶点的两棵树，下图4 中的 操作后w i e n e r h o s o y a 指标增加，即h ( t 1 ) 0 另一方面，所有不在上面列出的边，我们都可以很容易得出 h r , 0 ) = h 丁：( e ) r h 丁。 e l = h ，：m 。 所以显然有 ( r ：) 一h ( t ) ) o 证毕。 引理4t l 和t 2 是有n ( n 1 7 ) 个顶点的两棵树，下图5 中的 操作后w i e n e r h o s o y a 指标增加，即h ( r ) o 证毕。 引理5对任意有n ( n 兰17 ) 个顶点的树t ，下图3 中的两个操 作后w i e n e r - h o s o y a 指标增加。即当r 4 时，h ( t 1 ) 0 另方面，所有不在上面列出的边，我们都可以很容易得出 h r ( e ) = h r ，0 ) 且办丁。 e l 2 h r ： e l 。 所以显然有 协：) 一 骖0 类似的我们也可以证明 ，) 一比r 。胯。 证毕。 具有最小和最大w i c n e r - h o s o y a 指标的树 3 2具有最大的w i e n e r - h o s o y a 指标的树 如果一棵树至多有一个顶点的度大于或等于3 ，就叫这 棵树为一个鼍s p i d e r 设s 是一个s p i d e r ，它只有一个顶点的度 大于或等于3 ，我们就用o 来表示这个顶点且把s 0 ) 的各 部份叫做s 的腿，这个s p i d e r 也可以表示成s ( k ，：，丘) ，其中 ( i = l ，2 ，k ) 表示腿长为i 的腿的总数，k 是它最长腿的长度。 如8 ( 2 13 1 ) 就表示腿长为1 的有两根，腿长为2 的有一根，腿 长为3 的有3 根，腿长为4 的有一根。如下图： 、r tj ， j ：ji j f o 图7 ：表示s p i d e rs ( 2 13 1 ) 定理2 对任意的树t ( n 兰1 7 ) ，总有一个直径至多为6 的 s p i d e rs ，使得h ( t ) 0 另一方面，所有不在上面列出的边，我们都可以很容易得出 h r ( e ) = h r ：( e ) r h r k 】= h r ：k 】。 所以显然有 矗口。) 一 口骖。 当n ：3 k + 1 时，所有腿长为2 的分枝最后都可转化成腿 长为3 的s p i d e r ，即具有最大的w i e n e 卜h o s o y a 指标的树是 s ( o ，0 ，n _ - 1 ) 。 具有虽小和最大w i c n e p h o s o y a 指标的树 ，? ，一f n - 1，一。、 ，j j ，7 。：j 3 “7 ， o 仁c 一。 很容易算出： ( s ( o ，o ，1 n - 一1 ) = 2 。一1 ) 3 ”i 7 + j 1 【7 玎2 2 4 h + 1 7 ) 当n = 3 k + 2 时，除2 根腿长为2 的以外，其它的都可转 化成腿长为3 的s p i d e r ，即具有最大的w i e n e r h o s o y a 指标 的树是s ( 0 ，2 ，n - _ 5 ) 。 o 很容易算出： ( s ( 。，2 ，了n - 5 ) = 4 ( 2 一一1 ) 3 ”； + ；( 7 n 2 - 3 4 n + 4 1 ) 当n = 3 k 时，除1 根腿长为2 的分枝以外，其它的都可 转化成腿长为3 的s p i d e r ，即具有最大的w i e n e r h o s o y a 指 标的树是s ( 0 ，1 ，_ n - 3 ) 。 ，j ，| | | j 笋 ，。7；号= +。，?。l 。 ，：7 ) ：# 7r j 。 o 很容易算出：h ( s ( o ，1 ，_ n - 厂3 ) = ( 4 n 一3 ) 3 了n - 9 + 弘1 7 刀2 2 9 n + 3 6 ) 证毕。 由这个结果我们可以看出，具有最大的w i e n e r h o s o y a 指标的树是有尽可能多的腿长为3 的s p i d e r 。 2 0 学 一 o 具有最小和最大w i e n e r - h o s o y a 指标的树 参考文献 1 w ie n e r ，h 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 f f i nb o i l i n g p o in t s j a m c h e m s o c 1 9 4 7 ，6 9 ，17 2 0 。 2 h o s o y a ，h t o p o l o g ic a l i n d e x an e w l yp r o p o s e dq u a n t i t y c h a r a c t e r iz in gt o p 0 1 0 9 ic a ln a t u f eo fs t r u c t u r e lis o m e r so f s a t u r a t e dh y d r o c a r b o n s b u l l c h e m s o c j p n1 9 7 1 ，4 4 ， 2 3 3 2 2 3 3 9 【3 】r a n d i 6 ，m o nc h a r a c t e r iz a ti o no fm o l e c u l a rb r a n c h in g j am c h e m s o c 1 9 7 5 ，9 7 ，6 6 0 9 6 6 15 4 ar a t h e rc o m p le t eb i b li o g r a p h yo nt h er e l a t i o n s h i pb e t w e e n wa n d t h el a p l a c i a ncanb ef o u n di nt h ef 0 1 1 0 w i n g ：c h a n ， 0 ：l a m ，t k ：m e r r is ，r w ie n e rn u m b e ra s a ni m m a n a n to f l a p l a e i a n o fm o le c u l a r g r a p h s j c h e m i n f c o m p u t s c i 1 9 9 7 ，3 7 ，7 6 2 7 6 5 5 h o s o y a ，h g r a p h i e a le n u m e r a t i o no ft h ec o e f f ic i e n t so ft h e h o c k e lm 0 1e c u l a ro r b i t a ls t h e o r c h i m a c t a1 9 7 2 ，2 5 ， 2 15 2 2 2 6 g u t m a n ，i ：a r a u j o ，0 ：r a d a ，j a ni d e n t i t yf o rr a n d i 6 c o n n e c t iv i t yi n d e xa i 3 di t sa p p l ic a t i o r l s a c h m o d e lsc h e m 2 0 0 0 ，13 7 ，6 5 3 6 5 8 7 k l e in ，d j ：p a ls c i o s ，j l ：r a n d i 6 ，m ：w r i n a j s t ic ，n r a n d o mw a l k sa n dc h e m i c a lg r a p ht h e o r y t ob es u b m i t t e df o r p u b l i c a t i o n 8 b e e d h a m ，d e ：w e i ，i 一c ：s d y b 0 1 d ，p g m o l e c u l a rm o d e l i n g o fg h ep h y s ic a lp r o p e r t ie so ft h ea 1 k a n e s j a m c h e m 1 9 9 1 ， 7 1 5 51 6 8 9 r a n d i 6 ，m c o r r e l a t i o no fe n t h a l p ie so f o c t a n e sw it h o f t h o g o n a l m o le c u l a r d e s c r i p t o r s j m 0 1 s t r u c ( t h e o c h e m ) ，2 3 3 ，4 5 5 9 2 1 具有最小和虽大w i e n e r - h o s o y a 指标的树 10 s c o t t ，d w c o r r e l a t i o no f p r o p e r t i e so fa l k a n eh y d r o c a r b o n s 3 1 4 4 3 1 6 5 c h e m ic a lt h e r m o d y n a m ic j c h e m p h y s 1 9 7 4 ，6 0 ， 11 a l t e n b u r g ， k e i n e b e m e r l u n g z ud e mr a n d i cs c h e n “m 0 1 e k u l a r e nb i n d u n g s i n d e x ( m 0 1 e c u l a rc o n n e c t iv i t y in d e x ) ”z p h y s c h e m ( l e i p z i g ) 1 9 8 0 ，2 6 1 ，3 8 9 3 9 3 12 g a r b a l e n a ，m ：h e r n d o n ，w c o p t i m u m ；g r a p h t h e o r e t ic a l m o d e lsf o re a t h a l p icp r o p e r t i e so fa l k a n e s j c h e m i n f c o m p u t s c i 1 9 9 2 ，3 2 ，3 7 - 4 2 1 3 h h o s o y a ，k k a w a s a k ia n dk m iz u t a n i ，t o p o l o g ic a li n d e x a n dt h e r m o d y h a m ic sp r o p e r t i e s ，e m p i r ic a lr u l e s0 1 3t h e b o i1i n gp o i d tso fs a t u r a t e dh y d r o c a r b o n s b u l l c h e m s o c j p n ，4 5 ( 1 9 7 2 ) ，3 4 15 1 4 m r a n d i 6 ， w ie n e r h o s o y ain d e x 一一an o v e l g r a p h t h e o f e t ic a lm o l e c u l a rd e s c r i p t o r j c h e m i n f c o m p u t s c i ，4 4 ( 2 0 0 4 ) ，3 7 3 3 7 7 15 】h