極小ABC指數樹的搜索與刻畫.pdf

1、分子拓撲指數（分子圖的拓撲不變量）被廣泛地應用于理論化學的定量結構-性質/活性關系(QSPR/QSAR)研究，是現代化學圖論中最活躍的研究領域之一.
　　1998年Estrada等人提出分子連通性指數，簡稱為ABC指數.令G=(V，E)為一簡單連通有限圖，其ABC指數定義為:ABC(G)=∑vivj∈E√[d(vi)+d(vj)-2]/[d(vi)d(vi)],
　　其中d(vi)為G中的頂點vi的度.ABC指數已被證實和烷

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

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

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

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