對樹的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