對組合化學中Wiener索引逆問題的研究.pdf

1、組合化學是一門應用在藥物分子設計和分子識別中的新興的重要的技術。它是一種實驗室的方法，目的是通過“大規(guī)模并行”篩選化合物庫以發(fā)現(xiàn)具有某種生物活性的化合物。這種方法的應用主要是基于實驗設計和計算數(shù)學模型的交互。 藥物和其它化合物可以用多邊形模型表示，其中各頂點表示分子的一個原子，而原子間的共價聯(lián)系則用邊表示。這種由化合物的分子得到的多邊形我們稱為分子圖，這個多邊形可以是一條路、一棵樹或者一個普通的圖。定義在這個圖上的指標-Wien

2、er索引，是一個與化合物的物理化學性質密切相關的拓撲系數(shù)。前面對Wiener索引已經作了大量的工作，以前對Wiener索引的研究主要分為兩種類型：圖的Wiener索引問題以及Wiener索引逆問題。 Wiener索引逆問題指：給定一個整數(shù)n，是否存在一棵樹T，使得W(T)=n，以及如何計算更有效率。Wiener索引猜想指：除了有限的集合外，所有的正整數(shù)都是某一棵樹的Wiener索引值。這個猜想至今沒有得到證明，但是研究該問題的理

3、論不斷得到簡化。2000年，Goldman et al借助于索引值之間的遞歸聯(lián)系，提出了一個從較小的子樹構造樹的動態(tài)規(guī)劃算法。該算法雖然可以在理論上解決此問題，但是算法的計算量很大，程序復雜性和運行速度也不太理想。 本文首先對樹的Wiener索引和其它一些拓撲索引的關系進行了分析，并進一步利用這種關系對原算法進行了改進，極大地減小了原算法的搜索空間和遞歸次數(shù)。然后，又對上述猜想作了進一步的研究：通過設計更有效的算法來證明上述猜想

4、。以前的研究都側重于通過枚舉所有可能的樹來證明該猜想，本文通過設計一種新的數(shù)據(jù)類型一樹族，在這種數(shù)據(jù)類型中來證明上述猜想就已足夠。 本文圍繞樹的Wiener索引逆問題展開深入的研究，主要成果如下： 1)對Goldman提出的算法進行了改進，通過比較得出，改進后的算法在搜索空間和遞歸次數(shù)方面都明顯優(yōu)于原算法，并且給出了新算法和原算法在遞歸調用次數(shù)上的實驗對比結果； 2)提出了一種新的數(shù)據(jù)結構-樹族，比較系統(tǒng)的分析了