矩阵树定理

BJpers2 · 2019-08-11 14:59:26 · 个人记录

这是一类生成树计数的技巧，不过相对其他算法来说比较独立，命题空间不如其他算法大，因而在历年的全国性大赛中没有怎么出现过。

写出这篇文章主要是介绍一个关于它的美妙证明。

一、矩阵树定理

定理内容

定义无向图G的\text{Laplace}矩阵L为其「度数矩阵」减去「邻接矩阵」，则图G的「生成树」个数为L任意位置的「代数余子式」。

概念解释

度数矩阵

假设图中点u有\deg(u)条边与之相连，那么其度数矩阵
D=\text{diag}(\deg(1),\deg(2),\dots,\deg(n))
邻接矩阵

图的邻接矩阵
A=\{a_{ij}=[(i,j)\in E]\}
代数余子式

矩阵某个位置(i,j)的「代数余子式」定义为删去它所在的行列之后剩下矩阵的「行列式」乘上(-1)^{i+j}。记为(-1)^{i+j}M_{ij}。

使用限制

（之后会给出这些限制下的计数方法）

二、相关证明

引理1

无向图的\text{Laplace}矩阵L在每个位置的代数余子式都相等。

证明

根据定义，L每行每列的和都为0，我们只要用这条性质证明每行的代数余子式相等，列可以同理得到。
考虑代数余子式(-1)^{i+j}M_{ij}和(-1)^{i+j}M_{ik}，不妨设j<k。接下来我们尝试证明矩阵挖掉第i行第j列的矩阵L'和挖掉第i行第k列的矩阵L''的行列式只相差(-1)^{j-k}这一个符号。
首先把L'中第k列(实际指原矩阵中的第k列在L'中的对应列)取反，那么行列式也取反。
把第1,2,\dots,j-1,j+1,\dots,k-1,k+1,\dots,n这些列乘-1加到L'的第k列上，行列式不变。
根据L每行之和为0，新的矩阵第k列应该与L''中的第j列完全相同。我们做k-j-1次列交换，矩阵便与L''完全相同，而其行列式应当乘上(-1)\times(-1)^{k-j-1}=(-1)^{j-k}才是L'的行列式。也即\det(L'')=\det(L')(-1)^{j-k}。命题得证。

引理2

矩阵L前n-1行n-1列的「行列式」中的每一项(乘了对角线上的值就将其拆成多个1相加)，与满足下列条件的有向有色图H存在「双射」：

除n之外每个点只有一条出边。

每条边有黑白两种可能，但黑色边只能出现在环上，且对于任意一个环，环上要么全为黑色边，要么全为白色边。

证明

该双射的构造如下：
考虑行列式的展开式
\det(A)=\sum_{\sigma\in S_n}(-1)^{r(\sigma)}\prod_{i=1}^n a_{i\sigma(i)}
其中S_n为n阶置换群，r(\sigma)表示\sigma变为单位置换id所需的「对换」次数（也就是我们常说的逆序对个数）。

它可以看作是一个符号配上n行中每行选择一个数的乘积，之后再求和。并要求选出的每个数不同列。
若i\not=\sigma(i)，视为i向\sigma(i)连了一条黑边。这一项会乘上-1。
否则i=\sigma(i)视为i向某个连向它的点连了一条白边。这个点可以规定为展开之前拆出的1在括号里的「位置」对应的点。

例如我们有图的\text{Laplace}矩阵去掉第n行第n列的结果：
L'=\begin{pmatrix}(1^{[2]}+1^{[3]}) & -1 & -1 \\ -1 & 1^{[1]} & 0 \\-1 & 0 & 1^{[1]} \\ \end{pmatrix}
如果选择(1,1)^{[2]},(2,2)^{[1]},(3,3)^{[1]}视为，1向2连白边，2,3向1连白。

而选择(1,1)^{[3]}则视为向1向3连白边。
考虑这样一张图的性质：
1. 图中所有边都能由原图G中的边定向得到。
2. 不看颜色，图是由若干棵「环基内向树」和一棵以n为根的「内向树」构成的（除n外每点一出边）。
4. 每个点最多只可能有一条黑色出边（每行只选一个数）。
5. 若一个点有一条黑色入边，那它的出边是黑的，而且这样的黑色入边最多只能有一条。（每列只选一个数）。
6. 根据性质3,4容易知道黑边只能在「环」上（若有黑边在「树」上，它要么在一棵环基树的「子树」上，那根据性质4会使它能走到的边全都必须是黑的，从而导致它对应的「树根」有两条黑色入边，这违反性质3；要么它在以n为根的「树」上，这会导致n有至少一条黑色入边，这违反性质2）。
7. 任意满足第1,5条的「图」都能唯一对应不同的行列式展开式中的一项。
从而我们成功建立了行列式中的项到图的「双射」，每项对应1（或-1）张图。我们定义这张图H的符号\text{sgn}(H)为(-1)^{\text{number of black edges}}\times(-1)^{r(\sigma)}。

定理

图G的「生成树」个数为其\text{Laplace}矩阵任意位置的「代数余子式」。

证明

由引理1，我们知道所有位置的「代数余子式」相同，因此只需证M_{nn}为「生成树」的个数。
由引理2，我们考虑所有满足上述「性质」的图的集合\mathbb{H}。可以自然地引出：
\det L'=\sum_{H\in\mathbb{H}} \text{sgn}(H)
只需证「生成树」个数等于等式右边。
对于H\in \mathbb{H}，我们分为三种情况
显然\mathbb{H}=\mathbb{T+H^++H^-}。
接下来只需说明两件事：
1. \forall H \in \mathbb{T},\text{sgn}(H)=1
2. |\mathbb{H^+}|=|\mathbb{H^-}|
- 对于第一条，我们由「性质5」可知这棵树上全是白色边，因此必然有\text{sgn}(H)=1
- 对于第二条，我们尝试构建\mathbb{H^+}到\mathbb{H^-}的双射。
首先对于任意含有「环」的图H，我们定义映射f表示将其中的含点标号最小的「环」上所有边颜色取反，显然新图f(H)=H'\in\mathbb{H}。

