本文關(guān)鍵詞：圖多項式若干問題研究

  更多相關(guān)文章： 圖多項式 Tutte多項式 子圖分支多項式 確定性復(fù)雜網(wǎng)絡(luò)模型 生成樹

【摘要】：本文主要由五章構(gòu)成。在本文的前半部分,我們主要研究了自相似復(fù)雜網(wǎng)絡(luò)模型的Tutte多項式的計算。在本文的后半部分,我們研究由子圖分支多項式確定的圖不變量,由子圖分支多項式確定的圖以及子圖分支多項式的區(qū)分度。在第一章,我們對圖多項式研究現(xiàn)狀和我們的研究動機進行了總述。在第二章,我們介紹了圖論的一些基本知識,這些知識都是敘述我們工作的必要準備。在第三章,我們主要研究Tutte多項式的計算。(1).在文獻[23]中,F. Comellas等人提出了一類自相似無聚類的小世界網(wǎng)絡(luò)模型Mn,并在文獻[24]中研究了這一類網(wǎng)絡(luò)模型的生成樹數(shù)。我們利用生成子圖分類的辦法,研究了Mn的Tutte多項式,得到了T(Mn;x,y)的一個遞歸表達式。利用這個遞歸表達式,我們解得圖Mn的流多項式,色多項式,生成樹數(shù),強連通定向數(shù),無圈定向數(shù)等圖不變量的具體表達式。(2).在文獻[82]中,章忠志等人首次將Farey圖作為復(fù)雜網(wǎng)絡(luò)模型來研究,并在文獻[83]中利用矩陣樹定理計算了Farey圖的生成樹數(shù)。我們利用Farey圖Gn自相似的結(jié)構(gòu)特點,得到了T(Gn;x,y)的一個遞歸表達式。在這個基礎(chǔ)上,我們還研究了甌的色多項式和可靠性多項式,并得到了Tutte多項式在某些特殊點(x,y)的值。(3).在文獻[81,84]中,章忠志和張靜遠等人利用不同的方法分別計算了Apollonian網(wǎng)絡(luò)的生成樹數(shù)。我們沒有直接計算Apollonian網(wǎng)絡(luò)的Tutte多項式,而是研究其對偶圖。利用Apollonian對偶圖與Hanoi圖的結(jié)構(gòu)聯(lián)系,我們得到了Apollonian對偶圖的Tutte多項式的一個遞歸表達式。(4).我們發(fā)現(xiàn),大部分確定性復(fù)雜網(wǎng)絡(luò)模型都是通過模塊組合得到的,而常見的模塊組合方法就是粘合兩個模塊之間的頂點。于是,我們研究了兩點連圖G：H的Tutte多項式。研究發(fā)現(xiàn),組合后的模塊的Tutte多項式T(G:H;x,y)能由各個子模塊的Tutte多項式表示。利用這個表示式,我們計算了擬分形無尺度網(wǎng)絡(luò)和廣義(2,2)-花圖的生成樹數(shù),還得到了鏈環(huán)的Tutte多項式的一個遞歸表達式和書圖的Tutte多項式的一個具體表達式。在第四章,我們研究子圖分支多項式Q(G;x,y),這個雙變量多項式是由Tittmann等人[75]在研究復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)時提出的。與雙變量的Tutte多項式類似,子圖分支多項式也包含了圖的很多信息,例如圖頂點數(shù),邊數(shù),連通分支數(shù)和獨立數(shù)等。我們發(fā)現(xiàn),還有其它的一些圖不變量能由子圖分支多項式確定,例如圖的頂點連通度。在一些特殊的圖類中,例如正則二部圖中,長為4的圈數(shù)等也能由子圖分支多項式確定。利用子圖分支多項式的這一性質(zhì),我們發(fā)現(xiàn)一些特殊的圖類能由子圖分支多項式確定,例如完全二部圖,輪圖,友誼圖,書圖,超方體等。最后,我們還比較了子圖分支多項式與一些其它的多項式的區(qū)分度,發(fā)現(xiàn)子圖分支多項式與其他多項式在區(qū)分度上沒有明顯的關(guān)聯(lián)。我們的這些結(jié)果,部分回答了Tittmann[75]等人提出的三個公開問題。在第五章,我們總結(jié)了本文的主要工作,提出了許多需要進一步展開研究的問題。
【關(guān)鍵詞】：圖多項式 Tutte多項式 子圖分支多項式 確定性復(fù)雜網(wǎng)絡(luò)模型 生成樹
【學(xué)位授予單位】：湖南師范大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 中文摘要3-5
• 英文摘要5-9
• 1. 緒論9-13
• 1.1 圖多項式的發(fā)展及現(xiàn)狀9-12
• 1.2 研究背景及意義12-13
• 2 預(yù)備知識13-22
• 2.1 基本概念和術(shù)語13-15
• 2.2 圖運算和一些特殊圖類15-19
• 2.3 一些圖多項式19-22
• 3. 幾類網(wǎng)絡(luò)圖的Tutte多項式22-61
• 3.1 Tutte多項式的定義及基本性質(zhì)22-25
• 3.2 一類自相似圖的Tutte多項式25-34
• 3.3 Farey圖的Tutte多項式34-41
• 3.4 Apollonian圖的Tutte多項式41-49
• 3.5 兩點連圖的Tutte多項式49-61
• 4. 子圖分支多項式61-75
• 4.1 子圖分支多項式的定義及基本性質(zhì)61-63
• 4.2 由子圖分支多項式確定的圖不變量63-67
• 4.3 由子圖分支多項式確定的圖類67-72
• 4.4 子圖分支多項式的區(qū)分度72-75
• 5. 結(jié)束語75-77
• 參考文獻77-83
• 碩博連讀期間發(fā)表的論文83-84
• 致謝84-85

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 吳廷增;扈生彪;;完全圖的兩類生成子圖是譜唯一確定的(英文)[J];華東師范大學(xué)學(xué)報(自然科學(xué)版);2012年01期

