由Matrix-Tree到多项式插值

《社会计算》大作业

生成树

生成树(spanning-tree)是图论里面一个重要的概念。

一个无向图的所有边构成的集合称为这个无向图的边集，一个构成树的边集的子集，就成为这个无向图的生成树。 如果只是要求一棵生成树或者是要求边总权值最小的生成树，有很多经典的算法，比如Prim与Kruscal算法。 然而如果要求一个无向图的生成树数量，就不是一个那么简单的任务了。

Matrix-Tree定理

以下引用自国家集训队2008论文集

Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念：

1、 G的度数矩阵D[G]是一个nn的矩阵，并且满足：当i≠j时,dij=0；当i=j时，dij等于vi的度数。 2、 G的邻接矩阵A[G]也是一个nn的矩阵， 并且满足：如果vi、vj之间有边直接相连，则aij=1，否则为0。

我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G]，则Matrix-Tree定理可以描述为：G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式，就是对于r(1≤r≤n)，将C[G]的第r行、第r列同时去掉后得到的新矩阵，用Cr[G]表示。

The Matrix Revolutions(ICPC Regionals 2014 :: Asia - Shanghai Problem A)

给定一个无向图，每条边上有黑色或者白色，求黑色边数不超过K的生成树数量对10^9+7取模。 点数不超过50。

Matrix-Tree定理可以求出一个无向图的生成树数量，但这个问题似乎不能直接用Matrix-Tree定理解决，我们换个思路，如果把度数矩阵与邻接矩阵中的1换成代表颜色的字母代数$x$和$y$。这样得到的行列式就有$x$和$y$这两个未知元，此时行列式得到的值就是一个关于$x$与$y$的多项式。而且可以发现${x}^{a}{y}^{b}$的系数就是含有$a$条$x$边以及$b$条$y$边的生成树数量。

由于一个生成树边的数量等于点的数量-1，意味着得到的多项式满足$a+b+1=$点数。也就是说可以让$y=1$，这样就可以少一个变元，简化接下来的运算。

暴力解一个行列式需要枚举所有全排列的情况，时间复杂度极高。然而可以使用高斯消元来对行列式进行初等变换成一个上三角矩阵，这样只需要$O(n^3)$的时间复杂度来求一个行列式对一个质数的取模，$n$为行列式的阶数。

然而这回这个问题里面有$x$这个变元，意味着我们无法进行高斯消元。但是知道得到的值是关于$x$的$n$阶多项式，可以考虑插值，把这个多项式的系数都计算出来，如果我们得到了所有系数，这个问题就迎刃而解了。

需要对一个$n$阶多项式插值，意味着至少需要知道$n$个这个多项式的取值。所以将$x=0$到$n-1$代入矩阵，分别解出对应的行列式，就能得到这些取值，时间复杂度为$O(n^4)$。

最后一步就是多项式插值，可以采用高斯消元或者拉格朗日插值法。 如果用高斯消元，系数矩阵是一个$0$到$n-1$的范德蒙矩阵，它的逆矩阵可以直接计算出来。 如果采用拉格朗日插值，需要构造出$n$个多项式，满足当$x=i$时值为$1$，$x\neq i$时值为$0$。对应取值的行向量与多项式构成的列向量做点积，就能得到这个行列式。

得到行列式之后，我们知道$x^i$的系数就是有$i$条$x$边的生成树数量，所以只需将不超过$K$的系数之和计算出来就是答案。

Written with StackEdit.