對樹的Wiener Index逆問題的研究.pdf

1、組合化學(xué)是近十幾年逐漸發(fā)展并成熟起來的一門學(xué)科，它將化學(xué)合成、組合理論、計算機輔助設(shè)計融于一體，在短時間內(nèi)將不同構(gòu)建模塊經(jīng)過連接形成化合物庫，再對庫成分進行篩選優(yōu)化，得到可能的有目標(biāo)功能的化合物結(jié)構(gòu)。通過計算機輔助設(shè)計可以極大提高庫的組成并同時控制庫的大小，因而計算機技術(shù)正在組合化學(xué)中發(fā)揮著越來越大的作用。 經(jīng)過長期的研究，科學(xué)家們發(fā)現(xiàn)很多化合物的物理性質(zhì)和化學(xué)性質(zhì)與它們的拓撲性質(zhì)密切相關(guān)。WienerIndex就是一個與化合物

2、的物理化學(xué)性質(zhì)密切相關(guān)的拓撲系數(shù)，它的性質(zhì)已經(jīng)被廣泛應(yīng)用于組合化學(xué)領(lǐng)域中。樹的WienerIndex逆問題是組合化學(xué)中的一個重要問題，Goldman于2000年提出的動態(tài)規(guī)劃算法雖然理論上可以解決此問題，但是算法的計算量很大，程序復(fù)雜性和運行速度方面也不太理想。 本文首先對樹的WienerIndex和其它一些拓撲系數(shù)的關(guān)系進行了分析，并進一步利用這種關(guān)系對原算法進行了改進，極大地減小了原算法的搜索空間和遞歸次數(shù)；在此算法基礎(chǔ)上本