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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：2699229