（未完待续）
$\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)$$
矩阵树定理
矩阵树定理有四条基本内容。
基本内容
- $$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}$$
- $$t(G)=\frac{1}{n}\lambda _ 1\lambda _ 2\cdots\lambda _ {n-1}$$
- $$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}$$
- $$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}$$
近期评论