矩阵树定理

Pengzt · 2025-02-06 17:27:41 · 个人记录

luogu & cnblogs

矩阵树定理

给定带权无向图 G，求出 \sum_T\prod_{e \in T}w_e 的值。

定义

定义 [n] = \{1, 2, 3, \cdots, n\}
对于无向图，定义 D(G) 为其度数矩阵，有：D(G)_{ij} = \left\{\begin{matrix} \deg_i & i = j \\ 0 & i \ne j \end{matrix}\right..
对于有向图，定义 D^{\text{in}}(G) 和 D^{\text{out}}(G) 分别表示其入度矩阵和出度矩阵，有：D^{\text{in}}(G)_{ij} = \left\{\begin{matrix} \deg^{\text{in}}_i & i = j \\ 0 & i \ne j \end{matrix}\right., D^{\text{out}}(G)_{ij} = \left\{\begin{matrix} \deg^{\text{out}}_i & i = j \\ 0 & i \ne j \end{matrix}\right..
定义 A(G) 为图的邻接矩阵。A(G)_{ij} 表示 i 连向 j 的边的数量。
定义无向图的 Laplace 矩阵 L 为 L(G) = D(G) - A(G)。有向图的情况可以类似的定义 L^{\text{in}} 和 L^{\text{out}}.
定义图 G 以 u 为根的根向树和叶向树的数量分别为 t^{\text{root}}(G, u) 和 t^{\text{leaf}}(G, u)。
定义矩阵 A 的子矩阵 A_{S, T} 为选取 i \in S，j \in T 构成的元素。
定义有向图 G 的关联矩阵为 M(G)（无向图可以随便定方向），有 M^{\text{in}}(G)_{ij} = \left\{\begin{matrix} \sqrt{w(e_j)} & \text{i is the starting point of edge j} \\ 0 & \text{otherwise.} \end{matrix}\right., M^{\text{out}}(G)_{ij} = \left\{\begin{matrix} \sqrt{w(e_j)} & \text{i is the end of edge j} \\ 0 & \text{otherwise.} \end{matrix}\right.，令 M(G) = M^{\text{in}}(G) - M^{\text{out}}(G)。

不难发现

D^{\text{in}} = M^{\text{in}} \cdot (M^{\text{in}})^T, D^{\text{out}} = M^{\text{out}}\cdot (M^{\text{out}})^T, A(G) = M^{\text{in}} \cdot (M^{\text{out}})^T.

进而有

L^{\text{in}}(G) = M^{\text{in}} \cdot (M^{\text{in}} - M^{\text{out}})^T, L^{\text{out}}(G) = (M^{\text{out}} - M^{\text{in}}) \cdot (M^{\text{out}})^T.

对于无向图有

L(G) = M \cdot M^T

定理

对于无向图 G 和任意的 k，有 t(G) = \det L(G)_{[n] \setminus \{k\}, [n] \setminus \{k\}}
对于有向图 G 和根 u，有 t^{\text{root}}(G) = \det L^{\text{out}}(G)_{[n] \setminus \{u\}, [n] \setminus \{u\}}，t^{\text{leaf}}(G) = \det L^{\text{in}}(G)_{[n] \setminus \{u\}, [n] \setminus \{u\}}

证明

引理 1（Cauthy-Binet）：

对于 n \times m 的矩阵 A 和 m \times n 的矩阵 B，有
\det(AB) = \sum\limits_{S \subseteq \{1, 2, \cdots, m\} \land |S| = n}\det A_{[n], S} \cdot \det B_{S, [n]}
如果 n > m，则必有 \det(AB) = 0。

证明咕了。

引理 2：

对于图 G 的子图 (V', E')，若 |E'| \le |V'|，则子图 T 是一棵以 V \setminus V' 为根的根向生成树当且仅当
\det(M_{V', E'}^{\text{out}}) \det(M_{V', E'}^{\text{out}} - M_{V', E'}^{\text{in}}) \ne 0
且该式的值在不为 0 时，恰好为 \prod_{e \in E'} w_e。

证明：

记 w(T) = \prod_{e \in T} w_e。先把行列式中每行的 \sqrt{w_e} 提出来，最后的答案再乘上一个 w(E') 就行了。

先考虑第一个行列式。如果 M_{V', E'}^{\text{out}} 存在某行全是 0（该点集中存在点没有在边集中出现），那么 \det(M_{V', E'}^{\text{out}}) 就是 0。然后又由于每条边只有一个出点，所以每行恰好有一个 1。所以这个式子保证了就有 |V'| = |E'|，但是没有保证 T 是一棵根向生成树。

现在考虑第二个行列式：M_{V', E'}^{\text{out}} - M_{V', E'}^{\text{in}}。这个矩阵中每行只有一个 1，零个或一个 -1。若 T 中存在环，这些边为 e_1 \to e_2 \to \cdots \to e_m。则行列式会长成形如这样的东西：

\begin{bmatrix} 0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & \cdots \\ 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & \cdots \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & \cdots \\ 0 & -1 & 0 & 0 & 0 & 0 & 0 & 1 & \cdots \\ -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{bmatrix}

记从第 i 行的 -1 处进入点 i，+1 处离开点 i。回顾消元求解行列式的过程，最后一定会消出一行 0。不存在环，那么就可以从叶子处开始消（叶子的那一行有且仅有一个 1，其余的都是 0），可以把它的父亲所在行的 -1 消掉。最后消出来的结果其实就是 \det(M_{V', E'}^{\text{out}})。

所以当且仅当 T 是一棵以 V \setminus V' 为根的根向生成树时 \det(M_{V', E'}^{\text{out}}) \det(M_{V', E'}^{\text{out}} - M_{V', E'}^{\text{in}}) = \det(M_{V', E'}^{\text{out}})^2 = w(T) \ne 0。

\square

根据刚刚的证明，有更通用的结论：

\sum\limits_{T \in \tau(G, u)} \prod_{e \in T} w_e = \det L^{\text{out}}(G)_{[n]\setminus \{u\}, [n] \setminus \{u\}}

这里的 \tau(G, u) 表示图 G 以 u 为根的根向生成树集合。

时间复杂度是求行列式的 \mathcal{O}(n^3)。

例题先咕了。