【摘要】：圖論中關(guān)于圖的生成樹數(shù)目的研究有很長的歷史.它在眾多領(lǐng)域,例如,網(wǎng)絡(luò)的可靠性分析,物理學(xué)上電路的設(shè)計等有廣泛的實際應(yīng)用[6,10,14].因此,研究圖的生成樹數(shù)目及其漸近性質(zhì)有重要的理論和實際意義.近年來無向循環(huán)圖倍受關(guān)注[2,8,13,27,28],本文致力于研究這類圖的生成樹數(shù)目及其漸近性質(zhì).針對一類特殊的循環(huán)圖,本文主要討論它的生成樹數(shù)目與其參數(shù)之間的關(guān)系式,并深入探討了它的生成樹數(shù)目的整體性質(zhì).首先,本文推導(dǎo)了上述循環(huán)圖的生成樹數(shù)目簡單精確的計算公式,實現(xiàn)了由圖的一些簡單參數(shù)便可以直接求得其生成樹數(shù)目,改進了計算循環(huán)圖的生成樹數(shù)目的方法.其次,分析了生成樹數(shù)目的漸近性質(zhì),給出了生成樹數(shù)目的漸近值的計算公式,其中為整數(shù),,表示最小公倍數(shù).這一漸近值表示生成樹數(shù)目的平均增長率[13].由此可以精確計算出這類循環(huán)圖的生成樹數(shù)目的平均增長率,克服了之前公式不易直接計算得到精確值的缺點,在很大程度上簡化了計算,便于實際的應(yīng)用.最后,討論了生成樹數(shù)目的漸近值的最值問題,證明了此漸近值具有單調(diào)遞增性質(zhì),進一步刻畫了該類循環(huán)圖的生成樹數(shù)目平均增長率的性質(zhì),具有一定的理論和實際應(yīng)用價值.
[Abstract]:The research on the number of spanning trees in graph theory has a long history. It has a wide range of practical applications in many fields, such as network reliability analysis, physics circuit design and so on. Therefore, it is of great theoretical and practical significance to study the number of spanning trees and their asymptotic properties of graphs. In recent years, undirected cyclic graphs have attracted more and more attention. In this paper, the number of spanning trees and their asymptotic properties of undirected cyclic graphs are studied. For a special cyclic graph, this paper mainly discusses the relationship between the number of spanning trees and its parameters, and discusses the global properties of the number of spanning trees. First of all, this paper deduces a simple and accurate formula for calculating the number of spanning trees of the above cyclic graphs. It is realized that the number of spanning trees can be directly obtained from some simple parameters of a graph, and the method of calculating the number of spanning trees of a cyclic graph is improved. Secondly, the asymptotic properties of the number of spanning trees are analyzed, and the formula for calculating the asymptotic value of the number of spanning trees is given, in which the number of spanning trees is an integer, representing the minimum common multiple. This asymptotic value represents the average growth rate of the number of spanning trees [13]. Thus, the average growth rate of the number of spanning trees of this kind of cyclic graphs can be calculated accurately, which overcomes the shortcoming that the previous formulas are not easy to directly calculate the exact values, and simplifies the calculation to a great extent, which is convenient for practical application. Finally, the problem of the asymptotic value of the number of spanning trees is discussed, and the monotone increasing property of the asymptotic value is proved. The properties of the average growth rate of the number of spanning trees of this kind of cyclic graphs are further characterized. It has certain theoretical and practical application value.
【學(xué)位授予單位】：深圳大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 李成軍;關(guān)于生成樹數(shù)目的公式[J];數(shù)學(xué)的實踐與認識;1993年04期

2 安建業(yè);于義良;朱建華;;通訊網(wǎng)絡(luò)中極小費用生成樹的一種算法[J];數(shù)學(xué)的實踐與認識;2007年17期

3 蔣強榮;;基于生成樹的回路核[J];鄭州大學(xué)學(xué)報(理學(xué)版);2010年03期

4 李增業(yè);;無向圖的第二大生成樹的算法[J];青海師專學(xué)報;1987年01期

5 塔力甫,尼牙孜,帕爾旦,永學(xué)榮;三種特殊的雙固定步網(wǎng)絡(luò)環(huán)的生成樹的數(shù)目(英文)[J];新疆大學(xué)學(xué)報(自然科學(xué)版);1997年02期

