526互联

【模板】图的计数相关：行列式及求值、Matrix-Tree 定理、BEST 定理、LGV 引理

发布时间 2023-07-21 19:34:28作者: caijianhong

归类为线性代数、图论。证明都是神仙，特别是名字带“理”的，不证了。

行列式

定义

行列式（Determinant）是对 \(n\) 阶方阵 \(A\) 定义的，是一个标量。\(A\) 的 \(n\) 阶行列式 \(det(A)\) 或 \(|A|\) 定义如下：

\[det(A)=\sum_p(-1)^{\mu(p)}\prod_{i}A[i][p_i]. \]

这里将排列的逆序对数定义为了 \(\mu(p)\)，\(p\) 是排列，枚举所有排列，每一行挑一个乘起来，拿逆序对相关的东西做系数。

排列奇偶性

Lemma 1. 对于排列 \(p\)，交换 \(p_i,p_j\)（其中 \(1\leq i,j\leq n,i\neq j\)），\(\mu(p)\) 的奇偶性改变。
Proof. 假设 \(i<j\)，令 \(l=j-i\)。先将 \(a_j\) 调至 \(a_i\) 前，考虑这一步操作的影响。原来 \(a_j\) 与 \(a_{[i,j)}\) 的组合，顺序对设为 \(a\) 个，逆序对设为 \(b\) 个，那么 \(a+b=l\)，现在将 \(a_j\) 调至 \(a_i\) 前，顺序对变为 \(b\) 个，逆序对变为 \(a\) 个，所以变化量 \(a-b\equiv a-b+2b\equiv a+b\equiv l\pmod 2\)。再将 \(a_i\) 调至原来 \(a_j\) 的位置，变化量与 \(l-1\) 同奇偶，那么总的变化量是 \(l+l-1\equiv 1\pmod 2\)。

行列式性质

Theorem 1. 单位矩阵的行列式为 \(1\)，上三角矩阵、下三角矩阵（对角线下/上全零的矩阵）的行列式为对角线乘积。
Proof. 考虑选数乘起来的过程，如果不选零，那么归纳发现只有一种选法，就是选对角线。

Theorem 2. 交换两行，行列式变号。
Proof. 对于每个排列，这个交换两行只会影响 \(\mu(p)\) 的奇偶性，由 Lemma 1 得 \(\mu(p)\) 奇偶性改变，所以 \((-1)^{\mu(p)}\) 全部变号，行列式变号。

Theorem 3. 某一行乘以 \(t\)，行列式值乘以 \(t\)。
Proof. 因为每行只选一个数进行乘积。

Theorem 4. \(\begin{vmatrix}a_1+a_2&b_1+b_2\\c&d\end{vmatrix}=\begin{vmatrix}a_1&b_1\\c&d\end{vmatrix}+\begin{vmatrix}a_2&b_2\\c&d\end{vmatrix}\)
Proof. 乘法分配律。

Theorem 4,5 合起来是行的线性性。

Theorem 5. 有两行相同，行列式为 \(0\)。
Proof. 如果交换这两行，行列式应该变号，但是方阵还是那个方阵，行列式的值应该没有改变。

Theorem 6. 用一行的倍数加到另一行，行列式不变。
Proof. 相当于 \(\begin{vmatrix}a&b\\c&d\end{vmatrix}=\begin{vmatrix}a&b\\c+ka&d+kb\end{vmatrix}\)。
由 Theorem 4 得 \(\begin{vmatrix}a&b\\c+ka&d+kb\end{vmatrix}=\begin{vmatrix}a&b\\c&d\end{vmatrix}+\begin{vmatrix}a&b\\ka&kb\end{vmatrix}\)。
右边那个对第二行乘 \(\frac{1}{k}\)，行列式值变为 \(0\)，所以右边那个的行列式为 \(0\)。

行列式求值

Theorem 2,3,6 就是高斯消元用的三种操作，所以对方阵高斯消元，消成上三角矩阵，取其对角线乘积即可。

实现时如果模意义下，没有逆元可用，可以辗转相除消元，参考实现：

点击查看代码 
const int P=998244353;
LL mod(LL x){return (x%P+P)%P;}
void red(LL&x){x=mod(x);}
LL det(vector<LL>*a,int n){
	LL res=1;
	for(int i=0;i<n;i++) for(LL&x:a[i]) x=mod(x);//最好是正数
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			while(a[i][i]){//最好是 a[i][i]，因为下面有个除法
				LL r=a[j][i]/a[i][i];
				for(int k=i;k<n;k++) red(a[j][k]-=a[i][k]*r);
				swap(a[i],a[j]),res=-res;
			}
			swap(a[i],a[j]),res=-res;
		}
	}
	for(int i=0;i<n;i++) red(res*=a[i][i]);
	return mod(res);
}

矩阵树定理

矩阵树定理（Matrix Tree Theorem）被用来计数无向图或有向图的生成树个数。前置条件：图中没有自环。

经典

一个无向无权图，取出它的邻接矩阵 \(A\)，度数矩阵 \(D\)（意思是 \(D[i][i]\) 是点 \(i\) 连接的边的条数，其他地方是零）。

则基尔霍夫（Kirchhoff）矩阵为：\(K=D-A\)。

随意选择 \(k\)，去掉 \(K\) 中的第 \(k\) 行和第 \(k\) 列，得到 \(K'\)，则 \(det(K')\) 为原图的生成树数量。

扩展

