主題
Search

Tutte 多項式

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

令 G 為一個 無向圖，並令 i 表示生成樹 T 的外部活躍邊的集合的 基數，G，j 表示 T 的內部活躍邊的集合的 基數，t_(ij) 表示 G 的生成樹的數量，其內部活躍度為 i，外部活躍度為 j。那麼 Tutte 多項式，也稱為二色多項式或 Tutte-Whitney 多項式，定義為

T(x,y)=sumt_(ij)x^iy^j
(1)

(Biggs 1993, 第 100 頁)。

一個等價的定義由下式給出

T(x,y)=sum(x-1)^(k_A-k)(y-1)^(k_A+n_A-n),
(2)

其中求和是對圖 G 的 邊集 的所有子集 A 進行的，k_A 是由 A 匯出的 n_A 個頂點的子圖的連通分量數，n 是 G 的 頂點數，k 是 G 的連通分量數。

已經考慮了 Tutte 多項式的幾種有向圖類似物，包括覆蓋多項式 (Chung and Graham 1995)、Gordon-Traldi 多項式 (Gordon and Traldi 1993) 和三變數 B-多項式 (Awan 和 Bernardi 2016; Chow 2016)。然而，除了 Gordon-Traldi 多項式 f_8 和 B-多項式外，這些都不是 Tutte 多項式的適當推廣，因為對於無向圖的特殊情況，它們與 Tutte 多項式不等價 (Awan 和 Bernardi 2016)。

Tutte 多項式可以使用 Wolfram 語言 計算，使用TuttePolynomial[g, {x, y}]。

Tutte 多項式對於不相交併集是可乘的。

對於一個具有 n 個頂點和 c 個連通分量的 無向圖，Tutte 多項式由下式給出

T(x+1,y+1)=x^(n-c)R(x^(-1),y)
(3)

其中 R(x,y) 是 秩多項式 (推廣了 Biggs 1993, 第 101 頁)。因此，Tutte 多項式是一個相當通用的雙變數圖多項式，從中可以計算出許多其他重要的一元和二元多項式。

對於不一定連通的圖，Tutte 多項式 T(x,y) 與 色多項式 pi(x)，流多項式 C^*(u)，秩多項式 R(x,y) 和 可靠性多項式 C(p) 的關係為

pi(x)=(-1)^(n-c)x^cT(1-x,0)
(4)
C^*(u)=(-1)^(m-n+c)T(0,1-u)
(5)
R(x,y)=x^(n-c)T(x^(-1)+1,y+1)
(6)
C(p)=(1-p)^(n-c)p^(m-n+c)T(1,p^(-1)),
(7)

其中 n 是圖中的頂點數，m 是邊數，c 是連通分量數。

圖 G 的 對偶圖 G^* 的 Tutte 多項式由下式給出

T_(G^*)(x,y)=T_G(y,x),
(8)

即，透過交換原始圖的 Tutte 多項式的變數。這個恆等式的特殊情況將 平面圖 G 的 流多項式 C_G^*(u) 與其 對偶圖 G^* 的 色多項式 聯絡起來，透過

C_G^*(u)=u^(-1)pi_(G^*)(u).
(9)

連通圖 G 的 Tutte 多項式也完全由以下兩個性質定義 (Biggs 1993, 第 103 頁)

1. 如果 e 是圖 G 的一條既不是環也不是橋的邊，那麼 T_G(x,y)=T(G^((e));x,y)+T(G_((e));x,y)。

2. 如果 Lambda_(ij) 是由一個具有 i 條邊的樹透過新增 j 個環形成的，那麼 T(Lambda_(ij);x,y)=x^iy^j

下表總結了一些特殊圖類的閉合形式，其中 s=sqrt((1+x+x^2+y)^2-4x^2y) 和 t=sqrt((x+y+1)^2-4xy)。Biggs 等人 (1972) 和 Brennan 等人 (2013) 考慮了 網狀圖 的 Tutte 多項式。

