Tutte多项式
导说这是很著名的概念，所以在这里简单记录一下。
内容参考自《Handbook of the Tutte Polynomial and Related Topics》，并添加了一些我的理解，学艺不精请大伙多多包涵。
秩和环度
对于图$G=(V,E)$，下表给出了一些基本量：
| 符号 | 含义 | 性质 |
|---|---|---|
| $k(G)$ | 连通块数量 | |
| $v(G)$ | 图$G$的顶点数 | |
| $e(G)$ | 图$G$的边数 | |
| $r(G)$ | 秩 | $r(G):=v(G)-k(G)$ |
| $n(G)$ | 环度（nullity） | $n(G):=e(G)-r(G)=e(G)-v(G)+k(G)$ |
| $f(A),A\subseteq E$ | 用边集代替对应生成子图作为参数 | $f(A)=f(G(V,A))$ |
| $r(E)-r(A)$ | 余秩（corank） |
$r(G)$可以理解为“图的生成森林的最大边数”，相应$n(G)$就可以理解成其余的边。
为了进一步理解，下面列出了对图$G$的操作与这两个变量取值的关联：
加孤立顶点：$r(G),n(G)$都不变；
加边且不改变连通块数量：$r(G)$不变，$n(G)$增加$1$；
加边使若连通块数量减少$1$：$r(G)$增加$1$，$n(G)$不变。
Tutte多项式
定义：$T(G;x,y)=\sum_{A \subseteq E}(x-1)^{r(E)-r(A)}(y-1)^{n(A)}$，其中
这是一个整系数多项式，即$T(G;x,y)\in\mathbb Z[x,y]$。
Tutte多项式枚举了所有边集的子集。
表达式的两个指数上分别是余秩和环度。
余秩对应生成子图与原图的连通块数量的差值。
$T(G;x,y)=\sum_{A \subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{n(A)}$
Whitney秩生成函数
定义：$W(G;x,y)=T(G;x+1,y+1)$
- $W(G;x,y)=\sum_{A \subseteq E}x^{r(E)-r(A)}y^{n(A)}$
二色多项式(dichromatic polynomial)
定义：$Z(G;u,v)=\sum_{A \subseteq E(G)} u^{k(A)} v^{e(A)}$
Tutte多项式、二色多项式、Whitney秩生成函数之间的关联
$T(G;x,y)=(x-1)^{-k(G)}(y-1)^{-v(G)}Z(G;(x-1)(y-1),(y-1))$
- 重写Whitney秩生成函数可以得到$W(G;x,y)=\sum_{A \subseteq E}x^{r(E)-r(A)}y^{n(A)}=x^{-k(G)}y^{-v(G)}\sum_{A \subseteq E}x^{k(A)}y^{e(A)+k(A)}$，这个形式与二色多项式非常相似，不同点在于提出的与$A$无关的部分，以及在$x,y$的指数上同时出现的$k(A)$。
- 代入$u=xy,v=y$可以得到$Z(G;xy,y)=\sum_{A \subseteq E}x^{k(A)}y^{e(A)+k(A)}$。
- 即$W(G;x,y)=x^{-k(G)}y^{-v(G)}Z(G;xy,y)$。
- 对于Tutte多项式与二色多项式只需要联立Whitney秩生成函数的定义即可：$T(G;x,y)=(x-1)^{-k(G)}(y-1)^{-v(G)}Z(G;(x-1)(y-1),(y-1))$。