「from CommonAnts」Matrix-Tree 定理相关

liu_cheng_ao 2017-06-01 14:50:49 2017-06-01 17:34:53

本文主要内容是 Matrix-Tree 定理相关知识的讲(kou)解(hu)

欢迎转载,荣幸之至。

本文作者很菜,但还是希望能有抛砖引玉的效果……

以下是吐槽


很久以前遇到了生成树计数的题,就去搜了几篇 Matrix-Tree 定理的博客学习了一番,觉得自己学会 OI 中的生成树计数了,直到昨天被一道题虐成 SB,才发现……我太菜了 QwQ 题目传送门:https://ly.men.ci/problem/256 请自觉把数据加强到 $n\leq 100$。
有趣的是,Matrix-Tree 定理确实和基尔霍夫电流定理有关,是基尔霍夫研究电网络时证明的,基尔霍夫矩阵在图论和电学中的定义是一致的。
#### 以上是吐槽

前置技能:矩阵基础
注意……下文中似乎有些地方口胡把余子矩阵和余子式说混了……请按上下文食用。

首先来介绍一下经典的 Matrix-Tree 定理。

无向图的 Matrix-Tree 定理

设无向图 G=(V,E),|V|=n,|E|=m 。这段内容中的图均为无向图。
定义 G 的度数矩阵 D[G] 为一个 n\times n 的矩阵,满足: \forall i\neq j,D[G]_{ij}=0,\forall i=j,D[G]_{ij}=\deg i
定义 G 的邻接矩阵 A[G] 为一个 n\times n 的矩阵,满足: \forall i,j,A[G]_{ij}=\sum_{e\in E=(i,j)}1
定义 G 的基尔霍夫矩阵 C[G]=D[G]-A[G]
那么,有:
定理 1 (Matrix-Tree定理) G 的所有不同的生成树的个数等于 C[G] 任何一个 n-1 阶主子式的行列式的值。

