题解：P6178【模板】Matrix-Tree 定理
cyffff
·
·
题解
\text{Link}
现有的证明都繁长冗杂，利用行列式的定义式带来的低秩矩阵分解这个工具，我们能轻松地证明矩阵树定理。
本文节选自 详细揭秘：低秩矩阵分解与矩阵树定理极简证明。
:::info[低秩矩阵分解]{open}
回顾行列式的定义式：
\det(A)=\sum_{p_{1\sim n}}(-1)^{\text{inv}(p)}\prod_{i=1}^nA_{i,p_i}
对于求解 \det(A+B) 的问题，根据行列式的定义式有：
- 选取一个集合 S\sube\{1,2,\dots,n\}；
-
-
| 如果其中 \text{rank}(A) 为常数，则可以进行低秩矩阵分解：根据行列式基本性质，只有 S 内行线性无关时才有可能做出贡献，此时明显有 $ |
S |
\le \text{rank}(A)$。 |
:::info[矩阵树定理]{open}
给定一张图，令 D,A 分别为图的度数矩阵、邻接矩阵，则任意选定 x 并删除 D,A 中的第 x 行、第 x 列后，\det(D-A) 等于该图生成树个数。
:::
对于一条边 (u,v)，其贡献为一个只有四个点有值的矩阵 M_i，其 (u,u),(v,v) 上的值为 1，(u,v),(v,u) 上的值为 -1。显然 M_i 的秩为 1，而 D-A 就是 \sum M_i，这适用低秩矩阵分解。
相当于对每个不等于 x 的点选择了一条边，且这些边互不相同。考虑每种方案的贡献：
- 如果选出了环，那么这些行加起来就是全零行，故对应贡献为 0。
- 如果没有任何环，那么考虑与 x 相连的任意点 p，其只能选择 (p,p) 上的 1，因为 (p,x) 被删去了，依此递推可以得到贡献为 1。
可以非常轻松地拓展至带权、有向版本推论。