矩阵树定理

· · 算法·理论

矩阵树定理，就是用矩阵去算生成树个数，可以用于各种生成树问题，非常の强悍

前置知识：

  1. 矩阵
  2. 行列式
  3. 图论
  4. 没了

无向图

Labubu Laplace 矩阵

我们定义一个无向图 G 的 Laplace 矩阵 L 为：

\deg_i, & \text{if }i=j \\ -\operatorname{e}(i, j), & \text{if }i\neq j \end{cases}

其中 \deg_i 表示 i 的度数，\operatorname{e}(i, j) 表示 i 与 j 相连的边数（因为可能有重边）。

对于一个 n 行 m 列的矩阵 A，我们记 A_{[n]/\{i\}, [m]/\{j\}} 表示删除 A 矩阵第 i 行第 j 列后的矩阵。

生成树计数

然后呢，聪明的你肯定能注意到，这个无向图的生成树个数就是

\det L_{[n]/\{k\}, [n]/\{k\}}, \text{for } k \text{ in }1,2,\cdots n

也就是说，Laplace 矩阵删掉任意一行一列然后求行列式都是这个图的生成树计数。

由于伟大的高斯消元可以用 O(n^3) 的复杂度求解行列式，于是这个算法的复杂度就是 O(n^3)。

卧槽这么牛逼的定理，但是为什么？

证明

对于一个 n 个点 m 条边的图 G(V, E)，首先给每条边随意指定一个方向，然后我们就可以构建一个关联矩阵 M：

1, & \text{if }\exists \text{ }v\in V, j = (i, v) \\ -1, & \text{if }\exists\text{ }v\in V, j = (v, i)\\ 0, & \text{otherwise} \end{cases}

注意这里的 j 表示的是一条边，所以这个位置是 1 就说明边 j 是从点 i 指出的，-1 就是指向 i 的，所以 M 是 n \times m 的。

然后我们可以惊人的发现，这个矩阵乘上它的转置，刚好就是 Laplace 矩阵，具体来说，对于 i = j，那么刚好就是 i 那一行有多少个非零数，就刚好是 i 的度数，而 i \neq j 则不是 0 的位置只有可能是这条边两端是 i 和 j，而且还是一正一负，则最后一定是 i 和 j 之间的边数的相反数。

于是乎我们删掉关联矩阵的任意一行，之后得到的 M' 矩阵乘上它的转置后也相当于原来的 Laplace 矩阵删掉该行该列。

所以我们求 Laplace 矩阵的行列式，就相当于求这个 M'M'^T 的行列式，于是：

\det(M'M'^T) &= \sum_{S\subseteq \{1, 2, \cdots, m\} \land |S| = n - 1}\det M' \det M'^T\\ &= \sum_{S\subseteq \{1, 2, \cdots, m\} \land |S| = n - 1}(\det M')^2 \end{aligned}

假如我们行列式选出的 n-1 列，即 n - 1 条边不是一个生成树，那么它必然不连通。

此时考虑每个连通分量，你会发现行向量之和为 0，因为一条边提供 1 和 -1，而且不会干涉到不在这个连通分量的边，所以这些行向量是线性相关的。

但是我们一开始还删了一行，如果删的这个点在连通块里怎么办？

你注意到虽然它被删掉了，行向量之和并不为 0，但刚好是原关联矩阵的行向量之和的相反数，这仍然是线性相关。

由于对于一个方阵，行向量线性相关等价于矩阵奇异，故行列式为 0，不会计入答案统计。

假如我们选出的是一个树，我们模拟一个类似于拓扑排序的过程，我们先选出一个叶子，令它为 v，它的父亲是 u，这条边叫 e。

如果我们一开始删的那一行就是这个 v，那么这个矩阵没有 v 就只有 u 和 e，那么 e 在 u 的位置是 \pm 1，在别的地方是 0，所以我们就可以对 e 这一列展开，这样这个矩阵最终的行列式就相当于删掉 u 这一行 e 这一列后的矩阵的行列式乘上一个 \pm 1，然后类似的继续找叶子就可以发现它的行列式就是 \pm 1。

那如果不是就说明这条边也只有在 v 和 u 上是 \pm 1，同样的我们就可以对 v 这一行 e 这一列展开，然后依旧是 \pm 1。

于是我们便证明了，如果是生成树，那么行列式的平方就是 1，否则是 0，所以上面那个式子的答案就是生成树个数。

例题：

[SHOI2016] 黑暗前的幻想乡

带权

有些题它不只让你去求生成树个数，还会让你求所有生成树的权值和，权值是这个树上每条边边权之积，那么我们该怎么办？

我们可以惊人的注意到，证明这个定理的过程是对每个点一步一步剥离出来一个 \pm 1 的系数的过程，所以如果我们把上面这个关联矩阵 M 的 \pm 1 换成 \pm \sqrt{w_e} （边权），由于是平方，最后得到的，就是边权之积。

而此时这个 M 矩阵对应的 Laplace 矩阵，就是当 i = j 的时候是与 i 相连的所有边边权之和，而 i \neq j 的时候就是 i 与 j 之间的边权之和。

例题：

[蓝桥杯第二届国际赛] 资源运输

[SDOI2014] 重建

[省选联考 2020 A 卷] 作业题（需要用多项式把加法变乘法）

有向图

我们可以注意到，无向图本质上就是每条边都是双向的有向图，所以有向图的 Laplace 矩阵和无向图的理应大差不差。

由于有向，所以入度和出度应该分开写，定义有向图 G 的入度 Laplace 矩阵 L^{\mathrm{in}} 为：

\deg^{\mathrm{in}}_i, & \text{if }i=j \\ -\operatorname{e}(i, j), & \text{if }i\neq j \end{cases}

同理的，\deg^{\mathrm{in}}_i 表示 i 的入度，\operatorname{e}(i, j) 表示 i 指向 j 的边数。

那么很显然这个图的出度 Laplace 矩阵 L^{\mathrm{out}} 就应该是：

\deg^{\mathrm{out}}_i, & \text{if }i=j \\ -\operatorname{e}(i, j), & \text{if }i\neq j \end{cases}

于是乎，我们便可以推出来，这个图以 i 为根的根向树形图（即所有边都指向父亲）个数就是：

\det L^{\mathrm{out}}_{[n]/\{i\}, [n]/\{i\}}

而叶向树形图（即所有边都指向儿子）就是：

\det L^{\mathrm{in}}_{[n]/\{i\}, [n]/\{i\}}

依旧同理的，带权我们就一样把入度或出度换成指向它的边权和或有它指出的边权和，边数换成边权和即可。

例题：

【模板】 Matrix-Tree 定理

[CQOI2018] 社交网络

没了