往上貌似证明的资料比较少而且不全，于是就来 水一篇博客。
定义
- 对于无向图，定义 \(D(G)\) 为图 \(G\) 的度数矩阵，其中：
- 对于有向图，定义 \(D ^ {in}(G)\) 为图 \(G\) 的入度矩阵，\(D ^ {out}(G)\) 为图 \(G\) 的出度矩阵，其中：
- 定义 \(A(G)\) 为图 \(G\) 的邻接矩阵，其中：
-
定义图 \(G\) 的 \(\rm kirchhoff\) 矩阵 \(K(G) = D(G) - A(G)\)。
-
定义无向图 \(G\) 的生成树数量为 \(t(G)\)，有向图根向树生成树（根为 \(u\)，下同）数量为 \(t ^ {root}(G, u)\)，有向图叶向树数量为 \(t ^ {leaf}(G, u)\)。
-
定义图 \(G\) 的关联矩阵 \(M(G)\) 为一个大小为 \(n \times m\) 的矩阵，其中（一下的方向对于无向图随意）：
-
定义图 \(G\) 的减关联矩阵 \(M_0(G)\) 为关联矩阵 \(M(G)\) 去掉最后一行后的大小为 \((n - 1) \times m\) 的矩阵。
-
定义图 \(G\) 的子减关联矩阵 \(M_0(G)[S]\) 为选出 \(M_0(G)\) 中的列构成子集 \(S\)，满足 \(|S| = n - 1, S \subseteq {1, 2, \cdots m}\)。
定理
以下默认所有数均为正整数。
- 无向图矩阵树定理：
- 有向图矩阵树定理：
- \(\rm Best\) 定理：设有向欧拉图 \(G\) 的欧拉回路数量为 \(ec(G)\)，则有：
其中对于欧拉图 \(\mathrm{in}, \mathrm{out}\) 均相同，因此 \(\deg\) 可任选其一。
若要求欧拉回路起点 \(k\)，则以 \(k\) 为起点的欧拉回路数量 \(ec(G, k)\) 为：
\[ec(G, k) = t ^ {root}(G, k) \deg_k \prod\limits_{u \in V} (\deg_u - 1)! \]此定理下面暂不证明，先咕着。
证明
以下只证明无向图无根树生成树矩阵树定理。
- 引理 \(1\)：
可以发现当且仅当 \(i, j\) 都为边 \(k\) 的一个端点时，贡献不为 \(0\)。
若 \(i = j\) 则 \(M(i, k) = M(j, k)\) 贡献相等，那么两者乘积贡献 \(1\)。因此总贡献为 \(\deg_i\)。
若 \(i \ne j\) 则 \(M(i, k) \ne M(j, k)\) 贡献相反，那么两者乘积贡献 \(-1\)。因此总贡献为 \(-A(i, j)\)。
于是有引理 \(1\) 成立。
- 引理 \(2\)：
若 \(S\) 构成的边集在原图上构成生成树，那么 \(\det M_0[S] = 1 / -1\) 否则 \(\det M_0[S] = 0\)。
先证后者：
若原图没有构成树，那么至少存在一个简单环 \(C(e_{i_1}, e_{i_2}, \cdots e_{i_k})\)，记 \(e_{{i_j}_u}, e_{{i_j}_v}\) 分别为边 \(e_{i_j}\) 的两个端点。
同时，对于 \(M_0[S]\) 有如下两点观察：
-
对于同一行，恰好存在两列非 \(0\)。
-
对于同一列，恰好存在两行一行为 \(1\) 一行为 \(-1\)。（若为最后一行也可视作出现）
下面证明 \(M_0[S]\) 对应原 \(M_0\) 的 \(i_1, i_2, \cdots i_k\) 列线性相关，考虑依次合并所有列：
我们首先拿第 \(i_1\) 列消 \(i_2\) 列，因为简单环上两边共点，因此至少存在一行使得两列上均非 \(0\)，我们消掉这一行后根据观察 \(2\) 必恰好仅有 \(e_{{i_1}_u}, e_{{i_2}_v}\) 这两行一行为 \(1\) 一行为 \(-1\)。
假设合并到第 \(i_j\) 列，若 \(j \ne k\) 那么使用 \(i_{j - 1}\) 列合并的结果同第一列消第二列的方式消掉第 \(i_j\) 列，于是第 \(i_j\) 列消完后必恰好在 \(e_{{i_1}_u}, e_{{i_j}_v}\) 这两行一行为 \(1\) 一行为 \(-1\)。
最后合并到第 \(i_{k - 1}\) 列时，此时非 \(0\) 两行与原 \(i_k\) 列未消时一致，故此时可以将第 \(i_k\) 列消为全 \(0\)。
因此这 \(i_1, i_2, \cdots i_k\) 列线性相关，\(\det M_0[S] = 0\)。
再证前者：
考虑将原行列式消成好算的形式，类似于高斯消元的方式，我们钦定一行的主元拿此行去消所有行。
具体地，若 \(S\) 构成的边集为一棵树，那么必定能找到叶子节点 \(u\)，此时选出 \(u\) 所在的行，必定恰好只存在一列非 \(0\)，拿此列去消所有行（事实上只能消掉边的另一个节点所对应的行）。
可以发现这等价于每次在 \(M_0[S]\) 中删去树上叶子节点所对应的一条边，故此过程一定可以不断递归直至消去所有边。
最后我们发现，每一行都只剩下恰好一列为其做为叶子时所对应列为 \(1 / -1\)，故此时行列式值仅在每行选这些列时非 \(0\)，不论逆序对数量，所得行列式值均为 \(1 / -1\)。
- 引理 \(3\)（\(\rm Binet - Cauchy\) 定理）：
定义大小分别为 \(n \times m, m \times n(n \le m)\) 的矩阵 \(A, B\) 则有：
\[\det(AB) = \sum\limits_{S \subseteq \{1, 2, \cdots m\}, |S| = n} \det(A[S]) \times \det(B[S]) \]其中 \(A[S], B[S]\) 分别表示 \(A\) 取 \(S\) 集合内的列，\(B\) 取 \(S\) 集合内的行所构成的矩阵。
证明引理 \(3\) 之前再给出两条引理：
定义 \(\lambda(P)\) 为排列 \(P\) 的逆序对数量。
-
- 引理 \(1\)：
-
定义 \(P'\) 为 \(P\) 的逆排列，即满足 \(P'_{P_i} = i\)，那么有：
\(\quad\) 不妨转化 \(P'\) 的逆序对求法，不难发现等价于给定序列 \(A\)，每个元素存在两个关键字 \(x, y\)，其中 \(A_{i_x} = p_i, A_{i_y} = i\)。
\(\quad\) 那么 \(\lambda(P')\) 等价于将将序列 \(A\) 按照第一关键字排序后以第二关键字为权值的逆序对数量。
\(\quad\) 在这里等价于按照权值排序后求下标的逆序对，这与直接求原排列的逆序对是等价的。
-
- 引理 \(2\)：
-
定义 \(P_{Q}\) 为排列 \(Q\) 与排列 \(P\) 的复合，则 \(\lambda(P_{Q})\) 与 \(\lambda(P) + \lambda(Q)\) 的奇偶性相同。
\(\quad\) 仿照引理 \(1\) 的证明方法，那么左式等价去求给定序列 \(A\)，每个元素存在两个关键字 \(x, y\) 其中 \(A_{i_x} = P_i, A_{i_y} = Q'_i\)，
\(\quad\) 那么 \(\lambda(P_Q)\) 等价于按照第一关键字排序后以第二关键字为权值的逆序对数量。
\(\quad\) 考虑调整证明，可知一开始的逆序对数量为 \(\lambda(Q') = \lambda(Q)\)，排序利用冒泡排序的过程，可知有效的交换仅有 \(P\) 的逆序对个。
\(\quad\) 而我们知道每交换排列里两个元素排列逆序对数奇偶性改变，故总共改变 \(\lambda(P)\) 次，所以 \(\lambda(P_Q)\) 与 \(\lambda(P) + \lambda(Q)\) 奇偶性相同。
首先我们展开等式右侧：
\[\begin{aligned} & \sum\limits_{S \subseteq \{1, 2, \cdots m\}, |S| = n} \det(A[S]) \times \det(B[S]) \\ &= \sum\limits_{S \subseteq \{1, 2, \cdots m\}, |S| = n} \left(\sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, S_{P_i}}\right) \times \left(\sum\limits_{Q} (-1) ^ {\lambda(Q)} \prod\limits_{i = 1} ^ n B_{S_i, Q_i}\right) \\ &= \sum\limits_{S} \sum\limits_{P} \sum\limits_{Q} (-1) ^ {\lambda(P) + \lambda(Q)} \prod\limits_{i = 1} ^ n A_{i, S_{P_i}} \times B_{S_i, Q_i} \\ \end{aligned} \]再展开等式左侧：
\[\begin{aligned} & \det(AB) \\ &= \sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n \left(\sum\limits_{j = 1} ^ m A_{i, j} \times B_{j, P_i}\right) \\ &= \sum\limits_{P} (-1) ^ {\lambda(P)} \sum\limits_{R} \left(\prod\limits_{i = 1} ^ n A_{i, R_i} \times B_{R_i, P_i}\right) (|R| = n, \forall i, R_i \in \{1, 2, \cdots m\}) \\ &= \sum\limits_{R} \sum\limits_{P} (-1) ^ {\lambda(P)} \left(\prod\limits_{i = 1} ^ n A_{i, R_i}\right) \times \left(\prod\limits_{i = 1} ^ n B_{R_i, P_i}\right) \end{aligned} \]仔细观察可知，对于可重排列 \(R\)，若 \(\exist i < j, R_i = R_j\) 那么交换 \(P_i, P_j\) 后后面的积式不变，但逆序对奇偶性改变，因此两者贡献互为相反数可抵消。
因此我们只需钦定每个 \(\exist i < j, R_i = R_j\) 的可重排列 \(R\)，让其和交换满足条件的最小 \(P_i, P_j\) 交换后的排列 \(P\) 的贡献相抵即可。
因为交换最小的 \(i, j\) 后依然满足 \(i, j\) 为最小的满足条件的点对，因此可以两两唯一配对。
故我们只需枚举不重的序列即可，为此我们首先枚举 \(\{1, 2, \cdots m\}\) 的子集，然后枚举一个长度为 \(n\) 的排列 \(Q\)：
\[\begin{aligned} & \det(AB) \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, S_{Q_i}} \times B_{S_{Q_i}, P_i} \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P_{Q'}} (-1) ^ {\lambda(P_{Q'})} \left(\prod\limits_{i = 1} ^ n A_{i, S_{Q_i}}\right) \times \left(\prod\limits_{i = 1} ^ n B_{S_i, P_{Q'_i}}\right) \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P_{Q'}} (-1) ^ {\lambda(P) + \lambda(Q)} \left(\prod\limits_{i = 1} ^ n A_{i, S_{Q_i}}\right) \times \left(\prod\limits_{i = 1} ^ n B_{S_i, P_{Q'_i}}\right) \end{aligned} \]整理即可得到从右侧推导得到的式子。
下面我们只证明矩阵树定理删去最后一行最后一列是正确的（对于删去其余的情况，只需将 \(M_0\) 的定义修改成删去改行即可）。
类似于引理 \(1\)，我们知道 \(K_0 = M_0 \times M_0 ^ T\) 其中 \(K_0\) 为 \(K\) 去掉最后一行和最后一列得到的方阵。
再根据引理 \(3\)，可知：
\[\begin{aligned} \det K_0 &= \sum\limits_S \det(M_0[S]) \det(M_0 ^ T[S]) \\ &= \sum\limits_S \det{^ 2}(M_0[S]) \end{aligned} \]由定理 \(2\)，若边集 \(S\) 不构成生成树，则 \(\det(M_0[S]) = 0\)，在该式中贡献为 \(0\)。
若边集 \(S\) 构成生成树，则 \(\det(M_0[S]) = 1 / -1\)，在该式中贡献为 \(1\)。
故可得到 \(\det K_0\) 即为原图的生成树数量。