6 李卓群;對生成樹協(xié)議的研究[J];科技廣場;2004年11期

7 呂大梅,呂嘉鈞;樹擴圖的生成樹數(shù)[J];遼寧大學(xué)學(xué)報(自然科學(xué)版);2005年04期

8 劉玉梅;李英;;一類簡單圖的生成樹數(shù)[J];南通大學(xué)學(xué)報(自然科學(xué)版);2006年02期

9 呂大梅;呂嘉鈞;;樹擴圖生成樹數(shù)的界[J];遼寧大學(xué)學(xué)報(自然科學(xué)版);2006年04期

10 嚴冬梅;蔣沈慶;;某些偽類環(huán)圖的生成樹數(shù)[J];遼寧大學(xué)學(xué)報(自然科學(xué)版);2007年03期

相關(guān)會議論文 前4條

1 曾安;胡延慶;狄增如;;同步能力與收斂時間最優(yōu)的生成樹[A];第五屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文（摘要）匯集[C];2009年

2 劉鵬;郭莉;;生成樹協(xié)議的研究與仿真實現(xiàn)[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會——通信與信息技術(shù)會議論文集（下）[C];2006年

3 李靜力;向永紅;陳蔓莉;周永恒;;組合星圖的最優(yōu)生成樹[A];2006年全國開放式分布與并行計算學(xué)術(shù)會議論文集（一）[C];2006年

4 董志遠;張品;陳磊;;一種基于兩測度的無線鏈路重要性評價方法[A];浙江省電子學(xué)會2011學(xué)術(shù)年會論文集[C];2011年

相關(guān)重要報紙文章 前10條

1 清水;802.1s解決架構(gòu)問題[N];中國計算機報;2003年

2 清水;無線標(biāo)準(zhǔn)還有問題[N];中國計算機報;2003年

3 ;生成樹協(xié)議走向完善[N];網(wǎng)絡(luò)世界;2003年

4 ;802.1S完善網(wǎng)絡(luò)架構(gòu)[N];網(wǎng)絡(luò)世界;2003年

5 ;手挽手 密無間[N];網(wǎng)絡(luò)世界;2004年

6 ;3Com SuperStack 3 Switch 4200自動配置堆疊[N];中國計算機報;2002年

7 楊阿昭;802.1w 802.1s 恢復(fù)網(wǎng)絡(luò)故障[N];中國計算機報;2003年

8 朱新亞;RSTP瞬間恢復(fù)連接[N];中國計算機報;2003年

9 徐炯;邊緣網(wǎng)絡(luò)日趨完善[N];中國計算機報;2004年

10 ;Foundry EdgeIron 4802CF交換機[N];中國計算機報;2004年

相關(guān)博士學(xué)位論文 前1條

1 程寶雷;BC網(wǎng)絡(luò)上獨立生成樹構(gòu)造研究[D];蘇州大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 程小倩;特殊圖的生成樹的生成與計數(shù)[D];寧夏大學(xué);2014年

2 王萬禹;生成樹及限制性禁排置換[D];新疆大學(xué);2012年

3 白立乾;生成樹中的若干極值問題[D];福州大學(xué);2010年

4 黃志輝;快速生成樹無窮計數(shù)問題的研究與改進[D];華南理工大學(xué);2011年

5 孫文靜;含某些指定邊的生成樹的生成與計數(shù)[D];寧夏大學(xué);2014年

6 漆帥;基于LINUX的MSTP設(shè)計與實現(xiàn)[D];電子科技大學(xué);2012年

7 張勁松;以太網(wǎng)交換機快速生成樹協(xié)議的研究與實現(xiàn)[D];西南交通大學(xué);2005年

8 李峰;若干圖的生成樹數(shù)目和網(wǎng)絡(luò)可靠性比較[D];青海師范大學(xué);2009年

9 李敏;一類無向圖的生成樹數(shù)目及其漸近性分析[D];深圳大學(xué);2015年

10 徐蓓;基于Linux多實例生成樹協(xié)議的研究與實現(xiàn)[D];武漢郵電科學(xué)研究院;2012年

，

本文編號：2322373