矩阵树定理

03 July 2018

In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time as the determinant of a matrix derived from the graph. It is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

定义：

矩阵树定理，又称基尔霍夫定理，是用来求一个图中生成树的数量。

设$D$为度数矩阵，$L$为邻接矩阵，$K$为基尔霍夫矩阵，则$K=D-L$；

矩阵树定理：

在无向图中，生成树的数量为$K$的$(i,i)$余子式；

在有向图中，以$i$为根的生成树的数量为$K$的$(i,i)$余子式；

余子式：对于一个$N*M$的矩阵$A$，将矩阵$A$的第$i$行第$j$列删去，剩下的$(N-1)*(M-1)$的矩阵的行列式，称为$A$的$(i,j)$余子式；

实现：

求一个矩阵的行列式往往用$Gauss$消元；

数学上，高斯消元法（英语：Gaussian Elimination），是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个行梯阵式。

在理解为何可以使用$Gauss$消元前，我们需要知道以下几条行列式的性质：

1.行列式中的两行（列）互换，改变行列式正负符号；

2.将一行（列）的k倍加进另一行（列）里，行列式的值不变；

3.将行列式扩大$k$倍，等于把某一行（列）扩大$k$倍；

上三角行列式和下三角行列式：

形如

或

的行列式分别称为上三角形行列式和下三角形行列式，亦称上三角行列式和下三角行列式，统称三角形行列式。每个行列式都可以只运用行或者列的性质化为一个与其相等的上(下)三角形行列式。上(或下)三角形行列式都等于它们主对角线上元素的乘积；

有了这些，我们就可以用$Gauss$消元来求行列式了，只需要用一些变换把一个行列式换成三角形行列式即可；

例题：

$Gauss$消元：

[SDOI2010]外星千足虫

题目

题解

矩阵树定理：

[CQOI2018]社交网络

题目

题解

[SHOI2016]黑暗前的幻想乡

题目

题解