对于无向图，如果说边有边权，然后对所有生成树的边权之积求和，我们看作是有边权条重边（默认边权为正），邻接矩阵 \(A[i][j]\) 就变为 \(i\to j\) 有多少条边，度数矩阵 \(D[i][i]\) 就变成点 \(i\) 的边权之和。

有向图生成树分两种情况：

  • 根向树，这种生成树的每条边都从儿子指向父亲。（部分说法是内向树）
  • 外向树，这种生成树的每条边都从父亲指向儿子。

处理方法如下：邻接矩阵不变，度数矩阵含义换一下。根向树的度数矩阵是每个点的出度，外向树的度数矩阵是每个点的入度。

另外有向图还有根的问题，这里的结论是：去掉哪一行、哪一列，根就是谁。

另一类：边权求和

求所有生成树的边权之和之和。

第一种做法是枚举边，先算一遍有这条边的生成树有多少个，再算一遍没有这条边的生成树有多少个，两个相减得到经过这条边的生成树个数，然后乘上它自己的边权。

第二种做法是，将每条边的边权，原来是 \(w\)，现在改成 \(wx+1\) 这个二项式，最后取行列式的一次项系数。
因为注意到乘法：\((ax+c)(bx+d)\equiv(ad+bc)x+cd\pmod{x^2}\)，就是说乘起来之后系数的变化是加。
而且这个二项式的除法很容易：\((ax+1)^{-1}\equiv ax-1\pmod {x^2}\)。
除法的另一种：\(\frac{ax+c}{bx+d}=\frac{(ax+c)(bx-d)}{b^2x^2-d^2}=\frac{abx^2+(bc-ad)x-cd}{b^2x^2-d^2}\)，这个除法很烦，我们对 \(x^2\) 取模，那么就 \(=\frac{c}{d}-\frac{bc-ad}{d^2}x\)。
加减法和普通多项式一样了。这样就能一次算出所有。

有一说一，这样将乘法转化为加法的技巧，除了 \([x^1](ax+1)(bx+1)\) 还有 \(\ln e^xe^y\)。不要忘了。

BEST 定理

BEST 定理，值得注意的是 BEST 分别是四个人的名字而不是“最好的”，用于对有向图欧拉回路计数。可以数出互不循环同构的欧拉回路条数。
前置条件注意：必须存在欧拉回路（\(inn_i=out_i\)），必须有至少一条边，必须连通。

它的形式为：有向图 \(G\) 的欧拉回路条数为 \(T\prod_{x\in V}(deg_x-1)!\)。其中 \(T\) 是任意一点为根的根向生成树个数，可以证明任意一个答案都相同。由于出度等于入度，因此这里的 \(deg_x\) 是入度和出度随便取一个。

如果题目钦定了起点 \(s\)，这里注意答案要乘上 \(deg_s\)，因为对于一个欧拉回路，\(s\) 在里面的出现次数明显是 \(deg_s\)。因为它们循环同构了，所以我们强行不让它循环同构，从 \(deg_s\) 个 \(s\) 里面选一个作为欧拉回路开始。
如果题目的边是不区分的，这时又要注意，BEST 定理算出来的边是有区分的，我们除一下重边条数的阶乘即可。
如果题目是无向图，需要钦定一下边的方向。

LGV 引理

LGV 引理，用于计算：在有向无环图上不相交路径的数量/权值和。

具体地，设起点们 \(A=\{a_1,a_2,\cdots,a_n\}\)，终点们 \(B=\{b_1,b_2,\cdots,b_n\}\)。然后当然有个 DAG。然后定义一条路径 \(P\) 的权值是边权之积 \(w(P)\)。
定义：\(e(i,j)\) 表示 \(i\) 到 \(j\) 的所有路径的权值，\(e(i,j)=\sum_{P:i\to j}w(P)\)。
一组不相交路径 \(S=\{P_1,P_2,\cdots,P_n\}\)，表示 \(P_i:A_i\to B_{\sigma(i)}\)，这里的 \(\sigma(i)\) 是一个排列，一个 \(S\) 对应一个 \(\sigma\)（如果合法的话）。\(S\) 中的路径必须没有公共点。

LGV 引理的结论是：

\[det(\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})=\sum_{S:A\to B}(-1)^{\mu(\sigma(S))}\prod_{i=1}^n w(P_i).\]

这里的 \(S\) 必然是不相交路径，否则不算进去。\(\sigma(S)\)，改个定义是 \(S\) 对应的排列 \(\sigma\)。\(\mu\) 是排列逆序对数，老朋友了。

如果有：“只要路径两两不相交，那么每个起点 \(A_i\) 只能到达和它对应的那个终点 \(B_i\)” 这一限制的话，那么就可以忽略掉公式中 \((-1)^{\mu(\sigma(S))}\) 这一项了。因为此时任意一组不相交路径的方案，对应的排列 \(P\) 都是 \(1,2,3,⋯n\)，也就是没有逆序对。但是如果没有上面那个限制，比如说 NOID1T2，第一层的第 \(i\) 个点最终不一定会走到最后一层的第 \(i\) 个点，那么就要考虑那个 \(-1\) 的次数带来的影响，这一题就是发现交点个数的奇偶性和最终起终点排列逆序对数的奇偶性相同，所以直接用 LGV 引理。——Luogu@AK_Dream

例题

洛谷题号吧，洛谷的模板题和题解还是很行的。

题解没有必要了，该讲的在上面都有。