(未完待续)
$\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}$$
近期评论