对于矩阵树定理的运用

学得很肤浅，但是常见的东西还是要记一下。

证明以后懂了再补。

一些定义：

定义 \(deg_x\) 表示点 \(x\) 的度数，\(cnt_{i,j}\) 表示 \(i\) 到 \(j\) 相连有的边数。

度数矩阵 \(D\) ： \(D_{i,i} = deg_i\)，\(D_{i,j} =0(i \neq j)\)；
关联矩阵 \(A\) ： \(A_{i,j} = cnt_{i,j}\)；

Laplace 矩阵： \(D - A\)

用处

处理关于生成树计数的问题。

证明：

\

内容

首先先是无向图，求出原图的 Laplace 矩阵，任意删去一行一列之后的行列式即是原图的生成树个数。

有向图：

关联矩阵定义不变

• 叶向树

叶向树指树上所有边的方向都指向叶子方向
度数矩阵中的 \(deg_x\) 表示为点 \(x\) 的入读，若要求以 \(k\) 为根的叶向树个数，删去矩阵第 \(k\) 行与第 \(k\) 列即可。

• 根向树

根向树指树上所有边的方向都指向根方向
度数矩阵中的 \(deg_x\) 表示为点 \(x\) 的出读，若要求以 \(k\) 为根的根向树个数，删去矩阵第 \(k\) 行与第 \(k\) 列即可。

技巧

• 如何求所有生成树的边权之和？

将之前的边权的改为一个二项式（形如 \(a+bx\)），再做以上操作，一次项所得的系数就是边权值和。

• 一个无向图上有的边有黑和白两种颜色，问生成树中有 \(x\) 条黑边的树

类似上面的做法，把黑边化成二项式之后，找多项式的 \(x\) 次项即可。