[学习笔记] 矩阵树定理

发表于 | 阅读次数： 
1
矩阵树定理用于计算无向图生成树个数，和基尔霍夫矩阵的行列式密切相关。

Part 1 前置知识

  1. $\text{Kirchhoff}$ 矩阵

我们记 $K$ 为 $\text{Kirchhoff}$ 矩阵，并计算出无向图$G$的度数矩阵 $D$ 和邻接矩阵 $A$ ，那么我们同通过 $K=D-A$ 就可以计算出基尔霍夫矩阵。

  1. 行列式

定义一个矩阵的行列式为 $\det(A)$

那么 $\det(A) = \displaystyle\sum_{j_1,j_2…j_n}(-1)^v\prod_{i=1}^{n} a_{i,j_i}$

其中 $v$ 表示序列逆序对的个数

  1. 主子式

取出矩阵 $B$ 的 $i$ 行 $i$ 列组成的新矩阵 $B’$ 为 $A$ 的 $i$ 阶主子式

Part 2 矩阵树定理

  1. 定义

对于一个无向图 $G$ ，它的生成树个数等于其基尔霍夫矩阵矩阵 $K$ 任何一个 $n-1$ 阶主子式的行列式的绝对值。

  1. 基尔霍夫矩阵 $K$ 的性质

  • $\det(K)=0$

  • 如果图是不连通的，则其任意 $n- 1$ 阶主子式为 $0$

证明见https://www.cnblogs.com/cjc030205/p/11790737.html（我不会）

Part 3 Binet-Cauchy定理

咕了

Part 4 例题

  1. $\text{[FJOI2007]}$ 轮状病毒

解法很多，递推也可以，最直接的解法是矩阵树定理。

当输入 $n$ 时，容易写出其 $n + 1$ 阶的 $\text{Kirchhoff}$ 矩阵，那么我们求出它的 $n$ 阶子式的行列式即可,其余就是毒瘤的高精度了。