化學及網(wǎng)絡中的某些圖論問題的研究.pdf

1、正如我們所知道的，圖論中的圖代表很多含義.因此，圖論有很多方面的應用.例如，如果一個簡單無向圖G=(V,E)的每個頂點代表分子中的一個原子，每條邊代表原子之間形成的化學鍵，這種圖就叫分子圖.分子拓撲指數(shù)以及分子圖的不變量的研究是現(xiàn)代化學圖論中最活躍的研究領域之一.它們能夠被用來描述有機化合物的物理化學特性尤其是藥理特性.自從1947年H.Wiener提出第一個分子拓撲指數(shù)即Wiener指數(shù)以來，數(shù)百種分子拓撲指數(shù)，包括Randic指數(shù)以

2、及廣義Randic指數(shù)，在數(shù)學和化學文獻中被研究.這里，圖G的廣義Randic指數(shù)定義為wα(G)=∑(u,v)∈E[d(u)d(v)]α,其中d(u)表示頂點u的度并且α為不等于0的實數(shù).特別地，w-1/2(G)稱為圖G的Randic指數(shù). 除此之外，我們也通常用一個連通的(有向或無向)圖G=(V,E)作為互連網(wǎng)絡的拓撲結構，這時圖G的頂點代表網(wǎng)絡中的組件，組件之間的通信聯(lián)系用相應頂點之間的連線來表示.網(wǎng)絡中的容錯路由選擇的研

3、究是網(wǎng)絡中圖論問題的研究的一個重要方向.設x和y是(強)連通(有向)圖G=(V,E)中不同的頂點，PG(x，y)是G中(x，y)-路之集，P(G)={PG(x，y)：x，y∈V,x≠y}，B=V×V/{(x，x)：x∈V}.G中路由選擇定義為映射ρ：B→P(G)，(x，y)→ρ(x，y)∈PG(x，y).也就是說，映射ρ給B中的每一點對(x，y)都指定了一條(x，y)-路ρ(x，y).ρ(x，y)稱為路徑.網(wǎng)絡中的路由選擇ρ是預先設計好

4、的，因而必須通過ρ指定的那些路徑來傳輸所有的數(shù)據(jù).因此，當容錯網(wǎng)絡的某些結點和(或)連線發(fā)生故障時，通過那些包含這些結點(作為內部點)和(或)連線的路徑來傳輸數(shù)據(jù)就不可能.但仍可以通過一系列幸存的路徑傳輸數(shù)據(jù).為了使數(shù)據(jù)傳輸?shù)臅r間不至于太長，經(jīng)過的幸存路徑應該盡可能地少.對于具有給定路由選擇ρ且頂點和邊(或弧)故障F可能發(fā)生的通信網(wǎng)絡G.幸存路徑圖的直徑D(R(G，ρ)/F)是一個重要的網(wǎng)絡容錯參數(shù)，它直接反映數(shù)據(jù)傳輸延遲時間.

5、 本文主要研究化學圖論中的Randic指數(shù)和廣義Randic指數(shù)以及網(wǎng)絡中的容錯路由選擇問題.全文共分為五章. 第一章除了介紹一些圖論術語外，還介紹了我們所研究的問題的背景以及一些已知結果. 第二章討論樹的廣義Randic指數(shù)wα的下界問題.設Jn.m為所有含有n個頂點且最大匹配的基數(shù)為m的樹所成之集.記T0n,m為通過在星圖Sn-m+1的m-1個非中心點的每一個點上都粘貼一條懸掛邊后生成的階為n的圖.在這一章里，我們首

6、先證明：對于-1/2≤α＜0和Jn，m中的所有樹，T0n,m取得最小廣義Randic指數(shù)wα.同時，對于α＞0和2m≤n≤3m+1我們也得到Jn,m中所有樹的廣義Randic指數(shù)wα的下界以及達到極值的圖或圖類.本章的主要結果已發(fā)表在MATCHCommun.Math.Comput.Chem.54(2)(2005). 第三章討論單圈圖的廣義Randic指數(shù)wα的下界問題.設Unk是一個由一個長為n-k的圈粘貼k條懸掛邊到該圈上同一

7、個頂點后所得到的單圈圖.在3.1節(jié)里，我們證明：對于所有階為n且具有k個懸掛點的連通單圈圖，Unk取得最小Randic指數(shù).此結果已發(fā)表在MATCHCommun.Math.Comput.Chem.55(2)(2006).在3.2節(jié)里，我們首先給出一個共軛(即具有完美匹配)單圈圖的Randic指數(shù)的緊的下界.緊接著，我們又給出了階為n及且最大匹配的基數(shù)為m的單圈圖的Randic指數(shù)的緊的下界.此小節(jié)的結果將在JournalofMathem

8、aticalChemistry上發(fā)表.在3.3節(jié)里，我們分別就-1≤α＜0和α＞0給出單圈圖的廣義Randic指數(shù)wα的下界以及達到極值的圖或圖類. 第四章討論網(wǎng)絡中的容錯路由選擇問題.考慮笛卡爾乘積圖，證明：對于任意最小路由選擇ρ，若G和F滿足某些給定的條件，則有D(R(G1×G2×…×Gn，ρ)/F)≤3.此結果推廣了以前的一些結果.本章結果已投到DiscreteOptimization. 第五章對本文的工作進行了總