圖T(x,y)
書圖 S_(n+1) square P_2((1+x+x^2)^n[x(y-1)-y]+y(x+x^2+y)^n)/(y-1)
蜈蚣圖x^(2n-1)
圈圖 C_n(x^n-x)/(x-1)+y
空圖 K^__n1
森林x^(|E|)
齒輪圖2^(-n)(-2^n-2^nx-2^ny+2^nxy+(1+x+x^2+y-s)^n+(1+x+x^2+y+s)^n
舵圖x^n{-1-x-y+xy+2^(-n)[(1-t+x+y)^n+(1+t+x+y)^n]}
梯形圖((s(x-1)+x^3-xy+y+1)(s+x^2+x+y+1)^n-(-sx+s+x^3-xy+y+1)(-s+x^2+x+y+1)^n)/(2^(n+1)sx^2)
梯子橫檔圖x^n
平底鍋圖(x[x^n+x(y-1)-y])/(x-1)
路徑圖 P_nx^(n-1)
星圖 S_nx^(n-1)
日射圖 C_n circledot K_1(x^(2n)+x^n(x(-1+y)-y))/(x-1)
輪圖 W_nxy-x-y-1+2^(1-n)[(x+y+1+t)^(n-1)+(x+y+1-t)^(n-1)]

下表總結了一些簡單圖類的 Tutte 多項式的遞推關係。

圖階遞推關係
反稜柱圖6
書圖 S_(n+1)P_22p_n=(2x^2+2x+y+1)p_(n-1)-(x^2+x+1)(x^2+x+y)p_(n-2)
蜈蚣圖1p_n=x^2p_(n-1)
圈圖 C_n2p_n=(x+1)p_(n-1)-xp_(n-2)
齒輪圖3p_n=(x^2+x+y+2)p_(n-1)+(-x^2y-x^2-x-y-1)p_(n-2)+x^2yp_(n-3)
舵圖3p_n=x(x+y-2)p_(n-1)-x^2(x+1)(y+1)p_(n-2)+x^4p_(n-3)
梯形圖2p_n=(x^2+x+y+1)p_(n-1)-x^2yp_(n-2)
梯子橫檔圖1p_n=xp_(n-1)
莫比烏斯梯子 M_n6
平底鍋圖2p_n=(x+1)p_(n-1)-xp_(n-2)
路徑圖1p_n=xp_(n-1)
稜柱圖 Y_n6
星圖 S_n1p_n=xp_(n-1)
日射圖 C_n circledot K_12p_n=x(x+1)p_(n-1)-x^3p_(n-2)
網狀圖6
輪圖 W_n3p_n=(x+y+2)p_(n-1)-(x+1)(y+1)p_(n-2)+xyp_(n-3)

Tutte (1954, 1967) 發現了 完全圖 K_n 的 Tutte 多項式 T_(K_n)(x,y) 的方程。特別是，T_(K_n)(x,y) 具有 指數生成函式

sum_(n=1)^inftyT_(K_n)(x,y)(u^n)/(n!)=1/(x-1){[sum_(n=0)^inftyy^((n; 2))(y-1)^(-n)(u^n)/(n!)]^((x-1)(y-1))-1},
(10)

(Gessel 1995, Gessel 和 Sagan 1996)。這可以用餘邊界多項式更簡單地表示

chi^__G(q,t)=(t-1)^(n_G-c_G)T_G((q+t-1)/(t-1),t),
(11)

其中 c_G 是連通分量計數，n_G 是圖 G 的 頂點數 (Martin 和 Reiner 2005)。在這種形式下，K_n 的指數生成函式由下式給出

1+qsum_(n=1)^inftychi^__(K_n)(q,t)(x^n)/(n!)=(sum_(n=0)^inftyt^((n; 2))(x^n)/(n!))^q,
(12)

可以使用上述關係和替換 q->(x-1)(y-1) 和 t->y 將其轉換為相應的 Tutte 多項式。Pak 以以下遞推形式重新發現了該公式

F_n(x,y)=sum_(k=1)^n(n-1; k-1)(x+y+y^2+...+y^(k-1))F_(k-1)(1,y)F_(n-k)(x,y),
(13)

其中 F_n(x,y)=T_(K_(n+1))(x,y)。

完全二部圖 K_(m,n) 的 Tutte 多項式的公式由 Martin 和 Reiner (2005) 以餘邊界多項式的雙變數 指數生成函式 的形式給出

1+qsum_(m=0)^inftysum_(n=0)^inftychi^__(K_(m,n))(q,t)(x^my^m)/(m!n!)=(sum_(k=0)^inftysum_(l=0)^inftyt^(kl)(x^ky^l)/(k!l!))^q
(14)

由 Martin 和 Reiner (2005)。

非同構圖不一定具有不同的 Tutte 多項式。de Mier 和 Noy (2004) 將由其 Tutte 多項式確定的圖稱為 T-唯一圖，並表明 輪圖、梯形圖、莫比烏斯梯子、完全多部圖 (除了 T_(1,p)) 和 超立方體圖 是 T-唯一圖。Kuhl (2008) 表明 廣義 Petersen 圖 GP(m,2) 及其 線圖 L(GP(m,2)) 是 T-唯一的。

n=1, 2, ... 個節點的非 Tutte 唯一簡單圖的數量分別為 0, 0, 0, 4, 15, 84, 548, 5629, ... (OEIS A243048)，而相應的 Tutte 唯一圖的數量分別為 1, 2, 4, 7, 19, 72, 496, 6717, ... (OEIS A243049)。下表總結了一些小的共-Tutte 圖。

nTutte 多項式圖
4x^2P_3 union K_1, 梯子橫檔圖 2P_2
4x^3爪圖 K_(1,3), 路徑圖 P_4
5x^2P_3 union 2K_1, 2P_2 union K_1
5x^3K_(1,3) union K_1, P_3 union P_2, P_4 union P_1
5x^4叉圖, 路徑圖 P_5, 星圖 S_5
5x(x+x^2+y)爪子圖 union K_1, C_3 union P_2
5x^2(x+x^2+y)牛圖, 板球圖, (3,2)-蝌蚪圖
5x(x+2x^2+x^3+y+2xy+y^2)飛鏢圖, 風箏圖

參見

色多項式, 流多項式, 秩多項式, Tutte 矩陣

使用 探索

參考文獻

Andrzejak, A. "Splitting Formulas for Tutte Polynomials." J. Combin. Th., Ser. B. 70, 346-366, 1997.Andrzejak, A. "An Algorithm for the Tutte Polynomials of Graphs of Bounded Treewidth." Disc. Math. 190, 39-54, 1998.Biggs, N. L. "The Tutte Polynomial." Ch. 13 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 97-105, 1993.Biggs, N. L.; Damerell, R. M.; and Sands, D. A. "Recursive Families of Graphs." J. Combin. Theory Ser. B 12, 123-131, 1972.Björklund, A.; Husfeldt, T.; Kaski, P.; and Koivisto, M. "Computing the Tutte Polynomial in Vertex-Exponential Time." In Proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 677-686, 2008.Brennan, C.; Mansour, T.; and Mphako-Banda, E. "Tutte Polynomials of Wheels Via Generating Functions." Bull. Iranian Math. Soc. 39, 881-891, 2013.Brylawski, T. and Oxley, J. "The Tutte Polynomial and Its Applications." Ch. 6 in Matroid Applications (Ed. N. White). Cambridge, England: Cambridge University Press, pp. 123-225, 1992.Chow, T Y. "Digraph Analogues of the Tutte Polynomials." Preprint chapter for The CRC Handbook on the Tutte Polynomial and Related Topics (Ed. I. Moffat and J. Ellis-Monaghan). 2016.Chung, F. R. K. and Graham, R. L. "On the Cover Polynomial of a Digraph." J. Combin. Theory, Ser. B 65, 273-290, 1995.de Mier, A. and Noy, M. "On Graphs Determined by Their Tutte Polynomial." Graphs Combin. 20, 105-119, 2004.de Mier, A. and Noy, M. "Tutte Uniqueness of Line Graphs." Disc. Math. 301, 57-65, 2005.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications I: The Tutte Polynomial." 28 Jun 2008. http://arxiv.org/abs/0803.3079.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. http://arxiv.org/abs/0806.4699.Gessel, I. M. "Enumerative Applications of a Decomposition for Graphs and Digraphs." Disc. Math. 139, 257-271, 1995.Gessel, I. M. and Sagan, B. E. "The Tutte Polynomial of a Graph, Depth-First Search, and Simplicial Complex Partitions." Electronic J. Combinatorics 3, No. 2, R9, 1-36, 1996. http://www.combinatorics.org/Volume_3/Abstracts/v3i2r9.html.Gordon, G. and Traldi, L. "Polynomials for Directed Graphs." Congr. Numer. 94, 187-201, 1993.Haggard, G.; Pearce, D. J.; and Royle, G. "Computing Tutte Polynomials" ACM Trans. Math. Software 37, Art. 24, 17 pp., 2010.Jaeger, F. "Tutte Polynomials and Link Polynomials." Proc. Amer. Math. Soc. 103, 647-665, 1988.Jaeger, F.; Vertigan, D.; and Welsh, D. "On the Computational Complexity of the Jones and Tutte Polynomials." Math. Proc. Camb. Phil. Soc. 108, 35-53, 1990.Kuhl, J. S. "The Tutte Polynomial and the Generalized Petersen Graph." Australas. J. Combin. 40, 87-97, 2008.Pak, I. "Computation of Tutte Polynomials of Complete Graphs." http://www.math.ucla.edu/~pak/papers/Pak_Computation_Tutte_polynomial_complete_graphs.pdf.Martin, J. and Reiner, V. "Cyclotomic and Simplicial Matroids." Israel J. Math. 150, 229-240, 2005.Sloane, N. J. A. Sequences A243048 and A243049 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Contribution to the Theory of Chromatic Polynomials." Canad. J. Math. 6, 80-91, 1954.Tutte, W. T. "On Dichromatic Polynomials." J. Combin. Th. 2, 301-320, 1967.

在 中被引用

Tutte 多項式

請這樣引用

Weisstein, Eric W. "Tutte 多項式。" 來自 Web 資源。 https://mathworld.tw/TuttePolynomial.html

主題分類