圖的多項(xiàng)式唯一性.pdf

1、多年來，圖多項(xiàng)式一直是一個(gè)活躍的研究課題，它在圖論與傳統(tǒng)代數(shù)之間架起了橋梁。因?yàn)閳D多項(xiàng)式的系數(shù)包含了豐富的組合信息，所以圖多項(xiàng)式的研究為我們了解圖的復(fù)雜結(jié)構(gòu)與參數(shù)提供了新的途徑。一個(gè)很自然的問題就是什么類型的圖能被它們的多項(xiàng)式唯一確定?特別地，什么類型的圖，它的結(jié)構(gòu)可以被一個(gè)圖多項(xiàng)式完全刻畫?換句話來說，我們是否可以找到一類圖使得他們可以被一個(gè)給定的多項(xiàng)式所確定?本文主要研究這些問題。
　　 圖論中有三個(gè)重要的多項(xiàng)式：色多項(xiàng)式、

2、Tutte多項(xiàng)式以及流多項(xiàng)式。這三個(gè)多項(xiàng)式有很密切的關(guān)系，其中色多項(xiàng)式與流多項(xiàng)式在某種意義上具有“對偶性”，并且它們都是Tutte多項(xiàng)式的特殊形式。色多項(xiàng)式以及能夠由色多項(xiàng)式唯一確定的圖等問題已得到深入研究，近些年，更多研究關(guān)注于Tutte多項(xiàng)式以及能夠由Tutte多項(xiàng)式唯一決定的圖。然而，關(guān)于流多項(xiàng)式，這方面的成果還屈指可數(shù)。另外，關(guān)于能被色多項(xiàng)式與流多項(xiàng)式所共同確定的圖方面的研究還是空白。本論文首次對這些問題進(jìn)行了研究。
　　

3、 論文結(jié)果包括兩個(gè)方面的內(nèi)容。第一部分主要是對流多項(xiàng)式的研究以及能被色多項(xiàng)式與流多項(xiàng)式共同確定的圖的研究；第二部分主要涉及能被Tutte多項(xiàng)式所唯一確定的圖的研究。
　　 論文的第一部分包括第二章和第三章。在第二章中，我們主要關(guān)注圖的流多項(xiàng)式。我們研究了流多項(xiàng)式的系數(shù)，并且證明：若兩個(gè)連通的對偶簡單圖有相同的流多項(xiàng)式，那么他們有相同的點(diǎn)數(shù)、邊數(shù)、邊連通度以及相同數(shù)目的最小邊割。利用這些信息，我們得出了廣義θ－圖的對偶圖、5個(gè)頂

4、點(diǎn)的完全圖K5以及六個(gè)頂點(diǎn)的完全二部圖K3，3是可以被它們的流多項(xiàng)式所唯一確定的。
　　 在第三章中，我們綜合運(yùn)用包含在色多項(xiàng)式與流多項(xiàng)式中的信息，證明了梯子、Mobius梯子以及圈平方圖可以被它的色多項(xiàng)式和流多項(xiàng)式所共同決定。而這幾類圖，de Mier和Noy曾證明它們是能被Tutte多項(xiàng)式所唯一確定的，這個(gè)結(jié)果可以看作是我們結(jié)論的推論。
　　 第二部分即第四章。在這一章中，我們研究了兩類圖：第一類圖我們稱作是“曲輪”