矩阵树定理

Kirchhoff 矩阵树定理(简称矩阵树定理)解决了一张图的生成树个数计数问题。

本篇记号声明

本篇中的图,无论无向还是有向,都允许重边,但是不允许自环。

无向图情况

是一个有 个顶点的无向图。定义度数矩阵 为:

为点 与点 相连的边数,并定义邻接矩阵 为:

定义 Laplace 矩阵(亦称 Kirchhoff 矩阵) 为:

记图 的所有生成树个数为

有向图情况

是一个有 个顶点的有向图。定义出度矩阵 为:

类似地定义入度矩阵

为点 指向点 的有向边数,并定义邻接矩阵 为:

定义出度 Laplace 矩阵 为:

定义入度 Laplace 矩阵 为:

记图 的以 为根的所有根向树形图个数为 。所谓根向树形图,是说这张图的基图是一棵树,所有的边全部指向父亲。

记图 的以 为根的所有叶向树形图个数为 。所谓叶向树形图,是说这张图的基图是一棵树,所有的边全部指向儿子。

定理叙述

矩阵树定理具有多种形式。其中用得较多的是定理 1、定理 3 与定理 4。

定理 1(矩阵树定理,无向图行列式形式) 对于任意的 ,都有

其中记号 表示矩阵 的第 行与第 列构成的子矩阵。也就是说,无向图的 Laplace 矩阵具有这样的性质,它的所有 阶主子式都相等。

定理 2(矩阵树定理,无向图特征值形式) 个非零特征值,那么有

定理 3(矩阵树定理,有向图根向形式) 对于任意的 ,都有

因此如果要统计一张图所有的根向树形图,只要枚举所有的根 并对 求和即可。

定理 4(矩阵树定理,有向图叶向形式) 对于任意的 ,都有

因此如果要统计一张图所有的叶向树形图,只要枚举所有的根 并对 求和即可。

BEST 定理

定理 5 (BEST 定理) 是有向欧拉图,那么 的不同欧拉回路总数

注意,对欧拉图 的任意两个节点 ,都有 ,且欧拉图 的所有节点的入度和出度相等。

定理证明

前置知识:LGV 引理

定义 ,矩阵 的子式 为选取 的元素得到的子矩阵。

定义一条边 的权值为

以下的内向也指根向,表示有向边的方向指向根。

引理 1(Cauchy-Binet) 给定 的矩阵 的矩阵 ,则有

证明:考虑建出有向无环图



「NOI2021」路径交点 的模型相同,容易发现上式左右两侧计算的都是 的不相交路径组中,交点个数为偶数的方案数减去奇数的方案数,其中 表示路径组经过的 中的点。

性质 1 Laplace 矩阵 的所有代数余子式 的值都相等。

证明:删去第 行后,设列向量是 ,则有

将余子式 中除了 之外的所有 都加到 上,得到

取反并通过交换两列移动到 左边,得到 ,所以

同理,删去第 列后行向量之和为 ,得到

