「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}$$