塔特-格羅騰迪克不變數(Tutte-Grothendieck invariant)是一種度量，指擬陣M上的且滿足如下條件的不變數f：1.當擬陣M1，M2同構時，f(M1)=f(M2).2.若M為M1，M2的直接和，即M=M1⊕M2，則f(M)=f(M1)f(M2).3.當M的元素e不是自環，或單點割集時，f(M)=f(M-e)+f(M/e)，這裡M-e和M\e分別為M關於e的刪除和收縮。例如，擬陣M的秩母函式為此類不變數：R(M;u，v)=∑X⊆Eur(M)-r(X)v|X|-r(X)。
基本介紹
- 中文名：塔特-格羅騰迪克不變數
- 外文名：Tutte-Grothendieck invariant
- 所屬學科：數學
- 所屬問題：離散數學（組合序）
- 簡稱：TG不變數
基本介紹,TG不變數舉例,相關結論,
基本介紹
一個擬陣的不變數是一個從全體擬陣的集合到某個交換環的一個映射f，使得若
，總有f(M)=f(N)。若擬陣不變數f滿足下列兩個條件：
(TG1)對每個擬陣M和每個M的非環，非余環元e∈E(M)，都有f(M)=f(M-e)+f(M/e)，並且
(TG2)對兩個擬陣M1和M2的直和，都有f(M1⊕M2)=f(M1)f(M2)，
則f稱為一個塔特-格羅騰迪克不變數，簡稱TG不變量(Tutte-Grothendieck invariant)。
TG不變數舉例
下面是幾個TG不變數的例子。
(i)b(M)=
(擬陣M的基的個數)。
(ii)i(M)=
(擬陣M的獨立集的個數)
(iii)c(M)=
(擬陣M的極小圈的個數)。
相關結論
對於TG不變數，Brylawski證明了一個非常重要的結論。
定理1 (Brylawski 1972)設f是TG不變數，則下列命題成立：
(i)f由f(U0,1)和f(U1,1)惟一地確定。
(ii)存在一個二元多項式T(M；x，y)，使得若f(U1,1)=x，f(U0,1)=y，就有f(M)=T(M；x，y)。
證明梗概 若f是TG不變數，則由於反覆套用(TG1)和(TG2)， f的值就完全由f=f(U1,1)和y=f(U0,1)惟一確定。把這個過程倒推回去，就得出了f是x和y的一個多項式的結論。
用類似的證明，可把定理1進一步推廣為下面的定理2。
定理2 (Oxley和Welsh 1979)設a，b為非零實數， f是擬陣不變數，滿足
(TG2)和
(TG1') 對每個非環元和非余環元e∈E(M)，f(M)=af(M-e)+bf(M/e)。若f(U1,1)=x，f(U0,1)=y，則
定理1中所確定的多項式T(M；x，y)稱為Tutte多項式(Tutte-Polynomial)。下面是幾個例子。
(i)T(M；x，y)=T(M*；y，x)。
(ii)設Mi=M(Gi)是圖1所示圖Gi(1≤i≤2)的圈擬陣，則
(iii)(Brylawski 1972)存在不同構的擬陣M1和M2滿足T(M1；x，y)=T(M2；x，y)。
令E={1，2，3，…，7}， M1為一個E上的秩3擬陣，滿足
(M1)={1，2，3，4}，{1，5，6，7}，{2，6，7}，{3，6，7}，{4，6，7}}； M2是E上可圖擬陣，滿足M2-7
M(K4)而{6，7}∈
(M1)∩(M2)(見圖2)。
套用(TG1)和(TG2)，可得
T(M1；x，y)=T(M2；x，y)