定理 1(Kirchhoff's Matrix Tree) 对于带边权的简单无向图 ,若 的生成树,定义 所有生成树的集合,则 的 Laplace 矩阵的所有代数余子式的值等于

证明:根据性质 1,只需证明 。对于一条边 ,定义

定义 ,构造关联矩阵:

容易发现 ,定义 删去第一行得到 ,则 。代入 Cauchy-Binet 公式得到:

的组合意义是对点 ,分别选一条 中的边,且每条边都恰好被选一次。若 选择了 ,就看做有向边 ,所以也相当于给 中的边定向,使得 的出度为

对于存在环的方案,构造对合映射(满足 的映射 ):取环上点编号最小值最小的环(容易发现环的点不交,所以这样的环唯一),将这个环上的边反向。

若环长为奇数,则排列奇偶性不变,关联矩阵中系数符号变化了奇数个;若环长为偶数,则排列奇偶性改变,关联矩阵中系数符号变化了偶数个。所以贡献值相反,出现环的权值都被两两抵消,对行列值没有贡献。

于是只用考虑不存在环的情况,此时有向图只能是以 为根的内向树,此时定向方案唯一(确定了边集和根),也就是每个点选择的出边都唯一,所以 即为该树的边权积,求和就得到

性质 2 设 Laplace 矩阵的特征值为 ,则

证明:因为 ,所以 是半正定矩阵,特征值都非负。而 ,所以必定有

定义 - 生成森林 是图的一个生成子图 ,使得这个子图有 个连通分量且无环。

定理 2 定义 表示无向图 - 生成森林的集合, 表示森林 的每个连通分量的点数之积, 的特征多项式为 ,则有

证明:考虑 ,枚举排列行列式时,贡献到 相当于选择相同编号的 列删去,这些就是每个连通分量的根,其他点选择出边连到这些根(类似定理 1 的证明), 表示将负号去掉。

推论 是生成树个数的 倍。

定理 3 内向生成树计数(见上)

证明:发现定理 1 的证明中用到了两个关联矩阵,于是我们考虑使用两个不同的关联矩阵 承担不同的功能。

与定理 1 中不同的是,关联矩阵 限制了只有边的起点能选择这条边,剩下的讨论均与定理 1 相同。

例题

例题 1:「HEOI2015」小 Z 的房间

矩阵树定理的裸题。将每个空房间看作一个结点,根据输入的信息建图,得到 Laplace 矩阵后,任意删掉 的第 行第 列,求这个子式的行列式即可。求行列式的方法就是高斯消元成上三角阵然后算对角线积。另外本题需要在模 的整数子环 上进行高斯消元,采用辗转相除法即可。

例题 2:「FJOI2007」轮状病毒

本题的解法很多,这里用矩阵树定理是最直接的解法。当输入为 时,容易写出其 阶的 Laplace 矩阵为:

求出它的 阶子式的行列式即可,剩下的只有高精度计算了。

例题 2+

将例题 2 的数据加强,要求 ,但是答案对 1000007 取模。(本题求解需要一些线性代数知识)

推导递推式后利用矩阵快速幂即可求得。

推导递推式的过程:

注意到 删掉第 1 行第 1 列以后得到的矩阵很有规律,因此其实就是在求矩阵

的行列式。对 的行列式按第一列展开,得到

上述三个矩阵的行列式记为
注意到 是三对角行列式,采用类似的展开的方法可以得到 具有递推公式 。类似地,采用展开的方法可以得到 ,以及
将这些递推公式代入上式,得到:

于是猜测 也是非齐次的二阶线性递推。采用待定系数法可以得到最终的递推公式为

改写成 后,采用矩阵快速幂即可求出答案。

例题 3:「BZOJ3659」WHICH DREAMED IT

本题是 BEST 定理的直接应用,但是要注意,由于题目规定“两种完成任务的方式算作不同当且仅当使用钥匙的顺序不同”,对每个欧拉回路,1 号房间可以沿着任意一条出边出发,从而答案还要乘以 1 号房间的出度。

例题 4:「联合省选 2020 A」作业题

首先需要用莫比乌斯反演转化成计算所有生成树的边权和,因为与本文关系不大所以略去。

将行列式的项写成 ,最后答案是行列式的一次项系数,因为答案实际上是钦定一条边之后的生成树个数 这条边的边权之和,那么被乘上一次项系数的边就是被钦定的边。此时可以把高于一次的项忽略掉,复杂度

「北京省选集训 2019」生成树计数 是较为一般化的情况:计算生成树权值之和的 次方之和,用类似方法构造行列式的项即可,具体见洛谷题解。

例题 5:AGC051D C4

无向图欧拉回路计数是 NPC 问题,但这题的图较为简单,确定了 的边中从 指向 的有多少条,就可以确定其他三条边的定向方案,然后直接套用 BEST 定理就得到 的做法。

注释

根向树形图也被称为内向树形图,但因为计算内向树形图用的是出度,为了不引起 in 和 out 的混淆,所以采用了根向这一说法。