常见图上定理

矩阵树定理

• 感谢这篇文章对我更深层次理解矩阵树定理的帮助。

图的关联矩阵

对于一张无向图 $G=(V,E)$，定义其关联矩阵 $M$ 为（在此我们给边暂定方向，一条边 $e$ 的入点和出点分别为 $\text{in}(e)$ 和 $\text{out}(e)$）：

$$M_{i,j}=\begin{cases}1&V_i=\text{out}(E_j)\\-1&V_i=\text{in}(E_j)\\0&\text{otherwise.}\end{cases}$$

Laplacian Matrix

定义 $\text{cnt}(u,v)$ 表示无向图中边 $(u,v)$ 的数量，则图 $G=(V,E)$ 的 Laplacian Matrix $L$ 为

$$L_{i,j}=\begin{cases}\text{deg}(V_i)&i=j\\-\text{cnt}(V_i,V_j)&i\not=j\end{cases}$$

即为图的度数矩阵 $D$ 减去图的邻接矩阵 $E$，$E_{i,i}$ 同时等价于和 $i$ 相邻的边权之和。

其中有等式 $L=MM^T$，可以分讨 $i=j$ 和 $i\not= j$ 的关系来证明。

Cauchy-Binet Formula

令 $C_{n\times n}=A_{n\times m}B_{m\times n}$，$A[S]$ 表示选出 $A$ 所有 $\in S$ 的列构成的矩阵，$B[S]$ 表示选出 $B$ 所有 $\in S$ 的行构成的矩阵，则有：

$$\det(C)=\sum\limits_{S\subset\{1,\cdots,m\},|S|=n}\det(A[S])\det(B[S])$$

下面矩阵 $A$ 中选出所有 $\in S$ 的行 / 列构成的矩阵行列式统写为 $\det(A[S])$，因为 $\det(A)=\det(A^T)$。

证明略，详细可看 sys 博客。

无向图的 Matrix-Tree 定理

令 $L_0$ 为无向图的 Laplacian Matrix 去掉第 $k$ 行第 $k$ 列（$k$ 任意），则无向图的生成树个数为 $\det(L_0)$。**

证明

令 $M_0$ 表示 $L_0$ 对应的关联矩阵，则：

$$\begin{aligned}\det(L_0)&=\sum\limits_{S\subset\{1,\cdots,m\},|S|=n-1}\det(M_0[S])\det(M_0^T[S])\\&=\sum\limits_{S\subset\{1,\cdots,m\},|S|=n-1}\det(M_0[S])^2\end{aligned}$$

观察从 $M_0$ 中选 $\in S$ 的列向量构成的矩阵，相当于从 $m$ 条边里面选 $n-1$ 条边，且如果出现环矩阵应该是不满秩的，此时 $\det(M_0[S])^2=0$，否则我们可以类似高斯消元从叶子到根把矩阵消成每行每列只有一个元素，且为 $-1/1$，此时 $\det(M_0[S])^2=1$。

这里还有另一种简洁证法，不多阐述。

有向图的 Matrix-Tree 定理

令 $D_{\text{in}}$ 和 $D_{\text{out}}$ 分别为图 $G$ 的入度矩阵和出度矩阵，对应 $E_{\text{in}} / L_{\text{in}}$ 和 $E_{\text{out}} / L_{\text{out}}$，则：

• 以 $r$ 为根的叶向树个数为 $L_{\text{in}}$ 去掉第 $r$ 行第 $r$ 列后的行列式。
• 以 $r$ 为根的根向树个数为 $L_{\text{out}}$ 去掉第 $r$ 行第 $r$ 列后的行列式。

证明比较相似，分别证明 $L_{\text{in}}=MD_{\text{in}}^T$，然后 $\det(M)$ 限制树无环，$\det(D_{\text{in}})$ 限制除 $r$ 恰好都有一条入边，$\text{out}$ 同理。

带权图的 Matrix-Tree 定理

把权值看成重边即可。

BEST 定理

令一个有向图 $G=(V,E)$ 的根向生成树为 $\mathcal T_{\text{out}}(G)$，则若此图为欧拉图，则 $s$ 出发并从 $s$ 结束的欧拉回路条数为 $d\mathcal T_{\text{out}}(G)\prod\limits_{u\in V}(\text{deg}(u)-1)$。其中当循环同构算一种方案时，$d=1$，否则 $d=\text{deg}(s)$。

证明

以下证明基于 $d=\text{deg}(s)$。

式子的意思即为我们在原图中钦定每个点最后走的边作为根向树（除了 $s$），其他的边任意排列，我们只要证明这两者是双射关系。

