Tutte多項(xiàng)式及其相關(guān)問(wèn)題的研究.pdf

1、圖的多項(xiàng)式是代數(shù)圖論的重要研究對(duì)象.圖的Tutte多項(xiàng)式（雙變量）是由W.T.Tutte于1954年提出，它滿(mǎn)足一個(gè)廣義的刪縮遞減運(yùn)算.從某種意義上說(shuō)，Tutte多項(xiàng)式滿(mǎn)足的刪縮遞減關(guān)系恰恰反映了計(jì)算機(jī)科學(xué)，物理及生物學(xué)上許多網(wǎng)絡(luò)模型的演變過(guò)程，這不僅使Tutte多項(xiàng)式與互聯(lián)網(wǎng)絡(luò)研究中的全端可靠性多項(xiàng)式，統(tǒng)計(jì)物理上Potts模型配分函數(shù)，在生物學(xué)上有應(yīng)用的紐結(jié)的Jones多項(xiàng)式等密切相關(guān)，而且促使Tutte多項(xiàng)式被廣泛研究.
　　

2、Tutte多項(xiàng)式也叫雙色多項(xiàng)式，它的系數(shù)可由原始定義來(lái)解釋:T(G;x，y)=∑i,j tijxiyj，這里，tij是圖G中內(nèi)活躍度為i且外活躍度為j的生成森林個(gè)數(shù).Tutte多項(xiàng)式蘊(yùn)含了圖的豐富的組合和拓?fù)湫畔?Tutte多項(xiàng)式的研究旨在揭示Tutte多項(xiàng)式的代數(shù)性質(zhì)與圖的拓?fù)浣Y(jié)構(gòu)之間的本質(zhì)關(guān)系.本文共分五章，主要圍繞以下問(wèn)題展開(kāi)研究:(1) Tutte多項(xiàng)式的計(jì)算問(wèn)題;(2) Tutte多項(xiàng)式的系數(shù)問(wèn)題;(3) Tutte等價(jià)，Tu

3、tte唯一圖及相關(guān)問(wèn)題;(4)(X，Y)平面上點(diǎn)的Tutte值相關(guān)問(wèn)題（包括一些有趣的組合解釋?zhuān)?具體如下:
　　在第一章，先給出與本文有關(guān)的一些概念和符號(hào)，簡(jiǎn)述了相關(guān)領(lǐng)域的研究背景和研究現(xiàn)狀，同時(shí)也給出了本文的主要研究結(jié)果.
　　在第二章，遞歸計(jì)算了理論化學(xué)中一類(lèi)渺位六角系統(tǒng)，統(tǒng)計(jì)物理中幾類(lèi)自相似遞歸構(gòu)造圖類(lèi)(the modified Koch圖，Austria圖)的Tutte多項(xiàng)式，并確定了它們的一些Tutte值.此外，

4、以一類(lèi)Sierpi(n)ski-型自相似圖為例探討了計(jì)算自相似圖類(lèi)Tutte多項(xiàng)式的一般性方法.
　　在第三章，研究了Tutte多項(xiàng)式的若干極端項(xiàng)的系數(shù)，對(duì)極端項(xiàng)ym-n+1，ym-n，ym-n-1，xym-n，xym-n-1，xn-1，xn-2，xn-3，yxn-2，yxn-3的系數(shù)進(jìn)行了組合解釋?zhuān)@里，n和m分別是所討論圖的點(diǎn)數(shù)和邊數(shù).
　　在第四章，先討論強(qiáng)版的Akiyama-Harary問(wèn)題（即“是否存在非自補(bǔ)圖與其

5、補(bǔ)圖有相同的Tutte多項(xiàng)式”），再提出用‘圖替換邊’來(lái)構(gòu)造Tutte-等價(jià)圖的新方法.最后，證明兩類(lèi)完全二部圖刪邊子圖是色唯一，改進(jìn)了已知的結(jié)果.
　　在第五章，受圖和紐結(jié)的多項(xiàng)式相關(guān)研究啟發(fā)，我們研究了圖（賦權(quán)圖）的生成樹(shù)計(jì)數(shù)問(wèn)題.基于電網(wǎng)絡(luò)理論技巧，證明了一個(gè)有關(guān)任意圖及其線(xiàn)圖的生成樹(shù)數(shù)目的關(guān)系式，并討論了相關(guān)應(yīng)用.特別地，公式簡(jiǎn)化了Dong和Yan最近證明的一個(gè)復(fù)雜的公式.最后，對(duì)Zhang和Yan證明的一個(gè)有關(guān)對(duì)稱(chēng)圖（含