对树的Wiener Index判定逆问题的研究

摘 要 Goldman于2000年提出了可以解决树的Wiener Index逆问题的动态规划算法。本文首先分析了树的Wiener Index和其它一些拓扑系数的关系，并利用这种关系对原算法进行了改进，使其在计算量和运行速度方面明显优于原算法。

【关键词】组合化学 Wiener指标 动态规划

1 背景

1947年美国化学家Harold Wiener在研究碳氢化合物的物理—化学性质时，提出了Wiener Index的概念，Wiener Index对研究有机化学的量化机构特性是非常有用的工具。

树的Wiener Index判定逆问题是指：给定一个正整数W，判定是否存在一棵树T，使得w（T）=W。Goldman等人于2000年提出了一个解决树的Wiener Index逆问题的动态规划算法。

本文首先分析了树的Wiener Index和其它一些拓扑系数的关系，并利用这种关系对原算法进行了改进，使其在计算量和运行速度方面明显优于原算法。

2 基本定义和定理

定义：给定一棵树T = （V，E） 它的根为υ ∈V， 它的所有顶点到它根的距离之和是

l （T）= ∑ i∈v d （ i， υ）

令T = （V， E）为一棵树， （v1，v2）为树的一条边。 令T1 = （V1，E1） 和T2 = （V2， E2）为树拿掉边（v1， v2）后形成的两颗新树。 设树T 和 T1的根都是 v1，树T2的根为 v2。对于树的w， l和n值有下面的递归联系：

定理1：

n（T） = n（T1） + n（T2）

l（T） = l（T1） + l（T2） + n（T2）

w（T） = w（T1） + w（T2） + l（T1）n（T2） + l（T2） n（T1） + n（T1）n（T2）

定理2：

（N-1）2≤W≤（N3-N）/6

N-1≤L≤N（N-1）/2

3 对Goldman算法的一些改进

3.1 Goldman提出的动态规划算法

由以上的递归联系，Goldman等人于2000提出了一个解决树的Wiener Index逆问题的动态规划算法：如果每一个W

3.2 对Goldman算法的一些改进

Goldman算法是一个递归算法，运行速度很慢。观察Goldman的算法，我们发现，原算法在对W，L，N进行拆分时对W1，L1，N1和W2，L2，N2的定界范围太大，使得递归次数大大增加了。利用定理2中W，L，N之间的关系可以缩小算法中W1，L1，N1和W2，L2，N2的取值范围。

当（W，L，N）分解成（W1，L1，N1）和（W2，L2，N2）时，可利用定理1中的L和L1，L2的关系，得出L1的下界为MAX（N1-1，L-N2-N2（N2-1）/2）；L1的上界为MIN（N1（N1-1）/2，L-2N2+1）。

同理，可以得出W1的下界为MAX（（N1-1）2，W-L1N2-L2N1-N1N2-（N23-N2）/6），W1的上界为MIN（（N13-N1）/6，W-L1N2-L2N1-N1N2-（N2-1）2）。

通过改进，减少了算法要检验的数量，将其应用到树的Wiener Index判定逆问题，可以减少算法的运行时间。可以给出一个解决树的Wiener Index逆问题的算法：

给定W值，由定理2计算出L，N的上下界。对每一组这样确定的值调用树的判定逆问题的算法T，如果对任一组（W，L，N）值，T的返回值都为0，则说明Wiener Index值为W的树不存在，否则至少有一组（W，L，N）值T的返回值为1。

4 总结

本文首先介绍了树的Wiener Index判定逆问题，接着分析了树的Wiener Index和其它一些拓扑系数的关系，并利用这种关系对原算法进行了改进，并且提出了改进后的算法，使其在计算量和运行速度方面明显优于原算法。

参考文献

[1]H.Wiener，Structural determination of paraffin boiling points，J.Amer. Chem.Soc

[2]Bonchev，D.，Gutman，I.Polansky，O.， Parity of the Distance Numbers and Wiener Numbers of Bipartite Graphs，Commun.Math.Chem.22（1987） 209-214

[3]D.Goldman，S.Istrail，G.Lancia， A.Piccolboni，and B.Walenz，Algorithm strategies in combinatorial chemistry，2000.

作者簡介

张迎（1982-），女，曾获得山东大学硕士学位。现供职于山东省农村信用社黄岛科技中心。主要研究方向为算法分析与设计。

作者单位

山东省农村信用社联合社黄岛科技中心 山东省青岛市 266520