学习笔记 - BEST定理 | Lucky

——“这将是有史以来最好的定理” XD

# 引入例题

> Linked 洛谷 P5807 Which Dreamed It

简化题意：给定一个 $n$ 个点 $m$ 条边的有向图，求从 $1$ 出发有多少条欧拉回路；每条边视作互不相同，只要经过边的次序不同则视为不同的欧拉回路。

让你没有想到的是有向图欧拉回路也可以计数……

# BEST定理·内容

对于有向图 $G=(V,E)$：

记 $d_i$ 为点 $i$ 的出度，$T_u(G)$ 是 $G$ 的以点 $u$ 为根的内向生成树的个数。

则从点 $s$ 出发的欧拉回路数量为：

$F(s)=T_s(G)\times (d_s!)\times\prod_{u\in V,u\neq s}(d_u-1)!$

在代码实现时，$T_s(G)$ 直接用 Matrix-Tree 定理求解。

Matrix-Tree定理解决有向图生成树

定义 $D^{I},D^{O}$ 分别为入度、出度矩阵，即 $D^{I}_{i,i}$ 为 $i$ 的入度，$D^{O}_{i,i}$ 为 $i$ 的出度；邻接矩阵 $A$，$A_{i,j}$ 为 $i$ 到 $j$ 的有向边数量。

分为两大类：

外向生成树，拉普拉斯矩阵 $L=D^I-A$；
内向生成树，拉普拉斯矩阵 $L=D^O-A$；

仅此一点区别，最后答案即 $\det L$。

# BEST定理·证明

先解释一下式子的含义——

$T_s(G)$：除去点 $s$，每个点指定一条出边作为树边（除了树边，别的边都是非树边）；
$d_s!$：$s$ 的所有出边随意指定一个顺序；
$(d_u-1)!$：除了 $s$ 的点，把它的非树边出边随意指定顺序。

我们将要证明，这样一个指定了顺序的内向树与所有从 $s$ 出发的欧拉路径一一对应。分两部分证明：

- 内向树对应唯一欧拉回路

对于点 $u$（$u\neq s$），指定其树边出边为欧拉回路上最后从 $u$ 离开的边，而非树边出边则按照指定的顺序经过。需要证明这样的欧拉路径合法。

考虑每次经过一条边，就把这条边删去，只需证明剩下的边 存在欧拉路径 ，而有向图存在欧拉路径必须同时满足：

点的度数：任意点出度与入度之差都不超过 $1$，且入度不等于出度的点最多只有两个；
弱连通性：有向边变为无向边后所有边（不是点）都在同一个连通块里。

若原图符合点度数限制，新图显然符合；而弱连通性需要分类讨论——

若删去的边 $(u,v)$ 是非树边，由于树边是每个点最后离开的边，$u,v$ 之间的树边一定还没有被删去，则 $u$ 到 $v$ 之间可以直接通过树边形成弱连通；
若删去的边是树边，则删去后 $u$ 与剩下的图完全断开，相当于删去了一条链末端的一条边，剩余边仍然弱连通。

点度数限制与弱连通性仍然满足，新图一定存在欧拉路径，进而说明欧拉回路满足条件。

- 欧拉回路对应唯一内向树

对于点 $u$（$u\neq s$），指定其树边出边为欧拉回路上最后从 $u$ 离开的边，而非树边出边则按照指定的顺序经过。需要证明“树边”不成环。

假如成环。

树边出边是最后离开一个点经过的边，则从树边出边离开 $u$ 后就不应该再到达 $u$；
第一条说明从 $u$ 经过其树边出边到达 $v$ 时，$v$ 还未经过其树边出边；当 $v$ 经过其所有非树边出边后，会从其树边出边离开；
一直重复第二条的过程，会回到环上的一个点，而该点已经经过了其树边出边，与第一条矛盾。

所以树边不会成环，又由于原图 $G$ 满足欧拉回路的度数限制，所以树边构成内向树。

# 其他相关

整个有向图 $G$ 的欧拉回路数量为：随意指定一点 $s$，

$F(G)=T_s(G)\prod_{i\in V}(d_i-1)!$

可以从上面已证得的结论推导：从 $s$ 出发的欧拉回路与整个图 $G$ 的欧拉回路的唯一区别在于——$G$ 的欧拉回路没有端点。设 $G$ 的一条欧拉回路经过的点的次序为 $A$（成环），那么 $s$ 在 $A$ 中出现的次数为 $d_s$ 次，只要把环 $A$ 从 $s$ 出现的位置断开就可以得到 $d_s$ 条互不相同的从 $s$ 出发的欧拉回路。

则 $F(G)\times d_s=F(s)$，可推得上式。

顺便证明了存在欧拉回路的有向图 $G$ 满足：对于任意点 $s$，$T_s(G)$ 相等。

# 例题源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=105,M=2e5+10,MOD=1e6+3;
#define ci const int &
inline int Add(ci a,ci b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return int(1ll*a*b%MOD);}
inline int Pow(ci a,ci b){return b? Mul(Pow(Mul(a,a),b>>1),(b&1)? a:1):1;}
inline int Read(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}

int cas,n;
int mat[N][N],du[N],fac[M],din[N];

int Det(){
	int ans=1;
	for(int i=2;i<=n;i++){
		int it=-1;
		for(int j=i;j<=n;j++)
			if(mat[j][i]){
				it=j;
				break;
			}
		if(it==-1) return 0;
		if(it!=i){
			for(int j=i;j<=n;j++) swap(mat[i][j],mat[it][j]);
			ans=Sub(0,ans);
		}
		ans=Mul(ans,mat[i][i]);
		int dv=Pow(mat[i][i],MOD-2);
		for(int j=i;j<=n;j++) mat[i][j]=Mul(mat[i][j],dv);
		for(int j=i+1;j<=n;j++){
			if(!mat[j][i]) continue;
			int mul=mat[j][i];
			for(int k=i;k<=n;k++) mat[j][k]=Sub(mat[j][k],Mul(mat[i][k],mul));
		}
	}
	return ans;
}
void Init(){
	fac[0]=1;
	for(int i=1;i<M;i++) fac[i]=Mul(fac[i-1],i);
}
int main(){
	Init();
	Read(cas);
	while(cas--){
		Read(n);
		memset(mat,0,sizeof mat);
		memset(du,0,sizeof du);
		memset(din,0,sizeof din);
		for(int u=1,m,v;u<=n;u++){
			Read(m);
			while(m--){
				Read(v);
				mat[u][v]=Sub(mat[u][v],1);
				mat[v][v]=Add(mat[v][v],1);
				du[u]++,din[v]++;
			}
		}
		bool fai=false;
		for(int i=1;i<=n;i++)
			if(din[i]!=du[i])
				fai=true;
		if(fai){printf("0\n");continue;}
		int ans=Mul(Det(),fac[du[1]]);
		for(int u=2;u<=n;u++)
			ans=Mul(ans,fac[du[u]-1]);
		printf("%d\n",ans);
	}
	return 0;
}

学习笔记 - BEST定理