主题
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 矩阵

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

Tutte 多项式

请这样引用

Weisstein, Eric W. "Tutte 多项式。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/TuttePolynomial.html

主题分类