（应用数学专业论文）乘积图生成树的wiener数问题.pdfVIP

摘要 美国物理化学家t l a r 0 1 dw i e n e r 在 1 中最早提出w i e n e r 数( 在他的文献中 称为p a t hn u m b e r ) 。w i e n e r 构造w i e n e r 数的初衷是用于处理无环的有机分子 结构( 用图论的语言，这种无环的有机分子结构图就是树) 问题，其原始的定义 为矿2 ，( p ) ，其中和式取遍图中的每一条边e ，厂( p ) 表示将无环分子图的 边p 删除后的两个连通分支的顶点数之积。对于一棵树，而言，其w j e n e r 数也可 等价的定义为任意两点的距离之和，即矿( 7 t ) =d r ( u ，v ) 。这一定义后来 k 拉r ( r ) 被数学家及化学家推广到一般的连通图。 本文研究如下问题：给定一个连通图，如何确定其w i e n e r 数最小的生成树? 这是w i e n e r 数研究中的主要问题之一。这一问题不仅对于w i e n e r 数的研究有着 重要的理论和实际意义，同时也具有其它的一些实际背景( 如经济刚络的设计等 9 ) 。一般而言，这一问题具有相当的难度，即使是对于一些很特殊的图类如超立 方体，也还是一个尚未解决的问题。事实上，d o b r y n i n 在 9 中构造了超立方体 的两类w i e n e r 数“很小”的生成树，并进一步猜想这两类树都是w i e n e r 数最小 的生成树。利用归纳推理及递归关系，本文对更一般的且具有良好拓扑性质和较 高的网络模型应用价值的乘积图，如g l g 2 、鲜、四等，构造了相应的生成树 并计算了它们的w i e n e r 数的值，以期获得这些乘积图w i e n e r 数最小的生成树。 这些结果推广了d o b r y n i n 关于超立方体的结果。文章的最后，我们分析了k ? 、 c ? 的渐进性质。 关键词：生成树；w i e n e r ；乘积图 a b s t r a c t t h ew e l l k n o w nw i e n e rn u m b e r ( o ri n d e x ) 彬o n eo ft h ew i l d l yu s e dm o l e c u l a r d e s c r i p t i o n si ns 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 sw h i c hw a sf i r s t l yi n t r o d u c e db yh w i e n e ri n 【1 】，i st h es l i mo f d i s t a n c e so f a n yt w oc a r b o na t o m si nt h em o l e c u l a r i nt h e e a r l i e rl i t e r a t u r e s ，c h e m i s t su s e dw ；e n e rn u m b e rt od e a l w i t h a c y c l i co r g a n i c m o l e c u l e ss t r u c t u r e t h i sk i n do fa c y c l i cm o l e c u l e si sm a t h e m a t i c a l l yr e f e r r e dt oa s t r e e i nc a l c u l a t i n g ，w i e n e rn u m b e ri sa l s os t a t e da sa n o t h e re q u i v a l e n tf o r m ：w 2 ，( e ) ，w h e r et h es u m m a t i o n r u n so v e ra l lc a r b o n 。c a r b o nb o n d spa n d ( p ) i st h e p p r o d u c to f t h en u m b e r o f c m _ ；1 3 0 n a t o m s o n o n es i d e o f e a n d t h a t o f o t h e r s i d e t h i sp a p e rf o c u s e so nt h ep r o b l e m ：f m d i n gas p a n n i n gt r e eo fag r a p hw i t h m i n i m u mw i e n e rn u m b e r g e n e r a l l ys p e a k i n g ，t h i sp r o b l e mi sn o te a s y , e v e nf o ra v e r ys p e c i a lt y p r l l l eh y p e r c u b e i nf a c t , d o b r y n i n 9 】c o n s t r u c t e dt w ot y p e so f s p a n n i n gf l e e sf o rh y p e r c u b ea n df u r t h e rc o n j e c t u r e dt h a tt h e s et r e e sa r e t h em i n i m u m s p a n n i n gt r e e s ( w i t hr e s p e c tt ot h ew i e n e rn u m b e r ) i nt h i sp a p e r , w ec o n s t r u c ts o m e s p a n n i n gt r e e sf o rm o r eg e n e r a lg r a p h s ：c a r t e s i a np r o d u c tg r a p h s ( k n o w nw i t hg o o d t o p o l o g i c a lp r o p e r t i e sa n de x c e l l e n tn e t w o r kp a r a m e t e r ) s u c ha sg 1xg 2 、群、四 e t c ，i na l la t t e m p tt of i n dt h e i rm i n i m u ms p a n n i n gt r e e s o u rr e s u l tg e n e r a l i z e st h a to f d o b r y n i n s f i n a l l y , a na s y m p t o t i cp r o p e r t y f o rl a r g ep r o d u c tg r a p h sa b o v ei s a n a l y z e d i no u rs t u d y , t h em a t h e m a t i c a li n d u c t i o na n dr e c u r r e n c er e l a t i o nt e c h n i q u e s w i l lp l a yi m p o r t a n tr o l e s k e y - w o r d ：s p a n n i n gf l e e ；w i e n e ri n d e x ；c a r t e s i a np r o d u c tg r a p h s 乘积图生成树的w i e n e r 数问题 第一章引言 1 9 4 7 年，美国物理化学家h a r o l dw i e n e r 在 1 】中最早提出w i e n e r 数( 在他的 文献中称为p a t hn u m b e r ) 。w i e n e r 构造w i e n e r 数的初衷是用于处理无环的有机 分子结构( 用图论的语言，这种无环的有机分子结构图就是树) 问题，其原始的 定义为w = 厂( f ) ，其中和式取遍图中的每一条边8 ，( p ) 表示将无环分子图 的边e 删除后的两个连通分支的顶点数之积。而将w i e n e r 数定义为连通图中任 意两点的距离之和，是由h o s o y a 于1 9 7 1 年在 2 1 q b 首次提出的。形式上，它与 w i e n e r 数的原始定义略有不同，但事实上，二者是等价的。 2 0 世纪7 0 年代中叶以来，w i e n e r 数频繁地出现在各类化学文献中【3 ，4 ，5 】。 可是，很长一段时间以来，数学家们并没有注意到早期的化学文献中频繁出现的 w i e n e r 数。直到1 9 7 6 年，w i e n e r 数才第一次出现在数学文献 6 】中。尽管如此， 近现代的许多数学文献仍然以w i e n e r 数来命名它，以纪念这位伟大的科学家。 当然，在一些文献中，w i e n e r 数也被称作图的距离( d i s t a n c e o f a g r a p h ) 6 】、传 输( t r a n s m i s s i o n ) 7 】等。 本文考虑的对象是连通图g 。图g 的顶点集记为v 佑 边集记为er g j ， g 的顶点数记为 印，如( “，v ) 表示g 中“、v 两点之间的距离，如( v ) 表示图g 中顶点v 到其它所有顶点的距离之和，即如( 1 ，) = a g ( u ，v ) 。由此，图g 的 “v w i e n e r 数可表示为矿( g ) = 如( “，v ) = i 1 如( v ) 。 k ” r 【g )v c v ( g ) 对于连通图g ，总存在一个点a ，使得该点到其他点的距离之和最小，该和 式显然不会超过w 佑) 的罢，即比( “) 兰- 2 w ( c ) 。文中将这样的点订称为图 z仃 g 的重心。 在化学文献中，w i e n e r 数更多地用于处理无环有机分子的结构问题( 具体可 见文献 8 ，9 ，1 0 ，1 l ，1 2 】) 。这种无环的有机分子图就是我们下述的树。因此， 对树的研究是t v i e n e r 数的研究中最重要的方向之一。 树是连通的无圈图，通常用z 表示。树r 的顶点集、边集分别记为矿仃j 、 乘积图生成树的饴地，数问题 er 丁土小妨设l 矿( r ) l = 珂( r ) 3 ，可知l e ( 丁) l = n ( t ) - i ，日每个点对存存唯一 的路径。 度为1 的点称为悬挂点， 1 个顶点的树t 至少有2 个但至多有胛一j 个悬挂点。 其中只有2 个悬挂点的树称为路，记作只；有n 一，个悬挂点的树称为星图，记作 s 。容易得出，矿c 只，= ( ；+ 1 ，矿c s o ) = ( n - 1 ，2 。 定义1 、每一对不同的顶点都有一条边相连的简单图称为完全图。 在同构意义下，n 个顶点的完全图只有个，记为世。 定义2 、，部图是指这样的图，它的顶点集可分解为，个( 非空) 子集，使任何 一边的两个端点均彳i 同在任一个子集中；完全r 部图是指一个简单图，它的每 个顶点与不在同一子集中的所有顶点均相连，记为k 。，。 定义3 、简单图g i 和g 2 的乘积图g l g 2 是指具有顶点集y ( g 1 ) 矿( g 2 ) 的简 单图，其中( “，x ) 与( v ，y ) 相邻当且仅当或者“= v 且x y e ( g 2 ) ，或者x = y 且 “v e ( g 1 ) 。 我们将足? 递归地定义为：= 民x k ， 箸= k ? 一。类似地， 将c 递归地定义为：c = q g ，四= e c ：一。 图g 的生成树是指g 的生成子图，它同时也是树。可知，每个连通图都包 含至少一棵生成树。在图g 的所有生成树中，存在一些( 至少一个) 具有最小 w i e n e r 数的生成树，这类生成树在经济学刚络的设计、微机网络模型的应用等 方面具有重大的现实意义。d a n k e l m a n n 在 1 3 1 中将w i e n e r 数最小的生成树称为 m a d 树。 本文研究如下问题：给定一个连通图，如何确定其w i e n e r 数最小的生成树? 这是w i e n e r 数研究中的主要问题之一。这一问题不仅对于w i e n e r 数的研究有 着重要的理论和实际意义，同时也具有其它的一些实际背景( 如经济网络的设计 等 1 4 1 ) 。一般而言，这一问题具有相当的难度，即使是对于一些很特殊的图类如 超立方体，也还是一个尚待解决的问题。事实上，d o b r y n i n 在【1 4 中构造了超立 乘积图牛成树的w i e n e r 数问题 方体的两类w i e n e r 数“很小”的生成树。进一步地，d o b r y n i n 猜想这两类树都 是w i e n e r 数最小的生成树。下文列出几个相关的已知结论： 1 e n t r i n g e r 等人在【1 5 】中证明，在给定顶点数为n 的树中，w i e n e r 数最 大的是路e ，而最小的是星图。 2 对于连通图g 的任一生成树丁，都有w 仃，w 佑j 。e n t r i n g e r , k l e i t m a n ， 和s z e k e l y 等 1 6 1 q a 有如下的结论： 不妨设g 的顶点数为n ，则其生成树满足wf r j 2 ( 1 一二) 矿( g ) ，等号 n 成立当且仅当g = 疋且丁= k 1 + 。 3 b u r n s 和e n t r i n g e r 在 1 7 1 q b 给出完全，部图的具有最小w i e n e r 数的生 成树的具体刻画：1 i 妨设完全，部图g2 k 。的顶点划分为 k ，砭，一) ， r 2 ， l l = 珥 ( 1 i s ，) ， 啊 1 ，则丁为恰有两个非悬挂点的生成树，其中一个的度为n - r 6 ， 另一个为n l ，且其w i e n e r 数为n 2 3 ”+ 2 + m 一砰。 利用归纳推理及递归关系，本文对更一般的且具有良好拓扑性质和较高的网 络模型应用价值的乘积图，如g l g 2 、霹、凹等，构造了相应生成树及其 w i e n e r 数的值，以期获得这些乘积图w i e n e r 数最小的生成树。这些生成树的 w i e n e r 数的值分别满足下列关系： ( i ) w ( t o l x g z ) ( 2 一慢) ( ) + 彳( 强) ( i i ) ( ) = h 2 m - i ( r a n m 一1 ) + ”1 ( i i i ) ( 珐) 2 (-n-1)ntm+3m(n2-1)n2m-1+(n+1)nm当聆为奇数时 1 2 3m(n2-n)-n2-2n2+(n2+2)n，当竹为偶数时。 1 2 ( n 一1 1 这些结果推广了d o b r y n i n 关于超立方体的结果。文章的最后，我们还分析 乘积图牛成树的w i e n e r 数问题4 了霹、四的渐进性质。 乘积图生成树的i h e n e r 数问题 第二章乘积图g 1 g 2 定义4 、设五，瓦分别为g i ，g 2 的生成树，d 为图g l 的重心。g 1 g 2 的生 成树强。吗顶点集为v ( g 。) x v ( g 2 ) ，( ( ，v p ) ，( 。喁) ) 是生成树。g 2 的一条边当 且仅当p2g 且( “。，u n ) 是墨的一条边，或“。= “。= 甜日( v ，k ) 是正的一条边。 以如下的圈c 4 ，c 3 为例，说明求( ，q ) 的过程： u g1 4 u 2u 3 t1 v v g 2 t 2 其中m 、3 ) 1 = n ，五、五分别为c 4 、c 3 的生成树。 v 3 v3 乘积图生成树的w i e n e r 数问题 6 c u l ，) ( u 4 ，v 2 ) ( u 2 ，v 3 ) g q 由定义4 可知，c d x q 的生成树如下： ( u 3 ，v 2 l ( u 1 ，v 1 ) 乇。c 3 ( u 3 ，v 3 ) ( 。u 。3 、，v3 ) z 煦2 ，v 3 ) 、 ( u 4 ，v 3 ) - 一逝u 1 ，v 3 ) 、- 其中，由( “，v j ) ( i = 1 ，2 ，啊) 构成的生成树称为第j 层子生成树， ( i ) 当两点在同一层子生成树时，所有点对的距离之和为矿( 正) ，共有n ：层子生 成树，故总和为啦形( 王) 。 乘积图生成树的w i e n e r 数问题 7 ( i i ) 当两点分布存b 口两层不同的子生成树中时 d ( ( “。，) ，( 蚝，) ) = d ( ( 。，v p ) ，( u l ，v p ) ) + d ( v p ，k ) + d ( ( “l ，k ) ，( ，心) ) 所以， 善薹d f l u ，v p ) “喝) ) z d t l ( u 1 ) + n t d ( v p , ) + 啊d ( ( “，屹) ，( “。，k ) ) 】 n = l n l d 7 。( u 1 ) + n z l d ( v p ) + q 4 ( “1 ) 2 m 如( “1 ) + r h 2 d ( v p 喝) 其中d ( v p ，v q ) 为正中两点v ，与k 的距离，共有c 。2 对这样的点对，因而，分 布在不同层的两点的距离总和为c ，2 2 码4 。( 坼) + 砰( e ) 综合( i ) ( i i ) ，g 1 g 2 的生成树死，。：的盯印盯数彤( 死，吗) 如下： 矿( 。呸) = 矿( 7 i ) + c ，2 2 1 d q ( u ) + 砰矿( 正) ( 1 ) 由于“。为五的重心，故有吐( “。) 二矽( 正) ，代入上式得： n 矿( 。呸) n 2 w ( t i ) + 2 n 2 ( n 2 1 ) 肜( z ) + 砰肜( 五) = ( 2 一) 矽( 正) + 砰矿( 正) 因此得到形( g l x g 2 ) 的一个上界： ( g lx g 2 ) 形( ，q ) ( 2 一) 形( 正) + 砰矿( 正) 由上述运算，可得到以下的命题： 命题1 、连通图g l 、g 2 ，i 矿( g 1 ) l = 强，l 矿( g 2 ) i = n 2 ，设7 j 、e 分别为g l 、 g 2 的生成树，q 为依定义4 构造出关于g ，g 2 的生成树，则其g j o n e r 数满 足如下关系： 矿( g l g 2 ) 肜( 强。g 2 ) ( 2 一心) 形( 正) + 砰形( 正) 乘积图生成树的w i e n 盯数问题 8 第三章两类特殊的乘积图 3 1历个n 阶完全图的乘积图霹 显然，毛的脬即盯数最小的生成树为s ，且矿( 最) = 一1 ) 2 我们将最中 的非悬挂点标号为1 ，其它点随意标号，下图所示为墨的标号： 4 2 则有如f 定义： 定义5 、 k ? 的生成树k 定义为： ( ( 五。五，l ) ，( _ | i ，如一，k 。) ) 是生成树 的一条边当且仅当下列条件之一成立： ( 1 ) ( l ，k ) 为s 的一边，且z = 岛( f - 1 2 ，m 一1 ) ； ( 2 ) l = k = 1 ，( 厶。k 一。) 为s 的一边，工= 砖，( f - 1 2 ，m 一2 ) ； ( 3 ) 一。= k 一= 厶= k = 1 ，( 厶。k ：) 为瓯的一边，工= 屯，( i 2 l ，2 ，坍一3 ) ； - - 一 一一 ( m ) ，= 毛= 1u = 2 ，m ) ，( ，皇) 为& 的一边； 其中j ，e l 2 ，l 。 以嗣为例，根据上述定义，如下图所示： 乘积图生成树的晰p 瑚r 数问题 9 由定义可知， ? = e j 翠。1 利用( 1 ) 式可推得 矽( ) = n m - i ( n - 1 ) 2 + 略- 2 n ( ”一1 ) + 疗2 ( ) 2 拧”1 0 1 ) 2 + ( n m - i _ _ 1 ) 一1 ) + n 2 w ( 一) 即得到关于m 的一个递归式： 乘秘图牛成树的w i e n e r 数问题1 0 矿( ) 一”2 ( 一，) = f m - 1 0 1 ) ( 一1 ) ( 2 ) 同理有 ( 1 ) 1 1 2 矿( 一：) = r i m - 2 ( 一1 ) ( n ”1 1 ) ( 3 ) ( 2 ) 一月2 ( 3 ) 得： ( ) 一2 竹2 矿( ) + 丹4 矿( k ：) = 鱼专垡n “ ( 4 ) 利用母函数法求出肜( 乙) ，具体步骤如下： 其对应的特征方程为 x 2 2 n 2 x + 行4 ：0 特征根为z = 珂2 ( 二重根) ， 故其特解形式为矿( ? ) = 爿矿，将其代入( 4 ) 式可得： 4 疗m 一2 h 2 a n m - i + 胛4 - a - n m - 2 ：( n - 1 ) 2 ”m 解得a = 一1 因此矿( l 。) 的通解为 九 “n ( 墨? ) 2 4 ( 忍2 ) 。+ 4 m ( 胛2 ) ”+ h ”1 ( 5 ) 另一方面，由( 1 ) 式可直接求出 ( ) = n ( n 一1 ) 2 + e 2 n ( n 1 ) + h 2 一1 ) 2 = n ( n 一1 ) 2 ( 2 n + 1 ) = 2 n 4 3 n 3 + , ( ) 2n 2 ( 疗一1 ) 2 + 弓2 n ( 门一1 ) + 疗2 矿( ) = ”2 ( n - 1 ) 2 + n 2 ( n 2 - 1 ) ”( n 一1 ) + n 2 n ( n - 1 ) 2 ( 2 圩+ 1 ) = n 2 ( 聆一1 ) 2 ( 3 n 2 + 2 n + 1 ) = 3 n 6 4 n 5 + ”2 将上面两个初始值代入( 5 ) 式得 f a i n 4 + 4 2 n 4 + n = 2 n 4 3 n 3 + ” 1 4 胛6 + 4 3 心6 + 玎2 = 3 n 6 4 n 5 + 2 解得 4 ：，4 ：盟 代入( 5 ) 式得 乘积图生成树的w i e n e r 数口j 题 w g ? ) 2 胛2 ”一( 研”一所一1 ) + ”“一1 因此，我们有关于j 翠的如下命题： 命题2 、对于埘个月阶完全图e 的乘积图霹，为依定义5 构造出的关于霹 生成树，则它的w i e n e r 数满足如下关系： w ( k 2 ) 矿( ) = n 2 m - i ( r a n m 一1 ) + n ”1 容易彳导出 孙”斗o 。时， 矿( ) 一唧。磐。等_ 1 ) 。 由于n 维超立方体q = k 2 q o o b r y n i n 等在 1 4 中就q 构造了两类生 成树，具体如下： 方法一：设础为”一1 维超立方体q 一。的m a d 树。用长为l 的路替代础中 的每个顶点所生成的新的图形印为q 的生成树，记为碍1 ，可以算出： w g - ) ：4 w ( t j 0 + 掣 ( 6 ) 方法二：设瑶为n - 1 维超立方体q 一，的m a d 树。耀为稿的拷贝，k _ 1 、吒一。 分别为7 = 、瞄的重心，连接k - l 、t _ l ，即得到q 的另一棵生成树巧2 ，同样 地，可以计算： 矿( 巧2 ) = 2 形( 聪) + 2 ”( k 一- ) + 4 ”1 ( 7 ) 对( 6 ) 作递归，即可求得： w g 1 ) = 婴甜一l 对( 7 ) 作递归，即可求得： 矿( 巧2 ) = 掣掣”一。 由此可见，用方法一和方法二构造出的q 的生成树的g i e n e r 数相等。 由于n 维超立方体q = n ，将q 代入上述命题2 中得到的结果也是 ( q ) 兰w ( t o ) ：n - - 1 4 ”+ 2 “。 乘积图牛成树的w i e n e r 数问题 这说明命题2 推广了d o b r y n i n 等关于超立方体的结果。 容易得出，当h j 。时，w ( z q ) n 2 2 n - i ( 即。，l i m 以w 2 ( q ：，) 。= 1 ) 。 尚待解决的问题： 依照定义5 构造出的生成树是否就是的w y e n e r 数最 小的生成树? 这只是本文的一个猜想，有待于进一步的证明。 3 2 册个n 圈的乘积图c 显然，e 的生成树为只。只的重心a 为中间的点( 当n 为奇数时) ，或中间 的两点之一( 当胛为偶数时) 。因此，有( 只) 噍( 口) ! ： ，当”为奇数时； 等， 当”为偶数时。 n ( n + 1 ) 一1 ) 6 我们将只的重心标号为1 ，其他点随意标号，直到行，则有如下定义： 定义6 、( ? 的生成树毛定义如下： ( ( ，五，l ) ，( 南，k 2 ，屯) ) 是生成树乙的一条边当且仅当下列条件之一成 立： ( 1 ) ( j m ，k m ) 为只的一边，且工= 毛( f = l 2 ，m 一1 ) ； ( 2 ) 厶= k = 1 ，( 厶。吒一。) 为只的一边，工= t ，( i = 1 ，2 ，m - 2 ) ； ( 3 ) l 一。= k 一。= 厶= k m = 1 ，( l 。k m 一：) 为 的一边，工= k i ， 0 = i 2 m 一3 ) ； ( m ) z = t = i ( f _ 2 ，m ) ，( z ，t ) 为的一边 其中厶，屯 1 2 ，” 。 以q 为例，根据上述定义，砀如下图所示 乘积图生成树的孵p 搬r 数问题 1 3 l ，1 ) j 托l ( 2 ，i 。5 )( 3 ，l ，3 ) f 1 3 ，1 ) 4 。1 ) 乘积倒生成树的w i e n e r 数问题 1 4 以下就行为奇数的情形讨论缈( c ? ) 的一个上界： 将g = ex c ? 。代入式( 1 ) 式得： c 乏? ，= 一”矽c 只，+ ( ：”。 z ”- 如c 日，+ 一2 - 矿c = 。， 矿1 t n ( n - 1 ) ( n + 1 ) 坩，( n “- 1 - 1 ) 等村州乇。 o斗 、o 堂塑1 业2 + n z 形( 纠 、( ： 即得到关于m 的一个递归式 同理有 ( 毛) 一n 2 r v ( 砭- r ，) = n “( n 2 - 面1 ) ( 3 一n m - i - 1 ) ( b ，) 一 2 形( ) = n - ( n 2 - 1 1 ) ( _ 3 n - 2 - 1 ) ( 8 ) 一1 , 1 2 ( 9 ) 得： 矿( i ，) 一h 2 矿乇一：) = n , n - i ( 彪2 1 ) ( 3 n “一1 ) 利用母函数法求出矽( ) ，具体步骤如下 1 2 其对应的特征方程为x 2 2 n 2 x + n 4 = 0 解特征方程得x = n 2 ( 二重根) 故其特解形式为( 砀) = 彳，将其代入( 1 0 ) 式可得 a n m 一2 盯2 a n - - t + n 4 彳n m 一2 ：( n - 1 ) ( n 2 - 1 ) n m 1 2 ( 8 ) ( 1 0 ) 解得爿= 了n + f l ；因此形( 岛) 的通解为 矿( 备) = “确”+ 4 似一2 ) ”+ 等 ( 1 1 ) 由( 1 ) 式可直接求出 形( 乇m 吣) + 掣锄噍( 卅御( ) 乘积图生成树的w i e n e r 数问题 n2(n2-1)(sn-1) 1 2 形( 乇) = ”2 矿( 只) + 坌尘季生2 吨( 口) + 玎2 矿( 砀) = 兰：( 竺：二1 2 1 1 1 ：二翌= 1 2 1 2 将上面两个初始值代入( 1 i ) 式得 f a 。n 4 + 2 + 等= 型等业 【a 1 n 6 + 3 + 等= 型鼍笋塑 解r 沭方稗鲴得 a ：一型 1 1 2 且：盟 4 疗 代入( 1 1 ) 式得 矿( 岛) = ( - n - 1 ) n t m + 3 m ( n 西2 - 1 ) n 2 m - i + 一( n + 1 ) n 当n 为偶数时同样的方法可得 峨) = 巡塑专等业 命题3 、对于聊个n 圈e 的乘积图c ? ，强为依定义6 构造出关于四的生成树 它的w z e n e r 数满足如下关系： ( c 7 ) 矿( 。) ! 二坚二! ! ! ：! 竺f 芝二! 塑：! 堕! ! ! ：当n 为奇数时； 1 2 3m(n2-n)-n2-2n2+(n2+2)n”，当聆为偶数时。 1 2 ( n 一1 、 容易得出，当，z 为奇数，且m ，z 斗。时，( 乇) m ( n z ”+ t 了_ 一n 2 m - 1 ) ( 即 。!lim旦m(n2,+t_n2m-，)=1)； m m 。2 l j ； 乘积图生成树的w i e n e r 数问题 当h 为髋且m ，”_ m 峨卜竿卿腮裂1 ) 。 尚待解决的问题：依照定义6 构造出的生成树0 是否就是c ? 的w i e n e r 数 最小的生成树? 这只是本文的一个猜想，还有待于进一步证明。 乘积图生成树的w i e n e r 数问题 1 7 参考文献 1 lw i e n e r ，s t r u c t u r a l d e t e r m j n a t i o n o f p a r a f f i n b o i l i n g p o i n t s , j ，a m c h e m s o c ，6 9 ( 1 9 4 7 ) ，p 2 h o s o y a ，h 1 7 - 2 0 t o p o l o g i c a li n d e x an e w l yp r o p o s e dq o a n t it yc h a r a c t e r i z i n g t h et o p o l o g i c a n a t u r eo f s t r u c t u r a li s o m e r so f s a t u r a t e d h y d r o c a r b o n sb u l l c h e m s o c j p n 4 ( 1 9 7 1 ) p 2 3 3 2 2 3 3 9 3 g u t m a n ，i j s e r b c h e m s o c 4 g u t m a n ，i t h et h e o r yo ft h e a n dp o t g i e t e r j h ：毗e n e ri n d e xa n di n t e r m o l e c u t a rf o r c e s 6 2 ( 1 9 9 7 ) ，p 1 8 5 1 9 2 y e h ，y n ，l e e ，s l a n dl u o ，y l ：s o m er e c e o tr e s u l t si n w i e n e rn u m b e ，i n d i a nj c h e m 3 2 a ( 1 9 9 3 ) 。p 6 5 1 6 6 1 5 n i k o l i c ，s ，t r i n a j s t i c ，n a n dm i h a l i c ，z ：t h ew i e n e ri n d e x d e v e l o p m e n t s a n da p p l i c a t i o n & c r o a t c h e m a c t a6 8 ( 1 9 9 5 ) p 1 0 51 2 9 6 e n t r i n g e r ，r c ，j a c k s o n ，o e a n ds n y d e r ，d a ：d i s t a n c ei ng r a p h s c z e c h o s l o v a km a t h 7 p l e s n i k ，5 t h e o r y8 ( 1 9 8 4 ) ， 8 g u t m a n ，i c h e m s o c 6 2 ( 1 9 9 7 j 2 6 ( 1 9 7 6 ) p 2 8 3 2 9 6 咖t h es u mo fa l ld i s t a n c e si n 日g r a p ho rd i g r a p h , j g r a p h p 1 - 2 1 a n dp o t g i e t e r j h ：w i e n e ra n di n t e r m o l e c u a rf o r c e , j s e r b ) ，p 1 8 5 1 9 2 9 g u t m a n ，i ，y e h ，y n ，l e e ，s l a n dl u o ，y l ：s o m er e c e n tr e s u l t si n t h et h e o r yo ft h ew i e n e rn u m b e r , i n d i a nj c h e m 3 2 a ( 1 9 9 3 ) ，p 6 5 1 6 6 1 1 0 r o u v r a y ，d h ：s h o u l dwh a v ed e s i g n so nt o p o l o g i c a li n d i c e s ? i n ：r b k i n g ( e d ) ，c h e m i c a la p p t ic a t i o no ft o p o l o g ya n dg r a p ht h e o r y ，e l s e v i e r ，a m s t e r d a m ， 1 9 8 3 2 5 5 1 1 9 ) ( 1 2 r o u v r a y d h ：p r e d i c r i n gc h e m i s t r yf r o mt o p o l o g y , s c i a m e r 1 9 8 6 ) p 4 0 4 7 r o u v r a y ，d h ：t h eb 1 0 d e l j n go fc h e m i c a l i n d j c e & j c o m p u t c h e m 8 ( 1 9 8 7 ) ，p 4 7 0 4 8 0 1 3 d a n k e l m a n n ，p ：an o t eo nm a ds p a n n i n gt r e e s ( s u b m i t t e df o rp u b l i c a t i o n ) 乘积图生成树的聊 数问题 1 8 1 4 a n d r e y a d o b r y n i n ，r o g e re n t r i n g e ra n di v a ng u t m a n ：w i e n e r i n d e xo f t r e e s , a c t aa p p l i c a n d a em a t h e m a t i c a e6 6 ( 2 0 0 1 ) ，p 2 1 1 2 4 9 1 5 r c e n t r i n g e r ，o e j a c k s o n ，d a 8 n y d e r ：d i s t a n c ei ng r a p h s j c z e c h o s l o v a km a t h j 1 9 7 6 ，2 6 ，p 2 8 3 - 2 9 6 1 6 e n t r i n g e r ，r c ，k l e i t m a n ，d j a n ds z e k e l y ，