矩阵树定理(Matrix-tree Theorem)是把图的生成树个数和矩阵行列式联系起来的一个定理。

矩阵树定理

有向图内向生成树计数

对于无自环(允许有重边)的有向图。设出度矩阵表示每个点的出度的对角矩阵。而表示邻接矩阵,表示的边数。那么可得到对应的拉普拉斯矩阵(Laplacian Matrix)

关于的余子式(也是主子式)是以为根的内向生成树的个数。

无向图生成树计数

主子式形式

对于无自环(允许有重边)无向图,设度数矩阵表示每个点的度,而表示邻接矩阵,表示的重边数。则

对于任意关于的余子式是生成树的个数。即,无向图的拉普拉斯矩阵的所有阶主子式的行列式值都相等。

注意到无向图矩阵树定理求的实际上是,因此它也可以理解为是求所有生成树的边权乘积的和。

特征值形式

对于个非零特征值(即无向图的至少有一个特征值为的生成树个数为

关联矩阵

在矩阵树定理应用的过程中,我们不太需要关注证明,但需要知道拉普拉斯矩阵是怎么来的。

对于无向图,我们给的每条边随便定向,定向后的图为。另外我们给边标号,第条边是那么定义的关联矩阵

容易证明,

实际上我们也很少关心关联矩阵的性质,我们关注的是:是由两个矩阵相乘得到的。

生成树计数

给出一个个点边带权完全图,求其所有生成树的边权和的次方之和,即

首先这题用斯特林数是不方便的,考虑生成函数。

我们想办法转化为矩阵树定理方便处理的形式。

注意到,即上式等于

而我们只需要求项,则可以把多项式对取模。所以我们让边权是即可。

有个细节:每个点的度是,而不是。理解了拉普拉斯矩阵怎么来的就可以理解这一点。

时间复杂度

代码