矩阵树定理

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 相同。

例题

注释

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