学习笔记 - Matrix-Tree矩阵树定理 | Lucky_Glass's Blog
0%

学习笔记 - Matrix-Tree矩阵树定理

参考 (知乎)矩阵树定理(Matrix-tree Theorem)笔记


# 线代基础

行列式——在矩阵树定理中要用到其中的一些性质,这里只列出:

- 定义(并不严谨)

行列式是对一个方阵定义的运算,结果为标量。对 $A$ 方阵进行行列式运算可记作 $|A|$ 或 $\det A$。

具体来说,运算规则如下:若 $A$ 是一个 $n\times n$ 的方阵;记 $P=\{p_1,p_2,\dots,p_n\}$ 为 $1,2,\dots,n$ 的一个排列,$f(P)$ 为 $P$ 中逆序对的数量;则:

(上式对 $P$ 求和意为对 $P$ 取 $1,2,\dots,n$ 的所有排列求和)

- 重要性质

  1. 记 $A’$ 为 $A$ 的两行或两列互换后得到的方阵,则 $|A’|=-|A|$。
  2. 如果 $A$ 的某一行或列全为 $0$,则 $|A|=0$;如果方阵 $A$ 有两行或两列完全相同,则 $|A|=0$。
  3. 记 $A^T$ 为 $A$ 的转置矩阵

推论:将 $A$ 的第 $i$ 行的每个元素乘上 $k$ 再加到第 $j$ 行上($i\neq j$),$A$ 的行列式运算结果不变。


# Matrix-Tree 定理

- 定义&性质

于是在简单地记住行列式的几个性质后,我们就可以粗略地证明一下矩阵树定理了

最基础的矩阵树定理定义在一个无向图上,记无向图 $G=(V,E)$ 有 $n$ 个点 $m$ 条边,其中 $E=\{e_1,e_2,\dots,e_m\}$,$V=\{v_1,v_2,\dots,v_n\}$。

定义 $G$ 的关联矩阵 $M$ 如下。先给 $G$ 的每条边任意指定一个方向,则 $M$ 是一个 $n\times m$ 的矩阵:

再定义一个拉普拉斯矩阵 $L$:记无向图 $G$ 中 $v_i,v_j$ 之间有 $m_{ij}$ 条边,$v_i$ 的度数为 $d_i$,

根据 $L$ 的实际意义,可以得到 $L=M\times M^T$($M^T$ 是 $M$ 的转置矩阵,即 $M$ 沿对角线翻转,乘法为矩阵乘法)

$L=M\times M^T$ 的证明

首先 $L_{ij}=\sum_k M_{ik}M^T_{kj}=\sum_k M_{ik}M_{jk}$;

考虑两种情况即 $i=j$ 和 $i\neq j$:

  • $i=j$,则当且仅当 $e_k$ 与 $v_i$ 相邻时,$M_{ik}M_{jk}=1$,否则为 $0$,所以是 $v_i$ 的度数;
  • $i\neq j$,如果 $e_k$ 是 $v_i,v_j$ 之间的边(无论方向),则 $M_{ik}M_{jk}=-1$,否则为 $0$,因此为 $-m_{ij}$。

根据 $M$ 矩阵,我们再定义 $M_0$ 为 $M$ 删除最后一行的余矩阵。

根据 $M_0$,定义子矩阵 $M_0[S]$($S$ 为一个大小为 $n-1$ 的集合,$S$ 的每个元素都是 $1$ 到 $m$ 的整数)表示:将 $M_0$ 中所有 $i\in S$ 列都取出来得到的子矩阵。

- 矩阵树定理

可以知道 $M_0[S]$ 中 $S$ 的 $n-1$ 个元素指代的是 $G$ 的 $n-1$ 条边,则有:

如果 $S$ 中的 $n-1$ 条边构成一棵生成树,则 $M_0[S]=\pm1$,否则 $M_0[S]=0$。

(因为我不会严谨的证明,就简单地说明一下,应该可以意会)

上述引理的证明

  • 如果 $S$ 构成生成树,则可以将生成树中的每个节点拓扑排序,注意到 $M_0$ 是一个 $n-1$ 行的矩阵,因为我们删除了 $M$ 的最后一行(代表 $v_n$ 的那行)。因此在拓扑排序时,我们强制使 $v_n$ 成为最后被拓扑到的那个节点。
    然后按拓扑序枚举 $v_i$,设拓扑时与 $v_i$ 唯一相邻的节点为 $v_j$、$v_i$ 与 $v_j$ 相邻的边为 $e_k$,则我们将 $M_0[S]$ 的第 $j$ 行加上第 $i$ 行,可以知道此时 $M_0[S]_{jk}=0$,并且 $|M_0[S]|$ 不变。
    显然第一个拓扑到的 $v_i$ 对应的 $M_0[S]$ 的第 $i$ 行只有一个位置为 $\pm1$,其余位置为 $0$。根据数学归纳,当我们枚举到 $v_i$ 时 $M_0[S]$ 的第 $i$ 行只有一个位置为 $\pm1$。
    当我们处理完所有 $n-1$ 次操作后,$M_0[S]$ 变成了一个每行、每列都只有一个元素为 $\pm1$ 的矩阵,再排个序就可以得到对角线只有 $\pm1$,其他位置都是 $0$ 的一个矩阵,此矩阵的行列式运算结果为 $\pm1$。
  • 如果 $S$ 中存在环(不存在环是构成生成树的充要条件),则将环中的 $k$ 个点对应的 $k$ 行与环中的边对应的 $k$ 列提取出来得到子矩阵,该 $k\times k$ 的子矩阵的行列式运算结果为 $0$。则对应的原矩阵运算结果亦为 $0$。


则矩阵树定理为:定义 $L_0$ 为矩阵 $L$ 删去任意一行与任意一列(一般是删去最后一行最后一列)得到的矩阵,则 $\det L_0$ 就是生成树的个数。

在证明这个定理时,还需要用到一个结论——Binet-Cauchy Theorem:

设 $A$,$B$ 为两个 $n\times m$ 的矩阵,则:

其中 $S$ 是一个大小为 $n$ 的集合,元素范围为 $[1,m]$。$A[S],B[S]$ 定义类似 $M_0[S]$ 的定义。

则对矩阵树定理的简单证明如下:

证明同 $L=M\times M^T$,可以得到 $L_0=M_0\times M^T_0$;

其中 $M_0^T[S]$ 表示取 $M_0^T$ 的属于集合 $S$ 的列。
等式第二行是因为矩阵转置后行列式不变。

可以知道 $S$ 构成生成树时,$\det M_0[S]=\pm 1$,则 $(\det M_0[S])^2=1$,否则 $(\det M_0[S])^2=0$,因此对所有 $S$ 求和,得到的答案就是生成树的方案数。


THE end

Thanks for reading!