考虑这次「变换」带来了什么。

假设环上有k个点，则符号首先变化了(-1)^k

之后考虑r(\sigma)的变化，\sigma中有一个「子序列」从恒等置换id变为「轮换」a_i\rightarrow a_{i+1}。将恒等置换通过「对换」变为「轮换」操作需要的步数为k-1步，而中间的元素必然被操作恰好偶数次（因为每次「对换」是总会是一来一去）则其符号改变为(-1)^{k-1}。

从而总的符号该变量就是(-1)^{k}(-1)^{k-1}=-1。

我们得到\text{sgn}(H)=-\text{sgn}(H')。

因此\forall H \in \mathbb{H^+},f(H)\in \mathbb{H^-}。根据f的定义，因为最小环只有一个，所以所有的f(H)各不相同。反过来也有\forall H \in \mathbb{H^-},f(H)\in \mathbb{H^+}

所以\mathbb{H^+}\leftrightarrow \mathbb{H^-}，也就是说|\mathbb{H^+}|=|\mathbb{H^-}|。
由以上两点我们可以推出
\det L'=\sum_{H\in\mathbb{H}} \text{sgn}(H)=|\mathbb{T}|+|\mathbb{H^+}|-|\mathbb{H^-}|=|\mathbb{T}|
然而图G的「生成树」集合\mathfrak{T}与以n根为根的「生成内向树」集合\mathbb{T}也明显存在「双射」。原命题得证。

三、相关推论

推论\bold{1}

有向图G的以x为「根」的「生成内向树」个数为其「出度矩阵」减「邻接矩阵」在(x,x)处的「代数余子式」。（「邻接矩阵」定义为a_{ij}=[i\rightarrow j]\in E）

证明

考虑仍然构造上述「行列式的项」到「图」的双射，发现上面所有的理论都对这个构造完全成立。

推论\bold{2}

有向图G的以x为「根」的「生成外向树」个数为其「入度矩阵」减「邻接矩阵」在(x,x)处的「代数余子式」。（「邻接矩阵」定义为a_{ij}=[i\leftarrow j]\in E）

证明

以x为根的「生成外向树」与反图上的「生成内向树」构成双射，根据推论1即可证明。

推论\bold{3}

令S=\{i_1,i_2,\dots,i_k\}，无向图G的满足i_1,i_2,\dots,i_k不在同一棵树的含有恰好k个「联通块」的「生成森林」个数为
\det(L_{S,S})
其中A_{P,Q}表示矩阵A删去P集合中的行和Q集合中的列得到的结果。

证明

同样构造双射，集合\mathbb{H}中的图变为含有以i_1,i_2,\dots,i_k为根的只含「白边」的树和若干环基树。\mathbb{T}的定义变为以i_1,i_2,\dots,i_k为根的「内向森林」。
这样一来上述理论能全部适用。

推论\bold{4}

无向带权图G的所有生成树边权权值之积的「和」等于其「带权度数矩阵」减去「带权邻接矩阵」的任意「代数余子式」。

证明

考虑上述证明过程，把「黑边」也看作是从括号中选择的结果，发现并不影响后续的证明。

推论\bold{5}

假设完全无向图G的一个生成森林有k个联通块，每个联通块分别有a_1,a_2,\dots,a_k个点。那么该图的包含这个森林的生成树个数为n^{k-2}\prod_{i=1}^{k} a_i

证明

我们并不关心每个联通块的具体形态，而只关心点数。实际上，该问题可以转化为「i,j之间有a_ia_j条边」的无向完全图生成树计数。
转化成\text{Laplace}矩阵，我们要求的答案为
\begin{vmatrix}(n-a_1)a_1 & -a_1a_2 & -a_1a_3 & \cdots & -a_1a_{k-1} \\ -a_2a_1 & (n-a_2)a_2 & -a_2a_3 & \cdots & -a_2a_{k-1} \\ -a_3a_1 & -a_3a_2 & (n-a_3)a_3 & \cdots & -a_3a_{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -a_{k-1}a_1 & -a_{k-1}a_2 & -a_{k-1}a_3 & \cdots & (n-a_{k-1})a_{k-1} \\ \end{vmatrix}
提出行的公因数得到
\prod_{i=1}^{k-1}a_i\begin{vmatrix}n-a_1 & -a_2 & -a_3 & \cdots & -a_{k-1} \\-a_1 & n-a_2 & -a_3 & \cdots & -a_{k-1} \\-a_1 & -a_2 & n-a_3 & \cdots & -a_{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -a_1 & -a_2 & -a_3 & \cdots & n-a_{k-1} \\\end{vmatrix}
从下到上，第i+1行减第i行。
\prod_{i=1}^{k-1}a_i\begin{vmatrix}n-a_1 & -a_2 & -a_3 & \cdots & -a_{k-1} \\-n & n & 0 & \cdots & 0 \\0 & -n & n & \cdots & 0 \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 & \cdots & n \\\end{vmatrix}
用第一行的代数余子式展开
\prod_{i=1}^{k-1}a_i\bigg((n-a_1)n^{k-2}+\sum_{i=2}^{k-1} (-1)^{i+1}(-a_i)(-1)^{i+1}n^{k-2}\bigg)
整理可得答案为
n^{k-2}\prod_{i=1}^ka_i