线代入门/Matrix-tree定理/LGV引理/Best定理

我之前写的是什么玩意啊。。

主要还是为了证明 Matrix-tree 定理和之后的东西所以没用到的就不写了。

## 矩阵之前

先证明几个小引理吧：

定义：$\lambda(p)$ 为排列 $p$ 中的逆序对数，$p'$ 为一个排列，且满足对于任意 $i\in[1,n]$ ，有 $p'_{p_i}=i$ 。

**Lamma 0.1**

$\lambda (p')=\lambda (p)$

证明：不妨考虑设数对 $(i,p_i)$ 为 $(a_i,b_i)$ ，则对 $p$ 求逆序对等价于对 $a$ 排序后对 $b$ 求逆序对，对 $p'$ 求逆序对等价于对 $b$ 排序对 $a$ 求逆序对，没有本质区别。

**Lamma 0.2**

交换排列中的两个元素，逆序对奇偶性一定改变。

证明：交换两个相邻元素逆序对奇偶性一定改变。设这两个元素的位置为 $x,y$ ，则交换次数为 $(y-x)+(y-x-1)=2(y-x)-1$ 次，奇偶性一定改变。

## 矩阵

我们对一个 $n*n$ 的方阵 $A$ ，定义其行列式的值为：$det(A)=\displaystyle\sum_p -1^{\lambda(p)} \prod_{i=1}^n a_{i,p_i}$ ，其中 $p$ 为一个排列。

矩阵转置：就是令 $A_{i,j}=A_{j,i}$ ，记作 $A^T$。

然后是一些性质：

1. 方阵转置后行列式值不变。

由 **Lamma 0.1** 即可简单证明。

2. 行列式某一行的倍数可以直接提到值的外面。

直接带式子，对于每一种排列中每一行都会且只会在乘积中出现一个元素。

3. 可以将行列式某一行拆成两个部分再求和，行列式的值不变。

就是把那一行需要乘的东西分两次乘完了。

4. 交换行列式的两行，行列式值取相反数。

由 **Lamma 0.2** 即可简单证明。

5. 如果两行成比例，则行列式值为 $0$ 。

先把比例提出来，然后两行两行相等交换行列式不变，但是行列式的值取相反数，所以行列式的值只能为 $0$ 。

6. 将某一行加到另一行上，行列式值不变。

利用性质3，把加的拆出来，则存在两行相同行列式值为 $0$ 。

7. 对行满足的性质对列也满足。

因为转置不影响行列式的值。

## Matrix-tree 定理

先证明无向图，有向图先咕着。

定义：$D$ 为度数矩阵，$A$ 为邻接矩阵，$L$ 为 Laplacian matrix ，即 $D-A$ 。

再定义：$M$ 为关联矩阵。

$$
M(i, j) = 
\begin{cases}
1 & (\text{i is the end of the } edge_j) \\
-1 & (\text{i is the start of the } edge_j) \\
0 & (\text{Otherwise}) \\
\end{cases}
$$

$M_0$ 为把 $M$ 删掉最后一行的矩阵（我们只考虑删去最后一行的情况，其他的也同理）

然后引理开始：

**Lamma 1.1**

$MM^T=L$

证明：

$MM^T(i,j)=\displaystyle\sum_{k=1}^n M(i,k)*M^T(k,j)$

$=\displaystyle\sum_{k=1}^n M(i,k)*M(j,k)$

当 $i=j$ 时，贡献为 $d_i$ 。

当 $i \neq j$ 时，贡献为 $-a_{i,j}$ 。

**Lamma 1.2**

令 $S$ 是边集 $E$ 的一个子集，且 $|E|=n-1$ ，若 $S$ 构成一棵生成树，则 $det M_0[S] = \pm 1$  ，否则为 $0$ 。

此处的 $M_0[S]$ 相当于把边集 $S$ 中的边对应的列单独抽出来形成的一个方阵。

先证明后面的。

如果存在一个环，那把原矩阵转置一下在环上的行相加后一定能表示出来某一个，那么矩阵中就有两个相同行，所以行列式的值为 $0$ 。

然后前面的。

我们每次选择一个叶子节点，用它取去消除和相连的那条边对应的点。

做完后主对角线上的点值一定是 $\pm 1$ ，考虑证明。

首先可以通过每次重排序来选择叶子节点，容易想到这样只会影响正负号而不会影响绝对值。

然后考虑删去叶子节点的过程，此时叶子只连了一条边，所以只有主对角线上的点为 $-1$ ，所以这时候把它加到其父亲上没有影响。

**Binet-Cauchy Theorem**

定义大小分别为 $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])$$

线代里面的定理，~~不想证了~~ 有空回来证一下。

**Matrix-tree Theorem**

我们设 $L_0$ 表示  $L$ 删去 $n$ 行 $n$ 列后的矩阵。

由 **Lamma 1.1** 可以知道 $K_0=M_0*M^T_0$

由 **Binet-Cauchy Theorem** 可得：

$det(K_0)=\displaystyle\sum_{S} det(M_0[S])det(M_0^T[S])=\sum_{S} det^2(M_0[S])$

然后由 **Lamma 1.2** 可得当 $M_0$ 是生成树时 $det^2(M_0[S])$ 为 $1$ ，否则为 $0$ ，所以 $det(K_0)$ 就是原图的生成树数量。

**有向图的情况**

以外向树为例，内向树同理。

我们考虑对于外向树关联矩阵的构成，一定是叶子节点对应边为 $1$ ，然后对应的父亲为 $-1$ ，容易证明当 $S$ 是一棵外向树时， $det(M_0[S])=1$ ，但需要注意的是此时我们只能保证构成了一棵树（而不是一棵外向树

需要注意的是，此处 $M_0$ 是将根对应的行列去掉（因为相当于按拓扑序消元）

考虑设矩阵 $K$ ，用它去限制外向树，则此时还需保证每个点有且仅有一条入边，所以此时的 $K$ 为。
$$
K_{i,j} = \begin{cases}
1 &  i \ is \ the \ end \ of\ the\ edge_j \\
0 & \textit{otherwise.} \\
\end{cases}
$$

容易证明当 $S$ 是一棵树时，$det(K_0^T[S])=1$

$K_0$ 也是去掉根对应的行列。

此时 $L$ 的定义也随之发现变化，度数矩阵 $D$ 变成了入度矩阵。

然后可以仿照上文证明  **Lamma 1.1** 的方式证明出 $MK^T=L$

然后就和上面的证明一样了。

内向树也同理。

## LGV 引理
先咕咕了反正下面不用。

## BEST 定理

设：一个有向图 $G$ 的欧拉回路个数为 $F(G)$ ，内向生成树个数为 $T(G)$ ，每个点的入度为 $d_i$ ，则有：$F(G)=T(G)\displaystyle\prod_{i=1}^n(d_i-1)!$

感性理解下，保留每一个点的最后一条出边，那么在每一棵内向生成树中其他边任取即可，对于根节点需要固定第一条边不然会算重，所以就是 $\prod(d_i-1)!$

记得特判是否存在欧拉路径（每个点入度出度是否相同）以及把所有孤立点（即没有边的点）去掉。

正在渲染内容...