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

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

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

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

4、以一類Sierpi(n)ski-型自相似圖為例探討了計算自相似圖類Tutte多項式的一般性方法.
　　在第三章，研究了Tutte多項式的若干極端項的系數(shù)，對極端項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)行了組合解釋，這里，n和m分別是所討論圖的點數(shù)和邊數(shù).
　　在第四章，先討論強(qiáng)版的Akiyama-Harary問題（即“是否存在非自補(bǔ)圖與其

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