「OI」矩阵树定理 Matrix-Tree

（未完待续）

$\texttt{Kirchhoff}$ 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。证明比较复杂，但理解起来很简单。

前置知识

行列式

对于一个矩阵 $M$，我们定义其行列式为
$$\det(M)=\sum _ p(-1)^{\pi(p)}\prod^n _ {i=1}M _ {i,p _ i}$$

根据定义式求行列式显然十分复杂，时间复杂度为 $\Theta(n\times n!)$。下面我们考虑根据行列式的性质来简化运算。

性质

性质一

交换任意两行后，行列式的符号取反。

手动带入定义式后显然成立。

性质二

对于有两行相等的矩阵，其行列式为 $0$。

设该矩阵的行列式为 $a$。
考虑使用性质 $1$，则交换相等两行后行列式变为 $-a$，但由于矩阵不变，所以可知 $a=-a$，继而 $a=0$。

性质三

矩阵的任意一行乘 $k$，则行列式也乘 $k$。

带入定义公式即可证明。

性质四

如果一行是另一行的 $k$ 倍，那么行列式值为 $0$。

先利用性质三去除 $k$ 的影响，再由性质二得出行列式为 $0$。

性质五

一行加上另一行的 $k$ 倍，行列式不变。

我们可以把现矩阵的行列式拆成两个行列式相加，一个是原先矩阵的行列式，另一个是增长的行列式。
根据性质 $4$，可以得到增长的行列式为 $0$。

性质六

一个上三角矩阵的行列式为斜边元素之积。

根据公式显然成立。

快速求出

根据定义求行列式的方法的时间复杂度是 $\Theta(n\times n!)$，但是我们可以根据性质六进行 高斯 $\texttt{Gauss}$ 消元快速求出行列式的值。

相关的矩阵定义

无向图

对于无向图，我们定义了许多矩阵。

度数矩阵

我们用度数矩阵来描述图中每个节点的度数，具体地，用 $\operatorname{D}(G)$ 表示图 $G$ 的度数矩阵，有
$$\operatorname{D}(G) _ {i,j}=\begin{cases}\operatorname{deg}(i)&,i=j\\0&,i\ne j\end{cases}$$

邻接矩阵

我们用邻接矩阵来描述图的连通情况，具体地，用 $\operatorname{A}(G)$ 表示图 $G$ 的邻接矩阵，有
$$\operatorname{A}(G) _ {i,j}=\begin{cases}\operatorname{e}(i,j)&,i\ne j\\0&,i=j\end{cases}$$

其中 $\operatorname{e}(i,j)$ 表示 $i,j$ 之间的边数。

拉普拉斯矩阵（基尔霍夫矩阵）

我们定义 拉普拉斯 $\texttt{Laplace}$ 矩阵（亦称 基尔霍夫 $\texttt{Kirchhoff}$ 矩阵）$\operatorname{L}(G)$，有
$$\operatorname{L}(G)=\operatorname{D}(G)-\operatorname{A}(G)$$

有向图

度数矩阵

我们用入度矩阵和出度矩阵来描述有向图中每个节点的入度与出度，具体地，用 $\operatorname{D}^\text{in/out}(G)$ 表示图 $G$ 的入/出度矩阵，有
$$\operatorname{D}^\text{in}(G) _ {i,j}=\begin{cases}\operatorname{deg}^\text{in}(i)&,i=j\\0&,i\ne j\end{cases}$$
$$\operatorname{D}^\text{out}(G) _ {i,j}=\begin{cases}\operatorname{deg}^\text{out}(i)&,i=j\\0&,i\ne j\end{cases}$$

邻接矩阵

我们用邻接矩阵来描述有向图的连通情况，具体地，用 $\operatorname{A}(G)$ 表示图 $G$ 的邻接矩阵，有
$$\operatorname{A}(G) _ {i,j}=\begin{cases}\operatorname{e}(i,j)&,i\ne j\\0&,i=j\end{cases}$$

其中 $\operatorname{e}(i,j)$ 表示 $i$ 到 $j$ 的边数。

拉普拉斯矩阵（基尔霍夫矩阵）

我们定义 拉普拉斯 $\texttt{Laplace}$ 矩阵（亦称 基尔霍夫 $\texttt{Kirchhoff}$ 矩阵）$\operatorname{L}^\text{in/out}(G)$，有
$$\operatorname{L}^\text{in}(G)=\operatorname{D}^\text{in}(G)-\operatorname{A}(G)$$
$$\operatorname{L}^\text{out}(G)=\operatorname{D}^\text{out}(G)-\operatorname{A}(G)$$

矩阵树定理

矩阵树定理有四条基本内容。

基本内容

1. $$t(G)=\det\operatorname{L}(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n}$$
2. $$t(G)=\frac{1}{n}\lambda _ 1\lambda _ 2\cdots\lambda _ {n-1}$$
3. $$t^\text{root}(G,k)=\det\operatorname{L}^\text{out}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n}$$
4. $$t^\text{leaf}(G,k)=\det\operatorname{L}^\text{in}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n}$$