luogu & cnblogs

矩阵树定理

定义

• 定义 $[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)$。

定理

• 对于无向图 $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$。