極小ABC指數(shù)樹的搜索與刻畫.pdf

1、分子拓?fù)渲笖?shù)（分子圖的拓?fù)洳蛔兞浚┍粡V泛地應(yīng)用于理論化學(xué)的定量結(jié)構(gòu)-性質(zhì)/活性關(guān)系(QSPR/QSAR)研究，是現(xiàn)代化學(xué)圖論中最活躍的研究領(lǐng)域之一.
　　1998年Estrada等人提出分子連通性指數(shù)，簡稱為ABC指數(shù).令G=(V，E)為一簡單連通有限圖，其ABC指數(shù)定義為:ABC(G)=∑vivj∈E√[d(vi)+d(vj)-2]/[d(vi)d(vi)],
　　其中d(vi)為G中的頂點(diǎn)vi的度.ABC指數(shù)已被證實(shí)和烷

2、烴的生成熱密切相關(guān)，能夠預(yù)測它們的熱力學(xué)性質(zhì)，已被成功地用于研究烷烴的穩(wěn)定性和環(huán)烷烴的應(yīng)變能等.為了更好地應(yīng)用ABC指數(shù)，首要的一個(gè)問題就是確定ABC指數(shù)在某些特定圖類上的極圖.Furtula等證明了在所有樹中星是唯一的極大ABC指數(shù)樹，然而，刻畫極小ABC指數(shù)樹至今尚未得到解決.解決該問題的一個(gè)有效途徑是重復(fù)“搜索-猜想-證明”過程，即:(1)搜索低階極小ABC指數(shù)樹，(2)猜想極小ABC指數(shù)樹的性質(zhì)，(3)理論證明這些性質(zhì)，(4)利

3、用證明了的性質(zhì)改進(jìn)搜索算法，搜索更高階的極小ABC指數(shù)樹，依搜索結(jié)果修正對極小ABC指數(shù)樹性質(zhì)的猜想并證明之，(5)重復(fù)(4).
　　Gutman等人設(shè)計(jì)了一個(gè)暴力搜索算法;雖然采用了具有400個(gè)CPU的網(wǎng)格計(jì)算，運(yùn)行了150天，該算法僅搜索至。;通過觀察所得的極小指數(shù)樹Gutman猜想n(n≥10）階極小ABC指數(shù)樹應(yīng)具有如下性質(zhì):(1)無2長及以上內(nèi)部路;(2)無4長及以上懸掛路;(3)至多一條3長懸掛路;(4)無1長懸掛路.

4、Gutman等人證明了前三條猜想，我們證明了第四條.我們的結(jié)論是目前已知的極小ABC指數(shù)樹的最重要的結(jié)構(gòu)性質(zhì).Gutman等人又設(shè)計(jì)了一個(gè)非完全搜索算法，搜索至n=700，并依搜索結(jié)果提出了“模7猜想(modulo7 conjecture)”.然而該猜想被Ahmadi等人證明是錯(cuò)的.Dimitrov設(shè)計(jì)了一個(gè)基于度序列的搜索算法，用了15天在普通PC機(jī)上搜索至n=300，修正了Gutman等人的模7猜想.然而Dimitrov的算法并未充

5、分利用極小ABC指數(shù)樹的度序列的性質(zhì)，且在度序列的生成上是遞歸的，無法并行化，隨著n的增大，該算法將不可行.我們證明在給定度序列的樹中B FS(bread-fir st searching)樹是一個(gè)極小ABC指數(shù)樹.我們充分利用極小ABC指數(shù)樹的度序列的性質(zhì)，改進(jìn)了Dimitrov的算法.我們的算法僅需枚舉2％以下的部分度序列，其串行實(shí)現(xiàn)的效率約為Dimitrov的算法的5倍;并且我們的算法易于并行化，新算法的MPI+OpenMP實(shí)現(xiàn)搜