【摘要】：近年來,圖論作為組合數(shù)學(xué)的一個(gè)重要分支,與量子場(chǎng)論、組合優(yōu)化、運(yùn)籌學(xué)、物理通訊、計(jì)算機(jī)科學(xué),統(tǒng)計(jì)物理等領(lǐng)域的聯(lián)系越來越密切。而圖論中一個(gè)重要問題——關(guān)于生成樹的研究一直吸引著人們的關(guān)注,其中關(guān)于生成樹的計(jì)數(shù)問題的研究,也是一個(gè)重要的方向。雖然也出現(xiàn)了很多的算法去計(jì)算生成樹,這些算法大多是基于分析方法的,如Greedy算法、Fleury算法。矩陣樹定理則用代數(shù)方法解答了圖的生成樹個(gè)數(shù)的計(jì)算問題。本文在此基礎(chǔ)上,進(jìn)一步考慮推廣形式下的矩陣樹定理及某些相應(yīng)的性質(zhì)。在關(guān)于圖的生成樹問題的研究中,把生成樹每條邊賦予不同的變量,把同一生成樹上的這些變量相乘,再把所有的這種生成樹單項(xiàng)式相加,得到圖的Kirchhoff多項(xiàng)式,又稱圖的生成樹多項(xiàng)式。當(dāng)把每個(gè)變量賦予數(shù)值1時(shí),則可以得到關(guān)于生成樹個(gè)數(shù)的矩陣樹定理。關(guān)于圖的Kirchhoff多項(xiàng)式,一直是圖論中關(guān)于生成樹的重要課題,它的結(jié)構(gòu)是依據(jù)圖的生成樹定義而來,因?yàn)閳D的類型不同,所以可以得到很多種不同類型的生成樹多項(xiàng)式,如果把生成樹多項(xiàng)式中的變量定義在有限域上,并考慮它的零點(diǎn)個(gè)數(shù),則便是Kontsevich猜想所考慮的一個(gè)問題。而對(duì)偶Kirchhoff多項(xiàng)式則與特殊情形下的Feynman積分相關(guān)的某些不變量的問題相關(guān)。在本文中,我們計(jì)算了某些特殊圖的Kirchhoff多項(xiàng)式,并得到了平面圖的Kirchhoff多項(xiàng)式與其對(duì)偶圖的對(duì)偶Kirchhoff多項(xiàng)式之間的關(guān)系。給出了關(guān)于圖的Kirchhoff多項(xiàng)式可約的充要條件,并由此得到了兩個(gè)圖的Kirchhoff多項(xiàng)式互質(zhì)的充要條件。證明了Aztec鉆石圖的兩部分子圖的Kirchhoff多項(xiàng)式之間并不存在整除關(guān)系。給出了Kirchhoff多項(xiàng)式在某種圖運(yùn)算下的運(yùn)算,并計(jì)算了某些特殊圖的Kirchhoff多項(xiàng)式在有限域上的零點(diǎn)個(gè)數(shù),及在概率條件下的關(guān)于圖的生成函數(shù)。
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 高文宇;;最多葉子生成樹問題的核化算法[J];計(jì)算機(jī)學(xué)報(bào);2010年12期

2 趙星明;王萱;;環(huán)狀給水管網(wǎng)自動(dòng)生成樹的研究[J];中國農(nóng)村水利水電;2018年06期

3 黃河;劉海;;關(guān)于網(wǎng)絡(luò)圖的MCST問題探討[J];交通與計(jì)算機(jī);1990年02期

4 吳龍樹;王勤;;基于最小代價(jià)和生成樹的算法研究[J];微計(jì)算機(jī)信息;2010年12期

5 夏小云;郭肇祿;楊書新;王吉源;;(μ+λ)EA算法關(guān)于最多葉子生成樹問題的近似性能[J];江西理工大學(xué)學(xué)報(bào);2016年03期

6 姚國輝;朱大銘;馬紹漢;;有向無環(huán)圖最小度生成樹問題的一種近似算法[J];計(jì)算機(jī)研究與發(fā)展;2009年06期

7 高靜;李實(shí)秋;陳云;;用母函數(shù)求解圖的生成樹問題[J];重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年S1期

8 趙玲;張建科;;基于蟻群系統(tǒng)的雙目標(biāo)最小生成樹算法[J];西安郵電學(xué)院學(xué)報(bào);2008年05期

9 崔建群;陳愛玲;夏振廠;吳黎兵;;一種高穩(wěn)定性低延遲的應(yīng)用層組播生成樹算法[J];計(jì)算機(jī)科學(xué);2016年06期

10 高文宇;;有向圖最多葉子生成樹問題研究[J];計(jì)算機(jī)應(yīng)用;2010年06期

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

1 李幸福;最大內(nèi)部點(diǎn)生成樹問題的算法及復(fù)雜性[D];山東大學(xué);2015年

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

1 董陽;圖的生成樹多項(xiàng)式的計(jì)算及性質(zhì)研究[D];哈爾濱工業(yè)大學(xué);2018年

2 徐憶晨;最小標(biāo)記生成樹問題的研究與拓展[D];復(fù)旦大學(xué);2009年

3 鐘玉文;求解兩類圖論問題的P系統(tǒng)研究[D];重慶大學(xué);2016年

4 陳智豪;遺傳算法在最小steiner生成樹問題中的研究和應(yīng)用[D];安徽工業(yè)大學(xué);2012年

，

本文編號(hào)：2699229