秩多項式

秩多項式(rank polynomial)是圖的一個組合不變數，對於圖G=(V，E)，記R(G;x，y)=Σ_S⊆E x^r(S)y^s(S)，其中，r(S)，s(S)分別為以S為邊集的G的支撐子圖的秩和上秩，稱R(G;x，y)為圖G的秩多項式。

基本介紹

• 中文名：秩多項式
• 外文名：rank polynomial
• 所屬學科：數學
• 所屬問題：圖論
• 相關概念：圈基，色多項式，點覆蓋多項式等

定義

對於圖，記

其中，分別為以S為邊集的G的支撐子圖的秩和上秩(參見“圈基”)，稱為圖G的秩多項式。

相關性質

1. 圖的秩多項式與色多項式有如下關係：

2. 對於圖，記

其中，為G的秩，同上，稱為塔特多項式或范色多項式。塔特(W.T.Tutte)於20世紀60年代發現這個多項式，並且揭示了它與圖內在結構性質的關係。瓊斯(V.F.R.Jones)於20世紀80年代發現扭結的新的拓撲不變數，人們稱之為瓊斯多項式。近來，人們發現後者實質上可以從前者的思想同樣導出它與扭結的內在結構性質的關係。

圈基

圈基(circuit basis)是圖G的循環空間的一組基，循環空間的維數稱為圈秩或簡稱上秩，記為，

其中為的連通片數。上循環空間的一組基稱為上圈基，上循環空間的維數稱為上圈秩或簡稱秩，記為。若為圖的一個支撐樹，為相應的上樹，則任何一個上樹邊與樹恰形成一個圈，稱為樹的一個基本圈。相仿地，每一個樹邊與上樹恰形成一個上圈，稱為樹T的一個基本上圈。支撐樹T的所有基本圈構成圖G的一個圈基，所有基本上圈構成圖G的一個上圈基。雙循環空間的一組基稱為雙圈基，雙循環空間的維數稱為雙圈秩，與某一雙圈基中的每一個圈恰有一條公共邊的邊集，稱為雙樹。

子圖多項式與秩多項式

子圖多項式 當G為無向圖，由G的一切連通子圖所構成時，圖G在之下的點覆蓋多項式稱為“子圖多項式”，而當單元的度量不同時，可得一些特殊的多項式。例如雙色多項式、秩多項式、色多項式等。

若令，其中為連通子圖的秩，則

就是秩多項式，其中表示由S所成的支撐子圖的秩。