因为在临时抱佛脚，所以是没有证明的~

0. 前置芝士

0.1. 拉普拉斯展开

对于行列式 \(D\)，任意第 \(i\) 行（列同理）按下式展开的值与行列式值相等

\[\text{Value}=\sum_{j=1}^n (-1)^{i+j}\cdot a_{i,j}\cdot M_{i,j} \]

其中 \(M_{i,j}\) 是 \(a_{i,j}\) 的余子式。

---

一些闲话：这个可以用来推导 "轮状病毒" 一题中的递推式。

1. 矩阵树定理

1.1. 定理一

1.1.1. 内容

构造连通矩阵和度数矩阵。连通矩阵 \(A\) 的第 \(i\) 行第 \(j\) 列上的数字表示原无向图中 \(i,j\) 两点之间边的条数。度数矩阵 \(D\) 只有 \(D_{i,i}\) 有值表示点 \(i\) 的度数。定义 \(L=D-A\)，无向图生成树的个数就是 \(L\) 去掉任意行任意列的矩阵的行列式。

1.1.2. 应用

例 1. 求无向图所有生成树边权乘积的和。

将度数矩阵变成与点邻接边的边权和，连通矩阵变成边的权值再应用矩阵树定理即可。

例 2. 求无向图必选某一条边的所有生成树个数。

我是伞兵，这都不会。简单容斥即可。

例 3. 用生成函数描述限制：

例 4. \(\text{[SDOI 2014] }\)重建

题目要求

\[\begin{align} \text{Ans}&=\sum_{T(V,E')}\left(\prod_{e\in E'}p_e\cdot \prod_{e\in E\setminus E'}(1-p_e) \right)\\ &=\sum_{T(V,E')}\left(\prod_{e\in E'}p_e\cdot \frac{\prod_{e\in E}(1-p_e)}{\prod_{e\in E'}(1-p_e)} \right)\\\ &=\prod_{e\in E}(1-p_e)\cdot \sum_{T(V,E')}\left(\prod_{e\in E'}\frac{p_e}{1-p_e} \right) \end{align} \]

1.2. 定理二

1.2.1. 内容

给出有向图和其中的一个点，求以这个点为根的生成外向树个数（外向树满足每个点有且仅有一条入边）。

构造连通矩阵和度数矩阵。连通矩阵 \(A\) 的第 \(i\) 行第 \(j\) 列上的数字表示有向图中 \(i\rightarrow j\) 的边的条数。度数矩阵 \(D\) 只有 \(D_{i,i}\) 有值表示点 \(i\) 的 入度。定义 \(L=D-A\)，答案就是 \(L\) 去掉根所在的行和列的矩阵的行列式。

1.3. 定理三

1.3.1. 内容

给出有向图和其中的一个点，求以这个点为根的生成内向树个数。

构造连通矩阵和度数矩阵。连通矩阵 \(A\) 的第 \(i\) 行第 \(j\) 列上的数字表示有向图中 \(i\rightarrow j\) 的边的条数。度数矩阵 \(D\) 只有 \(D_{i,i}\) 有值表示点 \(i\) 的 出度。定义 \(L=D-A\)，答案就是 \(L\) 去掉根所在的行和列的矩阵的行列式。

2. \(\text{BEST}\) 定理

用于求解有向图欧拉回路的个数。

首先，如果存在某个点的入度和出度不相等，那么这张图不存在欧拉回路。否则，设 \(t(s)\) 为以 \(s\) 为根的内向树（或者外向树）个数，\(\text{deg}(s)\) 为 \(s\) 的出度（或者入度），所求即为

\[t(s)\cdot \prod_{v\in V}(\text{deg}(v)-1)! \]

需要注意的是，以任何一个点作为根最后都可以得出一样的答案。

如果要求从点 \(s\) 开始的欧拉回路个数呢？此时只能代入 \(t(s)\)，最后答案还要多乘上 \(\text{deg}(s)\).