圖論中,圖的獨(dú)立數(shù)為圖論中重要的圖參數(shù)。獨(dú)立數(shù)研究在預(yù)測(cè)新化合物、合成新藥品方面有很重要的應(yīng)用。本文主要研究了兩種特殊圖類(lèi)的獨(dú)立數(shù)問(wèn)題,分別為梯形圖和凸多面體圖。其中在梯形中我們主要研究了廣義梯形圖,Mobius梯形圖和循環(huán)梯形圖。對(duì)于凸多面體圖,我們主要研究了凸多面體圖類(lèi)An,Qn,Rn。在本文中,我們還給出了求解圖類(lèi)獨(dú)立數(shù)問(wèn)題的一般算法。對(duì)于梯形圖,得到廣義梯形圖,Mobius梯形圖和循環(huán)梯形圖的獨(dú)立數(shù)的精確值,并得到了三種圖形獨(dú)立集的總和NI的精確計(jì)算公式,并運(yùn)用轉(zhuǎn)換矩陣的思想設(shè)置程序驗(yàn)證結(jié)果。對(duì)于凸多面體圖,我們主要研究了三種凸多面體圖類(lèi),分別為An,Rn和Qn。我們求出來(lái)三種圖類(lèi)的獨(dú)立數(shù),并且求出凸多面體圖類(lèi)An的獨(dú)立集總和NI的精確計(jì)算公式。因?yàn)橥苟嗝骟w圖類(lèi)Rn和Qn結(jié)構(gòu)較為復(fù)雜和一般化,我們很難求出NI的精確計(jì)算公式,所以我們給出它們的上界或者下界。對(duì)于任意圖,我們給出了一般算法�？梢杂�(jì)算任意圖的NI問(wèn)題。利用二部圖和左部圖對(duì)其進(jìn)行驗(yàn)證。選出兩個(gè)特殊圖,如:K5,4,3,2和K5,4,3,2,4。得到NI（K5,4,3,2）=319,NI（K5,4,3,2,4）=757。... 

【文章來(lái)源】：中國(guó)地質(zhì)大學(xué)(北京)北京市 211工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：70 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

七橋問(wèn)題

印度數(shù)學(xué)中的 Virahanka 數(shù)字。（[16][17][18]）LiberAbaci 中描述的順序開(kāi)始1 = 1。定義 1.8.（盧卡斯數(shù)）（Startek，2009）設(shè)nL 為第 n 個(gè)盧卡斯數(shù)，則有0L =2，1且1 2= +n n nL L L ( n ≥ 2)，盧卡斯數(shù)列通項(xiàng)公式如下：1 5 1 5+2 2n nnL + = ( n ≥ 2). （1-5）定義 1.9.（k（邊）連通圖）（Bondy，1984）若 κ ( G )≥ k( κ′ ( G )≥ k)，則稱(chēng)為 k（邊）連通的。所有非平凡連通圖都是 1 連通的。

圖 1-3 （a）一個(gè)連通圖 （b）一個(gè)具有兩個(gè)分支的不連通圖定義 1.10.大多數(shù)（但不是全部）圖表有許多可視化的表示形式，通常稱(chēng)為嵌入。為了說(shuō)明上述定義，我們使用下面的圖表：G = {{ A, B , C , D , E } , {{ A, B} , { B , C } , {C , D} , {C , E } , { D , E } , { D ,A}}}.圖G 的邊集 E ( G )為 {{ A, B} , { B , C } , {C , D} , {C , E } , { D , E } , { D ,A} }。圖G 的頂點(diǎn)集 V ( G )為{ A, B , C , D ,E }。 V ( G )=5， E ( G )=6。如圖 1 所示，為圖 G 的兩種可能的嵌入：

【參考文獻(xiàn)】：
期刊論文
[1]圖論中數(shù)學(xué)歸納法的應(yīng)用[J]. 楊迪.  技術(shù)與市場(chǎng). 2016(01)
[2]關(guān)于獨(dú)立數(shù)問(wèn)題的一些結(jié)果[J]. 董茜.  四川兵工學(xué)報(bào). 2010(01)
[3]反證法及其在圖論中的應(yīng)用[J]. 達(dá)瓦,邊巴扎西.  中國(guó)電力教育. 2007(S4)
[4]合成圖的獨(dú)立數(shù)與控制數(shù)[J]. 李煒.  黃岡師專(zhuān)學(xué)報(bào). 1997(01)

碩士論文
[1]圖論的歷史發(fā)展研究[D]. 王麗麗.山東大學(xué) 2012
[2]圖的獨(dú)立數(shù)、連通度與Hamilton連通性[D]. 張秀玲.華中師范大學(xué) 2008
[3]樹(shù)的Merrifield-Simmons指數(shù)與獨(dú)立多項(xiàng)式[D]. 吳繼春.湖南師范大學(xué) 2008



本文編號(hào)：3286665