专栏文章

题解：P6178【模板】Matrix-Tree 定理

ccyffff
P6178题解参与者 17已保存评论 17

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
17 条
当前快照
1 份
快照标识符
@min8wkjp
此快照首次捕获于
2025/12/01 22:29
3 个月前
此快照最后确认于
2025/12/01 22:29
3 个月前
查看原文
Link\text{Link}
现有的证明都繁长冗杂，利用行列式的定义式带来的低秩矩阵分解这个工具，我们能轻松地证明矩阵树定理。
本文节选自 详细揭秘：低秩矩阵分解与矩阵树定理极简证明。
低秩矩阵分解
回顾行列式的定义式：
det⁡(A)=∑p1∼n(−1)inv(p)∏i=1nAi,pi\det(A)=\sum_{p_{1\sim n}}(-1)^{\text{inv}(p)}\prod_{i=1}^nA_{i,p_i}
对于求解 det⁡(A+B)\det(A+B) 的问题，根据行列式的定义式有：
  • 选取一个集合 S⊆{1,2,…,n}S\sube\{1,2,\dots,n\}；
  • ∀i∈S\forall i\in S，将 Bi,jB_{i,j} 替换为 Ai,jA_{i,j}；
  • det⁡(A+B)\det(A+B) 的值等于所有子集 SS 得到的矩阵 Bi,j′B'_{i,j} 的行列式之和；
如果其中 rank(A)\text{rank}(A) 为常数，则可以进行低秩矩阵分解：根据行列式基本性质，只有 SS 内行线性无关时才有可能做出贡献，此时明显有 ∣S∣≤rank(A)|S|\le \text{rank}(A)。
矩阵树定理
给定一张图，令 D,AD,A 分别为图的度数矩阵、邻接矩阵，则任意选定 xx 并删除 D,AD,A 中的第 xx 行、第 xx 列后，det⁡(D−A)\det(D-A) 等于该图生成树个数。
对于一条边 (u,v)(u,v)，其贡献为一个只有四个点有值的矩阵 MiM_i，其 (u,u),(v,v)(u,u),(v,v) 上的值为 11，(u,v),(v,u)(u,v),(v,u) 上的值为 −1-1。显然 MiM_i 的秩为 11，而 D−AD-A 就是 ∑Mi\sum M_i，这适用低秩矩阵分解。
相当于对每个不等于 xx 的点选择了一条边，且这些边互不相同。考虑每种方案的贡献：
  • 如果选出了环，那么这些行加起来就是全零行，故对应贡献为 00。
  • 如果没有任何环，那么考虑与 xx 相连的任意点 pp，其只能选择 (p,p)(p,p) 上的 11，因为 (p,x)(p,x) 被删去了，依此递推可以得到贡献为 11。
可以非常轻松地拓展至带权、有向版本推论。

评论

共 17 条评论，欢迎与作者交流。

正在加载评论...