2 周懷魯;;圈——書Ramsey數(shù)[J];曲阜師范大學(xué)學(xué)報(自然科學(xué)版);1988年02期

3 韓叢英,寧偉;具有約束的極小生成子圖的一個算法[J];山東礦業(yè)學(xué)院學(xué)報(自然科學(xué)版);1999年04期

4 邱念慈;n階無向完全圖非同構(gòu)生成子圖的結(jié)構(gòu)與作法[J];揚州教育學(xué)院學(xué)報;2004年03期

5 蔡小濤;;連通的歐拉生成子圖[J];數(shù)學(xué)季刊;1990年Z1期

6 周懷魯;奇圈對輪的Ramsey數(shù)[J];數(shù)學(xué)雜志;1995年01期

7 曹細玉,毛經(jīng)中;生成子圖與圖的哈密頓性質(zhì)[J];湖北大學(xué)學(xué)報(自然科學(xué)版);1996年04期

8 李霄民;李登信;雷瀾;;一類用于尋找歐拉生成子圖邊數(shù)的收縮子圖[J];數(shù)學(xué)的實踐與認識;2010年20期

9 劉芝梅;曹炬;劉毅;;尋找2-邊連通子圖的一種近似算法[J];應(yīng)用數(shù)學(xué);2007年S1期

10 湯鴻鳴;;尋找哈密爾頓函數(shù)圖形的周期[J];福建電腦;2012年06期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 廖云華;圖多項式若干問題研究[D];湖南師范大學(xué);2015年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前6條

1 鮑旭東;圖的BB-染色[D];浙江師范大學(xué);2015年

2 周蘭;圖的BBC染色[D];浙江師范大學(xué);2010年

3 丁哲衡;幾類網(wǎng)絡(luò)優(yōu)化和改進問題的算法研究[D];中國計量學(xué)院;2013年

4 張水明;圖的BB-染色[D];浙江師范大學(xué);2011年

5 何梅芝;圖譜的一些應(yīng)用[D];湖南師范大學(xué);2006年

6 王娜;關(guān)于圖的分數(shù)因子的若干結(jié)果[D];曲阜師范大學(xué);2007年

，

本文編號：909205