【摘要】：圖論中關(guān)于圖的生成樹數(shù)目的研究有很長(zhǎng)的歷史.它在眾多領(lǐng)域,例如,網(wǎng)絡(luò)的可靠性分析,物理學(xué)上電路的設(shè)計(jì)等有廣泛的實(shí)際應(yīng)用[6,10,14].因此,研究圖的生成樹數(shù)目及其漸近性質(zhì)有重要的理論和實(shí)際意義.近年來無向循環(huán)圖倍受關(guān)注[2,8,13,27,28],本文致力于研究這類圖的生成樹數(shù)目及其漸近性質(zhì).針對(duì)一類特殊的循環(huán)圖,本文主要討論它的生成樹數(shù)目與其參數(shù)之間的關(guān)系式,并深入探討了它的生成樹數(shù)目的整體性質(zhì).首先,本文推導(dǎo)了上述循環(huán)圖的生成樹數(shù)目簡(jiǎn)單精確的計(jì)算公式,實(shí)現(xiàn)了由圖的一些簡(jiǎn)單參數(shù)便可以直接求得其生成樹數(shù)目,改進(jìn)了計(jì)算循環(huán)圖的生成樹數(shù)目的方法.其次,分析了生成樹數(shù)目的漸近性質(zhì),給出了生成樹數(shù)目的漸近值的計(jì)算公式,其中為整數(shù),,表示最小公倍數(shù).這一漸近值表示生成樹數(shù)目的平均增長(zhǎng)率[13].由此可以精確計(jì)算出這類循環(huán)圖的生成樹數(shù)目的平均增長(zhǎng)率,克服了之前公式不易直接計(jì)算得到精確值的缺點(diǎn),在很大程度上簡(jiǎn)化了計(jì)算,便于實(shí)際的應(yīng)用.最后,討論了生成樹數(shù)目的漸近值的最值問題,證明了此漸近值具有單調(diào)遞增性質(zhì),進(jìn)一步刻畫了該類循環(huán)圖的生成樹數(shù)目平均增長(zhǎng)率的性質(zhì),具有一定的理論和實(shí)際應(yīng)用價(jià)值.
[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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 清水;802.1s解決架構(gòu)問題[N];中國(guó)計(jì)算機(jī)報(bào);2003年

2 清水;無線標(biāo)準(zhǔn)還有問題[N];中國(guó)計(jì)算機(jī)報(bào);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自動(dòng)配置堆疊[N];中國(guó)計(jì)算機(jī)報(bào);2002年

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

8 朱新亞;RSTP瞬間恢復(fù)連接[N];中國(guó)計(jì)算機(jī)報(bào);2003年

9 徐炯;邊緣網(wǎng)絡(luò)日趨完善[N];中國(guó)計(jì)算機(jī)報(bào);2004年

10 ;Foundry EdgeIron 4802CF交換機(jī)[N];中國(guó)計(jì)算機(jī)報(bào);2004年

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2322373