廣義Randic指標極值圖問題的研究.pdf

1、眾所周知，圖論學科的產(chǎn)生與發(fā)展與化學分子圖的研究非常密切。實際上，若僅考慮原子間的連接關系，則用圖或樹狀圖來表示分子的結構是一件非常自然的事情?；瘜W分子圖理論對于新物質、新材料的研究一直起著非常重要的作用。上世紀末，伴隨科技的飛速發(fā)展和生活水平的日益提高，制造業(yè)和醫(yī)藥領域對于新材料、新藥物的需求與日俱增。如果盲目地合成這些新材料、新藥物不僅造成時間上和經(jīng)濟上的浪費，而且也是不現(xiàn)實的。為了能有目的地、快捷地合成新物質，組合化學再次成為研究

2、的熱點。 化學分子圖的拓撲指標理論是組合化學的一個重要研究分支。所謂分子的一種拓撲指標是從分子圖集合到實數(shù)集合的一個映射i，也就是說，把每個分子圖G對應于一個實數(shù)i(G)，而這種對應往往是通過分子圖的子圖及其計數(shù)來建立的。計算化學家們通過大量的數(shù)據(jù)，用統(tǒng)計方法給出了分子的各種物理化學性質與它的指標值之間的數(shù)量關系。也就是說，一個分子圖的拓撲指標值可以反映分子的物理化學性質和藥物學性質。這方面的研究在理論化學中也稱為QSAR和QS

3、PR理論。 由于映射i的值域可以看作為“活性空間”，具有相似活性的化合物被映射為此空間中相近的指標值，特別地，大量的化合物被映為同一個指標值或相近的指標值。那么一個最重要也是最自然的問題就是：確定某一物理化學性質的活性區(qū)域，即確定拓撲指標的取值范圍，以及指標取得極值時分子圖的結構。弄清楚這個問題有助于試驗化學工作者建立分子圖的數(shù)據(jù)庫，從而有目的地合成新物質。 1975年著名化學家M.Ranid(c)提出了連通性指標，即R

4、andi(c)指標。因為這一重要的拓撲指標和分子的物理化學性質(如分子的沸點、表面積等)和藥物學性質之間有著緊密的關系，近年來得到了特別地重視。 1998年，P.Erd(o)s和B.Bollobás提出了廣義Randi(c)指標的概念，從數(shù)學上發(fā)起這方面的研究，因而引起了許多數(shù)學家和理論化學家的重視，并且得到許多深刻而且很重要的結果。圖G的廣義Randi(c)指標Rα(G)的定義是： Rα(G)= 其中α是任意實

5、數(shù)，d(u)為圖G中頂點u的度數(shù)。目前的研究主要集中于求以下幾類圖的極值和極圖問題：具有給定的頂點數(shù)或(和)邊數(shù)的(連通)圖，樹，化學圖(即最大度不超過4的圖)和化學樹。因為樹和連通圖都是極重要的化學結構，所以本文著重研究樹和連通圖的廣義Randi(c)指標的極值和極圖問題。 本文第二章研究了對于任意實數(shù)α，樹的廣義Randi(c)指標的最小值問題。我們證明了對于階數(shù)n≥5的樹，當α＜0時，星圖Sn具有最小的廣義Randi(c)

6、指標，而當α＞0時，路圖Pn具有最小的廣義Randi(c)指標。同時給出了當α∈[-1，0)時達到第二、三小廣義Randi(c)指標值的樹(類)，分別是彗星圖Pn,n-2和雙星圖S3,n-3。 在第三章，我們首先給出了當α≤-1時具有最大的廣義Randi(c)指標Rα的一類樹的結構性質，在此基礎上確定了所有不多于102個頂點的樹的廣義Randi(c)指標R-1的最大值，及達到最大值的一種樹的結構。這一結果大大擴展了已有的具有最大

7、的R-1指標值的樹的階數(shù)n的范圍(n從20擴展到了102)。當然列出所有階數(shù)為n的不同構的樹是不現(xiàn)實的，所以我們不可能用計算機直接計算所有樹的指標值，然后搜索出其中的最大值。我們的計算方法是對于所有不多于102個頂點的樹，先刻畫出一種達到最大廣義Randi(c)指標值R-1的樹的簡單結構，即分支子樹(去掉樹T中1度點和2度點后所得子圖)是星圖。由這一簡單結構出發(fā)，我們可以利用線性規(guī)劃的方法，設計程序用計算機方便地計算出對于每一個給定的n

8、≤102，廣義Randi(c)指標值R-1的最大值。 在第四章，我們完全解決了L.H.Clark和J.W.Moon提出的關于廣義Randi(c)指標R-1的上界的兩個猜想。因為具有最大廣義Randi(c)指標R-1的樹不是唯一的，所以其嚴格上界問題是困難的，提出多年未能解決。我們證明了limf(n)/n=15/56，其中f(n)是對所有n個頂點的樹廣義Randi(c)指標值R-1的最大值。我們還確定了樹的廣義Randi(c)指標

9、R-1的一個嚴格的上界。我們給出了一系列樹的結構，使得此上界對于無窮多個n是緊的。從而完全解決了樹的廣義Randi(c)指標R-1的嚴格上界問題。 廣義零階Randi(c)指標0Rα(G)是由零階Randi(c)指標推廣而來，對任意實數(shù)α，0Rα(G)=∑v∈V(G)d(v)α。在第五章，我們對連通圖的廣義零階Randi(c)指標的極值問題進行了研究。對于α的不同取值，刻畫了0Rα(G)達到極值時的圖的結構，確定了當α＜0和α＞