（应用数学专业论文）树按harary指标的排序.pdf

中文摘要 摘要 1 9 9 3 年p l a v g i de ta 1 和i v a n c i u ce ta 1 分别独立地介绍了一种重要的分 n n 子拓扑指标，p l a v g i 6e ta 1 将其命名为h a r a r y 指标：h ( g ) = r d 0 = i = 1 j = l r d o ，其中当i 不等于j 时r d i j 表示顶点地，叱的距离的倒数，否则为 i o ， d 矿( )角) ” n y ( w )v ( 岛， 当b = d 即u c ( t ) 时取到等号 即h ( t c ，) 2h ( t ) ，当且仅当u c ( t ) 时等号成立口 注：d 。指顶点u r 在树t 的距离，d 乞指顶点1 1 , ，u 在树r 的距离 第2 章一些相关的树。4 表示对t 的每个顶点进行求和 0 y ( r ) 引理2 1 2 树t 兀，如图2 所示，p 1 ，马是连接在顶点w 的两条悬挂 路i p l l i 岛i + 2 ，令e = u d 是只上的悬挂边，z 是马上的悬挂点，t o 是通过以下两个变换得到的树： ( 1 ) 收缩边e = u v ； ( 2 ) 在顶点z 添加一条悬挂边x v ； 则h ( t o ) 日( t ) 证明日( 死) 一日( t ) 2 | ，看舢( 南一丽1 ) o ， 则h ( t o ) 日( 丁) 口 图2 树r 中顶点钉的分支是指由u 的邻点生成的极大子图，c ( t ) 称为r 的 中心，由丁的顶点组成，c ( t ) 中的顶点到其它非中心顶点的距离尽可能的 相等，图s ( n m ) ? 3 m n i 是星图的剖分图，有几个顶点且中心只有一 个顶点“中心u 的m 个分支均由长度为【等j 或者等 的悬挂路构成 第2 章一些相关的树 定理2 1 3 若t 磊，且有k 条非悬挂边，2sk n ，则 h ( s ( n ，n 一1 一七) ) 之日( t ) 当且仅当t = s ( 礼，礼一1 一k ) 时等号成立 5 证明设图类r 为剖分星图，即： t 7 五，t y ( t ) ，且d ( u ) = m 2 ，d ( v ) 2 ，秽v ( t ) u 显然，r t ，s ( n ，m ) t 下面考虑树t 不属于图类r 设? 2 0 c ( t ) 由牡。长成树t ，伽称为树t 的根在r 中至少可找到这样的一个顶点 u 1 ，让l “o ，满足： 由u 1 作为起点可找到一条路只= t | 1 乱2 t i k ，满足 1 d ( u 1 ) = t l 3 ， 2 连接在u 1 的t 1 个分支中，除了包含顶点u o 的分支外，其余t l 一1 个 分支均是悬挂路 令h i = u s ，秽1 ，y 2 ，y k ，牡l 是连接顶点u o ，牡l 的路 ( 1 ) 若d ( v i ) ，i = 1 ，2 ，k ，则把连接在u 1 的任意t 1 2 条悬挂路平移到 顶点u o ( 2 ) 若坳，v 1 ，忱，仇中至少有个顶点的度大于2 ，设 ( i ) 是离顶点u 1 最近的度大于2 的顶点则把连接在仳1 的任意t l 一2 条悬挂路平移到顶点札t 步骤( 1 ) 或者( 2 ) 称为平移步骤，且通过移步骤得到的树记为丑 下面证明日( 丑) 日( t ) 平移步骤后顶点u 1 连接着一条悬挂路设为p i = 仳1 ，w l ，w 2 ，伽知，且悬 挂路p l 不包含顶点钆o 设路e 1 是由顶点u 1 出发过顶点u o 的另一条路，且路q 1 的另一个端点 第2 章一些相关的树 度为1 ，显然u l 1h = v o ，l q l i 之l h i 一1 设d u 代表顶点让，u 在树t 的距离，以埘指顶点t l ，u 在树丑的距离 日( 噩) 一h ( t ) = ，吾纠。瓦加氍，( 彘一赤) + 。圣品加训蒙讹。，( 壳一去) + 。曼。，【。瓦加y 乏u n ，瓦1 一。氍加矿篆u 乃，壳】 显然珑u 0 根据引理2 1 可得 6 荒加y 篆u r ，壳一。瓦加y 蔷u a ，击 0 则有日( 3 1 ) 一h ( t ) 0 ，即日( 乃) 日( t ) 若噩，则停止；若丑还不属于，类，则在丑中可以找到顶点 札2 满足上述条件( 1 ) ，( 2 ) 通过如上类似的平移步骤可得到树死，而且 日( 正) h ( t 1 ) ；再对树正做判断依此进行下去，最终可把树t 化 成已，使得已属于r 类，而且日( ) 日( t ) 根据定理2 1 。3 树b 最终可化成图类s ( 死，几一l 一七) ，且h ( s ( n ，n - x - k ) ) 2 h ( t n ) 当且仅当死= s ( n ，n 一1 一k ) 时等号成立 口 定义2 1 4 若t 瓦，且佗3 ，令若e = u u ，是r 的一条非悬挂边令 丑和乃是t e 的两个分支，u t i ，u 死，t o 是由t 经过下面的变换得 到的 ( 1 ) 收缩边e = u v ； ( 2 ) 在顶点u ( = u ) 添加一条悬挂边； 第2 章一些相关的树 7 步骤( 1 ) 和( 2 ) 称为t 的边递增变化( 见图3 ) 若而可由t 经过一步的 边递增变化得到，则把这种变化记为t _ 图3 ：树t 的边递增变换 定理2 1 5 令t 五，n 3 ，且至少有一条非悬挂边，若t 死，则 日( t o ) 日( t ) 证明令e = u v 是2 的一条非悬挂边，i i 和l j 是，一e 明网个分_ 叉， u 噩， 正，令t o 是由t 经过收缩边e 并且在顶点u 增加悬挂边e 7 得到 的，有 日( t ) = 日( 丑) + 日( 正) + ) 瓦1 x e v ( t ,+ y e 法v) 赤 )( 乃) 。 + ，蚤三南 z y ( n ) u ) 掣y ( j r 2 ) 口 日( 乃) = 日( 丑) + h ( 死) + z e v ( t 。) 壳+ 掣赢) 南) 掣y ( 乃) 1 + ； 南 x e v ( t , ) t v e v ( t 2 ) v ” 根据图3 可得到 z 瓦) 瓦1 = 。蒜，琢1 ，v v ( t 2 ) 瓦1 2 y v ( t 2 ) 南z ) 风z z ) 哦zv 厶) 仇vy 厶) 砚， 第2 章一些相关的树 则日( 死) 一h ( t ) 2 剁磊m 则葛砺1 一善y 品y e v ( t 2 ) l v 南霉y ( n ) u ，v y ( 丁) 。7善y ( n ) 仳 8 = 。y 品y 葛似瓦1 忑一霉y 品似，y 磊上d = i t n2 y 高y 禹 t ， d 旷1霉y 函 性 f ，函 定理得证 口 通过定理2 1 5 ，对于死中至少有一条非悬挂边的树t ，通过重复边递增 变化可以化成星图晶，因此也可以得到日( 晶) 日( t ) 死可以按照非悬挂 边数进行分类令砭表示有n 个顶点，且恰好存在i 条非悬挂边的树则 瓦= u 互显然，集合霹只包含星图又，而砰q 只包含路r 对于任意 树t z ，i = 1 ，2 ，几一3 ，可以对树t 重复i 个步骤的边递增变化，最 终化成星图& 集合霹和砰只包含如图4 所示的两种图类，记为砭f 和 譬刚对于t 。l d o ，满足i + 歹= n 一2 ，且1 i ，歹n 一3 ，而对于譬郇，满足 r + s + t = 仃一3 ，r ，t 1 ，s 0 砰有两种形式的图类，记为砭乙。，弛。和砭l 。蕊驰( 如图5 所示) ，且 1 1 + m l + p l + q l = 佗一4 ，p l 0 ，1 1 ，m 1 ，q l 1 ， 1 2 + m 2 + 沈+ 口2 = 竹一4 ，1 2 ，q 2 1 ，p 2 ，m 2 0 第2 章一些相关的树 m l p lg l ，- 一 、， 、，_ l 。、 t 0 ) ， 图4 “ 图5 s ，- 一k - _ - 、 ，l 、，- - 一， p 2 r ( 2 ) 9 )g 第2 章一些相关的树 l o 定理2 1 6 令e = t 是树t 的一条边，a 表示t - e 中包含顶点u 但是 不包含u 的部分b 表示t e 中分包含顶点 的部分而s 是与u 连接的 悬挂点组成的集合，且y e s ( 见图6 ) 定义t o = t 一 u s j s s ) + v s s s 则 h ( t o ) 一日( t ) = i s i 证明令t i = t s ， 【训(瓣1一_ldua+1)+(南一丽1肛1aev(a b e ：v ( b - n )一1 ( 1 ) 日( t ) = 日( r ) + 耋s + ( 2 ) h ( t o ) = 日( r ) + 兰s + ( 1 ) 式- ( 2 ) 式就可得到结论 ( a e v ( a - u ) 比+ 1 ) + ( b v ( b - u ) d 。+ 2 ) + b e v ( b - u ) 图6 定理2 1 7 当0 s t t 一5 ，t t 6 ，则 d 曲+ 2 d 曲+ 1 日( 置卵一4 一。) 日( 砭8 ，r t - - 5 - - 8 ) 日( 2 笋卜f 笋? ) 证明令t 叠吖，t o 珞1 , s , t - 1 ，则 口 丁 第2 章一些相关的树 1 1 h ( t o ) 一h ( t ) = 【1 + + 1 ) + ( s + 1 ) + ( r - 1 ) 1 一【1 + ，- + ( s + 1 ) + t 】 = i 1 ( t 一7 + 1 ) 若t 7 一1 ，则h ( t o ) 一h ( t ) 0 ，当且仅当t = r 一1 时等号成立 口 定理2 1 8 令t 叠础，t o 瑶1 8 1 p 当n 5 ，且r + s + t = n 一3 ， r ，t 1 ，s 0 ，若s 鸶一2 ，则h ( t o ) 日( r ) 证明根据定理1 5 可得 h ( t o ) 一即) = 云一丢+ 西t = 三一罟+ 砉+ 丢( r = n 锄- s ) 若h ( t o )日( t ) ，则；一罟+ i t + 0 ，即s 詈一i + 至3 ，面当t 取到最小 值即t = 1 时，詈一i t + ；取到最大值为 有h ( t o ) 且( ，) ，定理得证 i n i 9 ，所以当s 一2 1 詈一i 亡+ i ， 性质2 1 9 令t 蟹。一3 一r - “，r 1 ，则 即) - 【百n 2 + 等+ 三+ 三一百n t 一互1 】+ 丢( r - - n + 主+ 2 ) 口 对于图类t t _ 2 。一3 一，- t t ，7 _ 1 ，固定t ，根据上式可对此图类的h a r a l y 指标大小给出一定的顺序， 1 若t 为偶数，则 h ( t l , n - 4 - t , t ) 日( 砭n - 5 - t , t ) h ( 一扣，。) 日( 瑶+ l ，n 一2 川，。) = h ( 巧2 一。- c 吡) 日( q - 2 j l - - 3 ，) = h ( 联2 一) 日( 昝j - 1 加2 - c - 【丁2 n - - t 儿孕j ) = 日( 嗨- 一2 十f 字t 2 , 1 - t 1 ) 第2 章一些相关的树 1 2 2 若t 为奇数， a ) 若2 n t 兰l ( m o d 4 ) ，则 日( 咒舻4 一t ，t ) 日( 露。一5 t t ) 日( 雩+ ；，。一；。一3 1 ) 日( 稚3 - - t , o , t ) 日( 雩+ 扩2 h h ( 砰一。- t ，r ) 日( 蟹+ l 扩；。一s 日( 昝1 _ l ，n _ 2 _ - 竽1 ，f 罕1 ) b ) 若2 n t 三3 ( m o d 4 ) ，则 日( 哗j - l p 2 - f - ! ￥儿竽j ) 日( 置n - 4 - t , t ) 日( 乏n - - 5 - - t , t ) 日( 焉一肛争2 日( + ，。；。一3 ，。) 日( 瑶3 - t , o , t ) h ( + ，。一；。一4 ；，t ) 日( 砰一4 t t ，t ) h ( 昝j - 1 扩2 牛【竽儿竿j ) 日( 哗h 旷2 一t 一竽1 i 竿1 ) 第2 章一些相关的树1 3 2 2 一些相关的按h a r a r y 指标排序的树 定理2 2 1 对于只含有一条非悬挂边的讨，n 5 ，h a r a r y 指标大小顺 序如下t 日( 咒n 一3 ) h ( 礁。一t ) h ( 每jr 孚1 ) 证明令t t ；1 叮，不妨设p q ，t o 礓1 口+ l ，设u 是连接在1 ) 0 的 悬挂点，令t o = t 一 t 铷卜+ _ u u l ，则根据定理1 5 可得h ( t o ) 一h ( t ) = 三6 ( q p + 1 ) ，当q p 一1 时，h ( t o ) 一h ( t ) 0 ，即h ( t o ) 日( t ) ，当且 仅当q = p 一1 时等号成立显然，我们就可得到结论 口 定理2 2 2 若t 砰 置。- 5 l ，霹- 4 o ，1 ，砭n _ 6 1 ，砰5 1 1 露n - 7 l ，宠。- 7 2 瑶5 1 0 ，2 ，露- 6 ，2 1 ) ，n 7 ，则 日( 冠。一5 1 1 ) h ( 瑶4 n 1 ) 日( 瑾，。一6 ，1 ) 日( 臻5 i l 1 ) 日( 瑶n 一7 ，1 ) 日( 磋。一7 ，2 ) = 日( 露5 0 ，2 ) 日( 砰一6 ，2 1 ) h ( t ) 证明日( t 2 ，n - 5 , 1 ) = 筹一是+ 矗， h ( 霹- 4 ，o ：1 ) =譬一+ 1 ，46 h ( t 2 1 2 , n - 6 , 1 ) = 譬一芸+ 1 ， 日( 露- 5 ，1 1 ) = 日( t 2 以1 ) = 芷4 一堡3 + 2 击： _ 1 2 ： 芷4 一点1 2 几+ 2 i ：。_ 4 ： 日( t ；2 ，n - 7 , 2 ) = h ( 砰- 5 0 2 ) = 譬一丧饥+ 2 ； 胃( 瑶6 2 。) = 了n 2 一号+ 3 下面只要证明h ( 砰以2 1 ) h ( r ) 即可 第2 章一些相关的树1 4 设t = 叠加不妨设r t ， 情形1 若t = i ，则s 3 r 4 ，根据定理1 7 可得 h ( t l 6 2 1 ) 一日( t ) ) = ( s 一2 ) ( ；一丧) 0 ， 则日( 7 翟6 1 2 1 ) h ( 丁) 情形2 若t = 2 ，则821 ，n 一6 r 3 ， 胃( 蟹州，- ) 一( 砰祀) = 日( 露_ 6 ，2 ，1 ) 一日( 叠卧l ，。) 善7 - 石十砭， = ( s 一1 ) ( ；一老) ， 则日( 7 翟6 ，2 1 ) 一日( 丁) = 日( 砰一6 ，2 ，1 ) 一日( 譬啦) = ；+ 矗+ ( s 一1 ) ( ；一老) = ：r s 一熹s 一刍+ 西7 = ；( 仃一r 一3 ) 一丧几+ 2 ； ：( n 一6 ) 一丧n + ； = 景一 0 则日( 砰_ 6 2 ，1 ) h ( 丁) 情形3 若t 37 不妨设r t ， 日( 霹。+ ，) 一日( 蟹叫) = 日( 霹- 6 2 ，1 ) 一日( 霹州_ 1 1 ) 则日( 露2 ( 8 = n 一5 一r ) ( n 一6 r 3 ) ( t 一1 ) ( ；+ 丧) ： = ( s + f 一3 ) ( ； 6 2 1 ) 一日( r ) = 何( 砰6 2 1 ) a ) 若r = 3 ：则f = 3 一矗) ， h ( 砰姐) = ( t 一1 ) ( ：+ 矗) + ( s + t 一3 ) ( ；一矗) 一一 至兰主二些塑羞箜塑 1 5 h ( 瑶旺1 ) 一日( r ) = 日( 露一昭1 ) 一日( 叠。，2 ) = + i 1 0 ， 则日( 露- 6 2 ，1 ) 日( 丁) b ) 若r 之3 ，显然t 一1 ， + 蠢，；一西7 o ，s + t 一3 0 ， 则h ( 瑶6 2 1 ) 一日( 丁) 0 ，所以日( 了0 6 ，2 ，1 ) 日( t ) 定理2 2 3 丁t t ( 1 ，。) l - p 1 q l v 、t ，1 ) - - 6 , 0 , 1 ，可2 - 7 , 1 , dn 7 ，则 h ( 硝譬- 6 , 0 , 1 ) h t 、t ( ，1 ) - 7 , 1 , 1 ) h ( t ) 证明日( 可2 - - 6 , 0 , 1 ) = n 2 一j n + 1 孟， 日( 曩2 - - 7 , 1 , 1 ) = 佗2 一几+ 2 罟， 下面只要证明日( t ) 0 情形2 若l 2 ，则口1 ， h ( 曩：+ ，一。口。) 一日( 砭2 毋。) = ( f 一1 ) ( 詈+ 墨+ 盖+ 丧) 0 ， 日( 曩羔+ l 一。p + 。一。，。) 一日( 硝兰+ i 一。霸。) = ( g 一1 ) ( g + 嚣+ 击+ 嘉) 20 ， h ( 曩皇- 7 1 1 ) 一日( 曩：+ l 一。p + 。一，。) = ( p + 口一1 ) ( 詈+ 一 ) 0 日( 删- 7 1 1 ) 一日( 曩裂一= 口 ( 1 - 1 ) ( 詈下卷+ 蠡+ 丧) + ( 口一1 ) ( 3 + 景+ 壶+ 去) + ( p + g 一1 ) ( 詈+ 5 一 ) 0 ， 则日( 矗_ - 7 1 1 ) ( 瓦i ：r ：弘。) 口 第2 章一些相关的树 定理2 2 4t k 识船v u , 上l ，- r ( 2 1 ) ，n - - 7 , 1 哦舾8 ，1 ， 俨9 ，1 ) ，n 1 0 ，则 h ( 哦n - - 7 , 1 ) h ( 砭 n - 8 , 1 ) h t 、t 。( 2 ) ，n - 9 , 1 ) 日( t ) 证明日( t 斑n - - 7 , 1 ) = j n 2 一詈+ i ， h ( 黧n - 8 , 1 ) = ；n 2 一妻n + 2 ， h ( 巧型n - - 9 1 ) = n 2 一老n + 3 壬 下面只要证明日( t ) 日( 哦n - 9 , 1 ) 即可，令t = 曩翌舢 不妨设p20 ，f m g 1 ，显然 t 一6 1 2 ，m ，q 1 ，p 0 情形1 假若l = 2 ，则t = t 屹2 ( 2 2 ) 俨”或者巧兰舻1 0 ，2 ， 日( 砭n 吨。) = i 1 2 一西7n + 3 丢 0 ，则有日( t ) 0 ， ( f _ 。八b 6 1 m 2 - t - - 1 q 2 - 一 ) 0 ，( 口一1 ) ( 6 6 l 。1 m 乏一 ) = 0 ，( m 一1 ) ( b 6 。旦6 6 1 石1 ) = 0 ， 因此h ( 砖 n - - 9 , 1 ) 一h t 上l i ( 2 。) ，p 口) 0 ，则有日( t ) 若7 n 2 ，q21 ，则 0 ，( g 1 ) ( ：+ + 墨一 ) 0 ，( m 一1 ) ( ：+ + 一 ) 0 ， 因此h ( 础n - 9 , 1 ) 一日( 曩裂舢) 0 ，则有日( t ) 日( 置。一3 ) 日( 砬n 4 ) 日( 冠。5 1 1 ) 日( 霹- 4 o ，1 ) 日( 黯。一5 ) 日( 砭。6 1 ) h t ( 2 。) ，n - - 7 , 1 ) h ( 瑶5 。1 ，1 ) 日( 删6 0 1 1 ) 日( t 4 n 1 6 ) h ( 露n - - 7 , 1 ) 日( t 。2 ，n - - 7 , 2 ) = 日( 瑶5 ，0 2 ) h ( 砖 n - - 8 , 1 ) h ( s ( n ，礼一5 ) ) 日( 丁) 证明日( & ) = 日( 丑。一3 ) 礼2 + 等一 ， = i l n 2 + 击n ， 日( t ”1 一。) = 扣2 一击霓+ 2 ， 日( 冠。- 5 1 ) = h ( 砰- 4 i o ，1 ) = ( 冠n 一。) = n 日( t 。2 以1 ) = n 2 一丧n + 西7 ， 礼2 一 n + 1 ， 2 一 n + 2 ， ；礼2 j 礼+ 互3 ， h ( 可型n - 7 1 ) = ( 砰矗1 1 1 ) = j 礼2 一 礼+ 互5 ， 扣2 一 礼+ 2 丧， 第3 章树按h a r a r y 指标的排序， 1 9 h t w ( x 。) - 6 , 0 , 1 ) = 舻一 n + 鼍， 日( 砭。一6 ) = n 2 一专n + 3 ， h ( 疆n - 7 , 1 ) = 舻一丧n + 2 i ， 日( 砭n - 7 , 2 ) = h ( t l 5 ，o 。2 ) = n 2 一丧n + 2 ， h t 、q , 。( ，2 ) ，n - 8 , 1 ) =；礼2 一丧n + 2 ：， 日( s 一5 ) ) = 死2 一言扎+ 2 ， 当礼1 7 ， h ( s n ) 日( t 坍1 3 ) 日( t 。1 ，n 一4 ) 日( 咒n - 5 , 1 ) 日( 露一4 ，0 1 ) 日( t 。1 ，n 一5 ) ， 日( 磋n - - 6 , 1 ) 日( 硝置n - - 7 , 1 ) h ( 瑶5 1 。) 日( 础- 6 , 0 , 1 ) 日( 砭n 一6 ) ， 日( 瑶n - - 7 , 1 ) h ( 砭n - - 7 , 2 ) = 日( 霹- 5 , 0 , 2 ) 。h t 心( 2 1 ) ，n - - 8 , 1 ) h ( s ( n 一5 ) ) 若t 霹，则根据定理2 2 1 ， h ( t )打( t 叩1 7 ) = 譬一西7 礼+ 1 1 i 若t 露，根据定理2 2 2 ， 日( 砭。一6 ) h ( t ) h ( t l 6 ，2 ，。) = 譬一号+ 3 h ( 砭n - 7 , 2 ) = h ( t 2 - 5 , 0 , 2 ) 若t 曩裂概。，根据定理2 2 3 ， h ( 丁) 日( 础- 6 , 0 , 1 ) = 譬一 n + 3 鼍 日( 丁) 得证 口 第3 章树按h a r a r y 指标的排麈 3 2 注记 h a r a r y 指标是连通图的反距离矩阵所有元素和的一半，而w i e n e r 指标是 距离矩阵的所有元素和的一半，因此我们会考虑这个问题； 对于树噩，乃，若w ( t 1 ) t 2 ，是否有日( 7 1 ) 日( t 2 ) 成立? 对于这个问题，有些图是有这样的性质，但是不尽然全是 性质1 f 6 】丁是有n 个顶点的树，则日( 晶) 日( t ) ；日( & ) s 日( r ) 当且仅当时t = 晶时等号成立 性质2 1 1 0 】t 是有礼个顶点的树，且有k 条非悬挂边，则 w ( t ) ( s ( n ，n 一1 一七) ) ；h ( t ) h ( s ( n ，n 一1 一七) ) 当且仅当时t = s ( 他，礼一1 一k ) 等号成立 但是对于一些图h a r a r y 指标越大，其w i e n e r 指标也较大如： 1 ) 日( 露2 “o 。1 ) 日( t 邮1 5 ) ，w ( 露“0 1 ) w ( 礓n 一5 ) 2 ) 日( t ，1 俨6 ) ( 砭n 一7 2 ) 符号说明：露，互，且恰好存在2 条非悬挂边 t 。3 础磊，且恰好存在3 条非悬挂边。 对于树，当其满足一定的性质时，h a r a r y 指标越大，其w i e n e r 指标是否 也较大这是我们所关注的问题目前还没找有到效的性质来刻画这个结论 而上面给出的四个例子为我们往后的工作即刻画h a r a r y 指标和w i e n e r 指标 的关系作个铺垫 参考文献 2 1 r e f e r e n c e s 参考文献 【1 】b z h o u ，d s t e v a n o v i d ，an o t eo i lz a g r e bi n d i c e s m a t c hc o m m u n m a t h c o m p u t c h e m 5 6 ，5 7 1 5 7 8 ( 2 0 0 6 ) 【2 】b z h o u ，i g u t m a n ，r e l a t i o n s h i p sb e t w e e nw i e n e r ，h y p e r w i e n e r a n dz a g r e bi n d i c e s c h e n p h y s l e t t 3 9 4 ，9 3 - 9 5 ( 2 0 0 4 ) 【3 】d o n g ，h ，g u o ，x ( 2 0 0 6 ) o r d e r i n gt r e e sb yt h e i rw i e n e ri n d i c e s c o m m u n i c a t i o n si nm a t h e m a t i c a la n di nc o m p u t e rc h e m i s t r y , v 0 1 5 6 ，b r 3 ，s t r 5 2 7 - 5 4 0 【4 】d j a n e i i 6 ，a m i l i d e v i 6 ，n t r i n a j s t i 6 ，g r a p ht h e o r e t i c a lm a t r i c e si n c h e m i s t r y ( m a t h e m a t i c a lc h e m i s t r ym o n o g r a p h sn o 3 ，u n i v e r s i t y o fk r a g u j e v a c ，k r a g u j e v a c ，2 0 0 7 ) 5 】d p l a v g i 6 ，s n i k o l i d ，n t r i n a j s t i d ，z m i h a h d ，o nt h eh a r a r yi n d e x f o rt h ec h a r a c t e r i z a t i o no fc h e m i c a lg r a p h s j m a t h c h e m 1 2 ，2 3 5 - 2 5 0 ( 1 9 9 3 ) 【6 i g u t m a n ，ap r o p e r t yo ft h ew i e n e rn u m b e ra n di t sm o d i f i c a t i o n s i n d i a nj c h e m 3 6 a ，1 2 8 1 3 2 ( 1 9 9 7 ) 【7 i g u t m a n ，w l i n e r t ，i l u k o v i t s ，a n da a d o b r y n i n ，t r e e sw i t h e x t r e m a lh y p e r w i e n e ri n d e x ：m a t h e m a t i c a lb a s i sa n dc h e r n i c a l a p p l i c a t i o n s 。j c h e m i n f c o m p u t s c i 3 7 ( 1 9 9 7 ) 4 5 1 7 4 5 3 3 参考文献 ( 8 】j d e v i h e r sa n da t b a l a b a n ，t o p o l o g i c a li n d i c e sa n dr e l a t e dd e - s c r i p t o r si nq s a ra n dq s p r ，g o r d o n b r e a c hs c i p u b l ，a m s - t e r d a m ，1 9 9 9 【9 】k b u r n sa n dr c e n t r i n g e r ，ag r a p h - t h e o r e t i cv i e wo ft h eu n i t e d s t a t e sp o s t a ls e r v i c e ，y a l a v ia n da j s c h w e n k ( e d s ) ，g r a p ht h e - o r y , c o m b i n a t o r i c sa n da l g o r i t h m s ：p r o c e e d i n g so ft h ec o n f e r e n c eo i l t h et h e o r ya n da p p l i c a t i o n so fg r a p h s ，w i l e y , n e wy o r k ，1 9 9 5 ，3 2 3 - 3 3 4 【1 0 】l z h a n g ，b w u ，t h en o r d h a u s - g a d d u m - t y p ei n e q u a l i t i e sf o rs o m e c h e m i c a li n d i c e s m a t c hc o m m u n m a t h c o m p u t c h e m 5 4 ，1 8 3 - 1 9 4 ( 2 0 0 5 ) 【1 1 】m v d i u d e a ，m s 。f l o r e s c u ，p v k h a d i k a r ，m o l e c u l a rt o p o l o g ya n d i t sa p p l i c a t i o n s ( e f i c o np r e s s ，b u c h a r e s t ，2 0 0 6 ) ，p 5 7 【1 2 】0 i v a n c i u c ，t s b a l a b a n ，a t b a l a b a n ，r e c i p r o c a ld i s t a n c em a t r i x ， r e l a t e dl o c a lv e r t e x