廣義Randic指標(biāo)極值圖問(wèn)題的研究.pdf

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

2、的熱點(diǎn)。 化學(xué)分子圖的拓?fù)渲笜?biāo)理論是組合化學(xué)的一個(gè)重要研究分支。所謂分子的一種拓?fù)渲笜?biāo)是從分子圖集合到實(shí)數(shù)集合的一個(gè)映射i，也就是說(shuō)，把每個(gè)分子圖G對(duì)應(yīng)于一個(gè)實(shí)數(shù)i(G)，而這種對(duì)應(yīng)往往是通過(guò)分子圖的子圖及其計(jì)數(shù)來(lái)建立的。計(jì)算化學(xué)家們通過(guò)大量的數(shù)據(jù)，用統(tǒng)計(jì)方法給出了分子的各種物理化學(xué)性質(zhì)與它的指標(biāo)值之間的數(shù)量關(guān)系。也就是說(shuō)，一個(gè)分子圖的拓?fù)渲笜?biāo)值可以反映分子的物理化學(xué)性質(zhì)和藥物學(xué)性質(zhì)。這方面的研究在理論化學(xué)中也稱(chēng)為QSAR和QS

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

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

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

6、指標(biāo)，而當(dāng)α＞0時(shí)，路圖Pn具有最小的廣義Randi(c)指標(biāo)。同時(shí)給出了當(dāng)α∈[-1，0)時(shí)達(dá)到第二、三小廣義Randi(c)指標(biāo)值的樹(shù)(類(lèi))，分別是彗星圖Pn,n-2和雙星圖S3,n-3。 在第三章，我們首先給出了當(dāng)α≤-1時(shí)具有最大的廣義Randi(c)指標(biāo)Rα的一類(lèi)樹(shù)的結(jié)構(gòu)性質(zhì)，在此基礎(chǔ)上確定了所有不多于102個(gè)頂點(diǎn)的樹(shù)的廣義Randi(c)指標(biāo)R-1的最大值，及達(dá)到最大值的一種樹(shù)的結(jié)構(gòu)。這一結(jié)果大大擴(kuò)展了已有的具有最大

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

8、≤102，廣義Randi(c)指標(biāo)值R-1的最大值。 在第四章，我們完全解決了L.H.Clark和J.W.Moon提出的關(guān)于廣義Randi(c)指標(biāo)R-1的上界的兩個(gè)猜想。因?yàn)榫哂凶畲髲V義Randi(c)指標(biāo)R-1的樹(shù)不是唯一的，所以其嚴(yán)格上界問(wèn)題是困難的，提出多年未能解決。我們證明了limf(n)/n=15/56，其中f(n)是對(duì)所有n個(gè)頂點(diǎn)的樹(shù)廣義Randi(c)指標(biāo)值R-1的最大值。我們還確定了樹(shù)的廣義Randi(c)指標(biāo)

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