为了证明的简洁,先提几个引理:
引理 1 \forall G=(V,E),|C[G]|=0
证:根据 C[G] 的定义,其每行每列的和都为 0,当 n=1 时显然成立,否则前 n-1 行(列)的和是最后一行(列)的相反数,和最后一行(列)线性相关,故有 \mathop{\text{rank}} C[G]\leq n-1,|C[G]|=0
引理 2 对于一棵树 G=(V,E),\forall 1\leq i\leq n,|C[G]_i|=1 。( A_i 表示矩阵 A 关于第 i 行和列的主余子式)
证:设一开始 i 对应的点为 r ,将点的标号按照与 r 的距离排序,将矩阵 C[G]_i 交换成该顺序(交换两个点时,行和列都要交换,因而行列式值不变),设交换后的矩阵为 C' 。设 f_v 为这棵树看作以 r 为根的有根树时, v 的父亲。然后按与 r 的距离逆序每次将 v 对应的列加到其父亲(如果不是 r 的话)一列上。这样处理之后,我们发现: C' 是一个上三角矩阵并且主对角线上全是 1。故 |C[G]_i|=|C'|=1
用归纳法证明:最后一个点只和父亲有边,度为 1;否则假设当前处理的是第 i 列,并且第 i+1 至第 n-1 列都符合要求。则只有它的孩子对应的列才会加到第 i 列上来。所有这些列,都在第 i 行有个 -1 而在对角线上有个 1;而第 i 列在儿子对应的行上为 -1,在第 i 行上为 \deg i 。儿子对应的列加上后,这些-1 变为 0,而 \deg i 会变成 1(只剩下 i 于父亲连边的贡献)。证毕。
引理 3 G 的连通分量集是 S ,则 |C[G]_i|=|C[G_{b_i}]_i|\prod _{G'\in S,i\notin G'} |C[G']| ,其中 b_i 表示 i 所属的连通分量。
证:设 |S|=c,S={G_1,G_2,...,G_c} ,将 G 中的点按所属连通分量排序,则:

C[G]=\begin{bmatrix} C[G_1] & 0 & ... & 0 \\ 0 & C[G_2] & ... & 0 \\ ... & ... & ... & ... \\ 0 & 0 & ... &C[G_c] \end{bmatrix}

|C[G]^{ii}|=|C[G_{b_i}]^{ii}|\prod _{G'\in S,i\notin G'} |C[G']| ,证毕。
推论 1 不连通的图的基尔霍夫矩阵的任何一个主余子式的行列式为 0

根据引理 2 和 3,可以立刻得到一个朴素的想法: G i 为根的生成树个数等于 G 的所有 n 个点 n-1 条边的子图的基尔霍夫矩阵的关于 i 的主余子式的行列式之和

可以发现:边数与矩阵的阶相同。这样,熟悉线性代数的人会想到 Binet-Cauchy 公式:
定理 2 (Binet-Cauchy 公式) A B 各为 p\times q q\times p 矩阵,则有:

|AB|= \begin{cases} 0& p>q\\ \sum_{1\leq i_1<i_2<...<i_p\leq q}|A^{\{1,2,...,p\},\{i_1,i_2,...,i_n\}}||B^{\{i_1,i_2,...,i_n\},\{1,2,...,p\}}|& p\leq q \end{cases}

其中 A^{i,j} 表示取出 A i 中的行和 j 中的列交叉位置的元素组成的矩阵。

因而,为了枚举 n-1 条边,我们要用到一种 n\times m 的矩阵,即 G 的关联矩阵。
定义 G 的关联矩阵 B[G] 为一个 n\times m 的矩阵,满足: \forall i,j,B[G]_{ij}=[j 的一个端点是 i]
我们发现 B[G]B[G]^T=A[G]+D[G] 并不是基尔霍夫矩阵。但可以对 B 的定义做一些修改:一条边对应的列中,两个点行的位置一个为 1,另一个为 -1。这样,我们就可以得到: B[G]B[G]^T=C[G]
另外,在 B[G] 中取一个列的集合得到 B' ,则 B'B'^T 就是这些边对应的子图的基尔霍夫矩阵;将 B[G] 的第 i 行删掉得到 B' ,则 B'B'^T 就是 C[G]_i
根据我们的想法, G 的以 i 为根的生成树个数就是 B[G] 每个大小为 n-1 的列集合删掉第 i 行后与其转置之积的行列式之和。根据 Binet-Cauchy 公式,这个值等于 |C[G]|
至此,我们证明了 Matrix-Tree 定理。

接下来……

有向图的 Matrix-Tree 定理

设有向图 G=(V,E),|V|=n,|E|=m 。这段内容中的图均为有向图。
定义 G 的入度矩阵 D[G] 为一个 n\times n 的矩阵,满足: \forall i\neq j,D[G]_{ij}=0,\forall i=j,D[G]_{ij}=i 的入度。
定义 G 的邻接矩阵 A[G] 为一个 n\times n 的矩阵,满足: \forall i,j,A[G]_{ij}=\sum_{e\in E=(i,j)}1
定义 G 的基尔霍夫矩阵 C[G]=D[G]-A[G]
那么,有:
定理 3 G 的以 i 为根的生成树形图的个数等于 C[G]_i 的值。

证法类似无向图:
引理 4 \forall G=(V,E),|C[G]|=0
证:根据 C[G] 的定义,其每列的和都为 0,当 n=1 时显然成立,否则前 n-1 行的和是最后一行的相反数,和最后一行线性相关,故有 \mathop{\text{rank}} C[G]\leq n-1,|C[G]|=0
引理 5 对于一个以 i 为根的树形图 G=(V,E),|C[G]_i|=1
证:将点的顺序交换为拓扑序,设交换后的矩阵为 C' ,则根据拓扑序的性质, C' 是上三角矩阵。又根据树形图的性质,除根外每个点入度为 1 ,故 C' 是个主对角线全为 1 的上三角矩阵。证毕。
推论 2 基图为树的图,若有不少于 2 个入度为 0 的点,则基尔霍夫矩阵的任何一个主余子式的行列式为 0;否则,基尔霍夫矩阵关于除入度为 0 的点之外的点的主余子式的行列式为 0。
引理 6 G 的基图的连通分量集是 S ,则 |C[G]_i|=|C[G_{b_i}]_i|\prod _{G'\in S,i\notin G'} |C[G']| ,其中 b_i 表示 i 所属的连通分量。
证:设 |S|=c,S={G_1,G_2,...,G_c} ,将 G 中的点按所属连通分量的拓扑序排序,则:

C[G]=\begin{bmatrix} C[G_1] & 0 & ... & 0 \\ 0 & C[G_2] & ... & 0 \\ ... & ... & ... & ... \\ 0 & 0 & ... &C[G_c] \end{bmatrix}

|C[G]^{ii}|=|C[G_{b_i}]^{ii}|\prod _{G'\in S,i\notin G'} |C[G']| ,证毕。
推论 3 基图不连通的图的基尔霍夫矩阵的任何一个主余子式的行列式为 0

根据引理 5 和 6,可以得到: G i 为根的生成树形图个数等于 G 的所有 n 个点 n-1 条边的子图的基尔霍夫矩阵的关于 i 的主余子式的行列式之和

我们继续使用 G 的关联矩阵。
我们需要 B[G]B[G]^T 是基尔霍夫矩阵。但我们发现无论如何都不能做到这一点。
但我们可以构造两个矩阵 B[G] B'[G] ,其中 B[G] 满足:一条边对应的列中,起点行的位置为 -1,终点行的位置为 1, B'[G] 满足:一条边对应的列中,起点行的位置为 0,终点行的位置为 1。
这样, B[G]B'[G] 与上面无向图中的 B[G]B[G]^T 意义相同了。
至此,我们证明了有向图的 Matrix-Tree 定理。

有重边的 Matrix-Tree 定理

我们发现上面的证明根本没有用到无重边的性质嘛……因而只要仍然保持 C B 的性质,实际上我们不需要更改任何东西。

生成树和生成树形图的关系

只要给生成树中定一个根,我们就发现它和一个生成树形图一一对应……于是只要把无向边拆成两条有向边即可,这样混合图之类的东西都能做了。

带正整数权值的 Matrix-Tree 定理

如果一条边有边权会怎样……
考虑一棵树的基尔霍夫矩阵的主余子式的意义。为了消元,我们不得不把度数矩阵和邻接矩阵定义改成边权和。具体来说,就是:
定义 G 的度数矩阵 D[G] 为一个 n\times n 的矩阵,满足: \forall i\neq j,D[G]_{ij}=0,\forall i=j,D[G]_{ij}=i 的入边的权值和。
定义 G 的邻接矩阵 A[G] 为一个 n\times n 的矩阵,满足: \forall i,j,A[G]_{ij}=\sum_{e\in E=(i,j)}w_e
另外,我们需要修改关联矩阵:
两个矩阵 B[G] B'[G] ,其中 B[G] 满足:一条边对应的列中,起点行的位置为 -1,终点行的位置为 1, B'[G] 满足:一条边对应的列中,起点行的位置为 0,终点行的位置为边权。
这样, B[G]B'[G]=C[G] ,并满足上文所述的各种性质。
由于一棵树的基尔霍夫矩阵行列式为除根外每个点的父边权值之积(对于无向图就是所有边边权之积),我们可以发现算出来的是所有生成树边权之积的和。
当权值是正整数时,相当于权值条重边做乘法原理。

更一般的带权的 Matrix-Tree 定理

我们需要知道边权能用什么东西。一个复数?一个多项式?
首先,我们用到了矩阵和行列式的一些基本知识。这要求边权的定义必须是一个环 R
其次我们发现证明中没有任何地方用到除了环的一般性质以外的东西。这表明,Matrix-Tree 定理对于任意环的边权都成立
当然,不是每个环都能让你快速计算行列式。不过 OI 中真的有人会用到欧几里德环以外的边权吗……
例题:https://ly.men.ci/problem/256
就是先按位做,边权变成一个三维向量 (a_0,a_1,a_2) 表示边权和模 3 为 0,1,2 的方案各有多少。乘法定义成循环卷积,加法定义成对应位置相加就好了……事实上是个指数模 3 意义下的多项式,因此显然是个环。

Matrix-Tree 定理另外的几个拓展

求给定一些必选边的生成树个数。参见[1]。这个直接把连通的点缩点就行。
求生成树边权和之和。我似乎只会枚举每条边计算包含它的生成树个数。
求给定每个连通块的根的生成森林个数。参见[2]。做法是把这些点对应的行/列删除然后算行列式。

几个结论

n 个点完全图的生成树或给定根的生成树形图有 n^{n-2} 个。
两侧分别有 n m 个点的完全二分图的生成树有 n^{m-1}m^{n-1} 个。

参考资料:
[1]周冬.生成树的计数及其应用.2007年信息学奥林匹克中国国家队候选队员论文集.2007.
[2]郑碧霞.Kirchhoff矩阵树定理的一个推广.福州师专学报(自然科学版)第20卷 第3期.2000.

共 1 条回复

guo_dong

orz