矩阵树定理简单说明
cqbzlzm
·
·
算法·理论
介绍一下矩阵树定理的大致思路，以及关联矩阵是怎样和生成树联系起来的。
拉普拉斯矩阵
拉普拉斯矩阵 L，又叫基尔霍夫矩阵。
定义：
L_{i,j}=\begin{cases}
D_i & i=j \\
-G_{i,j}& i\neq j
\end{cases}
其中，D_i 表示 i 点的度数，G_{i,j} 表示原图中 i 点和 j 点之间连边数量。
矩阵树定理
对于无向图 G 和任意 k，定义 t(G) 是 G 的生成树个数：
t(G)=\det{L_{[n]\backslash {k},[n]\backslash k}}
关联矩阵
定义 B 是一个 n\times m 的矩阵：
B_{i,j}=\begin{cases}
1&\text{i=u[j]},\\
-1&\text{i=v[j]},\\
0&otherwise
\end{cases}
引理：L=B\times B^T。
证明：
分类讨论一下主对角线上的元素和非主对角线上的元素即可证明。
Cauchy-Binet 定理
定义大小分别为 n\times m 和 m\times n 的两个矩阵 A,B，有：
\det(AB)=\sum_{S\subseteq\{1,2,\cdots ,m\},|S|=n}{\det(A[S])\times \det(B[S])}
感性理解下。
### 生成树与行列式
定义 $B[i]$ 表示关联矩阵删掉第 $i$ 行后得到的矩阵。
因为 $B$ 的每一列的和都是 0，所以删掉的一行是可以用剩下的行表示出来的，因此没有信息丢失。
定义 $B[i]_{S}$ 表示 $B[i]$ 中选取集合为 $S$ 的列组成的矩阵（相当于选了 $S$ 中的边集），则：
$$
\det(L_{[n]\backslash {k},[n]\backslash k})=\sum_{S\subseteq E,|S|=n-1}{\det{(B[i]_{S})^2}}
$$
$i$ 是随便选的。
相当于把 $L=B\times B^T$ 用 Cauchy-Binet 定理展开。
下面说明为什么上式等于 $t(G)$。
分类讨论选出的 $S$ 构成的子图：
1. 有环不连通
写出 $B_S$：
$$
B=\begin{bmatrix}
1&0&0&0&0\\
-1&1&0&1&0\\
0&-1&1&0&0\\
0&0&-1&-1&0\\
0&0&0&0&1\\
0&0&0&0&-1
\end{bmatrix}
$$
容易发现每个极大联通快对应的行之和为 0。整个矩阵线性相关，则 $\det{B[i]}=0$。
2. 无环连通
$\det{B[i]_S} =\pm1$。
首先，原图一定有 $\geq 2$ 个叶子结点，那么 $B[i]_S$ 中也一定有至少一行表示叶子结点，这一行上只有一个 1 或 -1。
用这一行去消其他行，可以把这一列的其他位置也消成 0。
然后删掉这一行和这一列，简单归纳可证明。