• 根向树对应欧拉回路

考虑这样的走法：从根节点开始按顺序走，只有当前节点 $u$ 除了 $(u,fa_u)$ 的边都被走过了，再走这条边。

考虑是否能保证每条边都被走过。

如果走到 $u\not = rt$ 走不下去了，根据欧拉图定义，这种情况不可能存在。

如果走到 $u=rt$ 走不下去了，则存在一条内向树边未走，则这条边到根的所有边都未走，根据欧拉图定义可以退出根节点有至少一条出边未走，矛盾。

• 欧拉回路对应根向树

我们提出欧拉路中每个点最后走的出边（除了 $s$），一定是根向树。如果出现了环，说明一个点绕了一圈，但是走不出去了，不满足欧拉回路的性质。

故双射关系得证。

Prufer 序列

$n$ 个点构成的无根树个数为 $n^{n-2}$。

Cayley 定理：$n$ 个点，连接 $k$ 个大小分别为 $a_1,a_2,\cdots,a_k$ 的树，方案数为 $n^{k-2}\prod a_i$，证明如下：

容易得到其 Laplacian 矩阵去掉 $k$ 行 & 列的行列式如下：

$$\begin{vmatrix} a_1(n-a_1) & -a_2a_1 & \cdots & -a_1a_{k-1} \\ -a_2a_1 & a_2(n-a_2) & \cdots & -a_2a_{k-1}\\ \vdots & \vdots& \ddots & \vdots\\ -a_{k-1}a_1 & -a_{k-1}a_2 &\cdots & a_{k-1}(n-a_{k-1}) \end{vmatrix}$$

提个系数，并把 $2\sim k-1$ 列加到第一列得到：

$$\prod\limits_{i=1}^{k-1}a_i\begin{vmatrix} a_k & -a_2 & \cdots & -a_{k-1} \\ a_k & n-a_2 & \cdots & -a_{k-1}\\ \vdots & \vdots& \ddots & \vdots\\ a_k & -a_2 &\cdots & n-a_{k-1} \end{vmatrix}$$

最后把所有行都减去第一列：

$$\prod\limits_{i=1}^{k-1}a_i\begin{vmatrix} a_k & -a_2 & \cdots & -a_{k-1} \\ 0 & n & \cdots & 0\\ \vdots & \vdots& \ddots & \vdots\\ 0 & 0 &\cdots & n \end{vmatrix}$$

答案为 $n^{k-2}\prod\limits_{i=1}^ka_i$。

LGV 引理

对于一个 $n$ 个点的有向无环图，令 $w(P)$ 表示路径 $P$ 上所有边边权乘积，令 $e(u,v)$ 表示所有 $u\rightsquigarrow v$ 的路径 $P$ 的 $w(P)$ 之和。给定起点序列 $a$ 和终点序列 $b$，令

$$M=\begin{bmatrix} e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_n)\\ e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_n)\\ \vdots & \vdots & \ddots & \vdots\\ e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_n) \end{bmatrix}$$

LGV 引理声称（其中 $\text {sgn}(p)=(-1)^{\pi(p)}$，$\pi(p)$ 为排列 $p$ 的逆序对个数）

$$\det(M)=\sum\limits_{S:a\rightsquigarrow b}\text{sgn}(S)\prod\limits_{P\in S}w(P)$$

即 $M$ 的行列式为所有 $a\rightsquigarrow b$ 的不交路径组的路径权值与 $\pmb{a,b}$ 置换 $\pmb{\text{sgn}}$ 之积（记住这里的定义）。

证明

$$\begin{aligned} \det(M)&=\sum\limits_{p}\text{sgn}(p)\prod\limits_{i=1}^ne(a_i,b_{p_i})\\ &=\sum\limits_{p}\text{sgn}(p)\prod\limits_{P\in p}w(P) \end{aligned}$$

上面分配律拆一下就是下面的式子，你发现除了不交的限制其他已经一样了，只要证明有交的路径组贡献为 $0$ 就好了。

对于每一对有交路径组，找到最小的编号 $i$ 使得 $a_i\rightsquigarrow b_{p_i}$ 这条路径和别的路径有交，有交的第一部分是 $u\rightsquigarrow v$，另一条有交的路径为 $x\rightsquigarrow y$。交换 $v\rightsquigarrow b_{p_i}$ 和 $v\rightsquigarrow y$，置换逆序对奇偶性改变，$\text{sgn}$ 正负性改变。而且容易发现有交路径组必定能两两对应。注意一下如果找到编号最小的二元组 $(i,j)$ 有交是错的，因为不构成双射。

听说边权上可以套 GF，等我学了再回来补。