矩阵树定理 Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。
本篇记号声明 本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。
无向图情况 设 G n D(G)
D_{ii}(G) = \mathrm{deg}(i), D_{ij} = 0, i\neq j 设 \#e(i,j) i j A
A_{ij}(G)=A_{ji}(G)=\#e(i,j), i\neq j 定义 Laplace 矩阵（亦称 Kirchhoff 矩阵） L
记图 G t(G)
有向图情况 设 G n D^{out}(G)
D^{out}_{ii}(G) = \mathrm{deg^{out}}(i), D^{out}_{ij} = 0, i\neq j 类似地定义入度矩阵 D^{in}(G)
设 \#e(i,j) i j A
A_{ij}(G)=\#e(i,j), i\neq j 定义出度 Laplace 矩阵 L^{out}
L^{out}(G) = D^{out}(G) - A(G) 定义入度 Laplace 矩阵 L^{in}
L^{in}(G) = D^{in}(G) - A(G) 记图 G r t^{root}(G,r)
记图 G r t^{leaf}(G,r)
定理叙述 矩阵树定理具有多种形式。其中用得较多的是定理 1、定理 3 与定理 4。
定理 1（矩阵树定理，无向图行列式形式） 对于任意的 i
t(G) = \det L(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n} 其中记号 L(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n} L(G) 1,\cdots,i-1,i+1,\cdots,n 1,\cdots,i-1,i+1,\cdots,n n-1
定理 2（矩阵树定理，无向图特征值形式） 设 \lambda_1, \lambda_2, \cdots, \lambda_{n-1} L(G) n - 1
t(G) = \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}
定理 3（矩阵树定理，有向图根向形式） 对于任意的 k
t^{root}(G,k) = \det L^{out}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n} 因此如果要统计一张图所有的根向树形图，只要枚举所有的根 k t^{root}(G,k)
定理 4（矩阵树定理，有向图叶向形式） 对于任意的 k
t^{leaf}(G,k) = \det L^{in}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n} 因此如果要统计一张图所有的叶向树形图，只要枚举所有的根 k t^{leaf}(G,k)
BEST 定理 定理 5 (BEST 定理） 设 G G ec(G)
ec(G) = t^{root}(G,k)\prod_{v\in V}(\deg (v) - 1)! 注意，对欧拉图 G k, k' t^{root}(G,k)=t^{root}(G,k') G
例题 「HEOI2015」小 Z 的房间 解 矩阵树定理的裸题。将每个空房间看作一个结点，根据输入的信息建图，得到 Laplace 矩阵后，任意删掉 L i i k \mathbb{Z}_k
「FJOI2007」轮状病毒 解 本题的解法很多，这里用矩阵树定理是最直接的解法。当输入为 n n+1
L_n = \begin{bmatrix} n& -1& -1& -1& \cdots& -1& -1\\ -1& 3& -1& 0& \cdots& 0& -1\\ -1& -1& 3& -1& \cdots& 0& 0\\ -1& 0& -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ -1& 0& 0& 0& \cdots& 3& -1\\ -1& -1& 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n+1} 求出它的 n
例题 2+ 将例题 2 的数据加强，要求 n\leq 100000
解 推导递推式后利用矩阵快速幂即可求得。
推导递推式的过程。警告：过程冗杂 注意到 L_n
M_n = \begin{bmatrix} 3& -1& 0& \cdots& 0& -1\\ -1& 3& -1& \cdots& 0& 0\\ 0& -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& 0& \cdots& 3& -1\\ -1& 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n} 的行列式。对 M_n
\det M_n = 3\det \begin{bmatrix} 3& -1& \cdots& 0& 0\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n-1} + \det\begin{bmatrix} -1& 0& \cdots& 0& -1\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ 0& 0& \cdots& -1& 3\\ \end{bmatrix}_{n-1} + (-1)^n \det\begin{bmatrix} -1& 0& \cdots& 0& -1\\ 3& -1& \cdots& 0& 0\\ -1& 3& \cdots& 0& 0\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ 0& 0& \cdots& 3& -1\\ \end{bmatrix}_{n-1} 上述三个矩阵的行列式记为 d_{n-1}, a_{n-1}, b_{n-1} d_n d_n d_n=3d_{n-1}-d_{n-2} a_{n-1}=-d_{n-2}-1 (-1)^n b_{n-1}=-d_{n-2}-1
\det M_n = 3d_{n-1}-2d_{n-2}-2 于是猜测 \det M_n
\det M_n = 3\det M_{n-1} - \det M_{n-2} + 2 改写成 (\det M_n+2) = 3(\det M_{n-1}+2) - (\det M_{n-2} + 2)
例题 3 「BZOJ3659」WHICH DREAMED IT
解 本题是 BEST 定理的直接应用，但是要注意，由于题目规定“两种完成任务的方式算作不同当且仅当使用钥匙的顺序不同”，对每个欧拉回路，1 号房间可以沿着任意一条出边出发，从而答案还要乘以 1 号房间的出度。
注释 根向树形图也被称为内向树形图，但因为计算内向树形图用的是出度，为了不引起 in 和 out 的混淆，所以采用了根向这一说法。
build Last update and/or translate time of this articleCheck the history edit Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github people Contributor of this article pw384, s0cks5, Xeonacid translate Translator of this article Visit the original article! copyright The article is available under CC BY-SA 4.0 & SATA