矩阵树定理

最近学习了矩阵树定理。

矩阵树定理可以求生成树个数

前置知识

行列式

定义

对于一个\(N\times N\)矩阵\(A\)，它的行列式\(det(A)\)： \[ det(A)=\sum\limits_{(i_1i_2...i_n)}(-1)^ka_{1,i_1}a_{2,i_2}...a_{n,i_n}= \left|\begin{array}{cccc} a_{1,1} & a_{1,2} & \dots & a_{1,n} \\ a_{2,1} & \dots \\ \dots \\ a_{n,1} & a_{n,2} & \dots & a_{n,n} \end{array}\right| \]

其中\(i\)是\(n\)的一个排列，\(k\)是这个排列的逆序对数

这个定义可以理解为每行每列仅取一个，求所有方案的乘积和

几何意义：线性变换的（体积）放大率

性质

行列式具有以下性质：

• \(det(A)=det(A^T)\)（行列等价）
• 交换两行，行列式变号（从奇偶排列的角度看）
• 某一行乘K，行列式变为K倍（从几何意义理解）
• 某一行加上另一行的K倍，行列式不变（这意味着行列式可以高斯消元）

把\(\forall i>j,a_{i,j}=0\)的矩阵称为上三角矩阵，左上到右下称为主对角线

• 上三角矩阵的行列式为主对角线乘积（由定义得）

求解

行列式的求解可以用高斯消元\(O(n^3)\)实现：

先高斯消元把矩阵等价变形为上三角矩阵，然后求主对角线乘积就好了

如果答案要膜一个质数，就用逆元

如果丧心病狂不是质数，就只能辗转相除法了

注意记录交换行的次数，并取负

ll det(matrix a,int n){
	int tot=0;
	for (int i=1;i<=n;i++){
		int where=-1;
		for (int j=i;j<=n;j++) if (a[j][i]!=0) {where=j;break;}
		if (where<0) return 0;
		if (where>i){
			tot++;
			for (int j=1;j<=n;j++) swap(a[i][j],a[where][j]);
		}
		for (int j=i+1;j<=n;j++){
			ll t=a[j][i]*inv(a[i][i])%MD;
			for (int k=i;k<=n;k++) A(a[j][k],-a[i][k]*t);
		}
	}
	ll res=1;
	for (int i=1;i<=n;i++) (res*=a[i][i])%=MD;
	return (tot&1)?MD-res:res;
}

基尔霍夫矩阵

对于一个无向图，定义邻接矩阵和度数矩阵：

• 邻接矩阵：\(a_{u,v}=a_{v,u}=1 当且仅当存在u\leftrightarrow v\)
• 度数矩阵：\(a_{v,v}\)表示v的度数

类似地，有向图也有以下定义：

• 邻接矩阵：\(a_{u,v}=1 当且仅当存在u\rightarrow v\)
• 度数矩阵：\(a_{v,v}\)表示v的入度

基尔霍夫矩阵就是邻接矩阵减去度数矩阵

矩阵树定理

Matrix-tree定理：

一个图的生成树个数为 基尔霍夫矩阵的余子式\(M_{i,i}\)的行列式\(det(M_{i,i})\)

对应有向图就是以i为根的外向树个数

模板

bzoj4596

#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;

const int maxn=25;
typedef ll matrix[maxn][maxn];
const ll MD=1e9+7;
int n,m[maxn];
ll ans;
matrix kir;
struct data{
	int x,y;
	inline void read() {scanf("%d%d",&x,&y);}
}a[maxn][105];
inline void A(ll &a,ll b){ (a+=(b%MD+MD)%MD)%=MD; }
inline ll inv(ll a){
	ll res=1,w=a%MD,b=MD-2;
	while (b){
		if (b&1) res=res*w%MD;
		w=w*w%MD;
		b>>=1;
	}
	return res;
}
ll det(matrix a,int n){
	int tot=0;
	for (int i=1;i<=n;i++){
		int where=-1;
		for (int j=i;j<=n;j++) if (a[j][i]!=0) {where=j;break;}
		if (where<0) return 0;
		if (where>i){
			tot++;
			for (int j=1;j<=n;j++) swap(a[i][j],a[where][j]);
		}
		for (int j=i+1;j<=n;j++){
			ll t=a[j][i]*inv(a[i][i])%MD;
			for (int k=i;k<=n;k++) A(a[j][k],-a[i][k]*t);
		}
	}
	ll res=1;
	for (int i=1;i<=n;i++) (res*=a[i][i])%=MD;
	return (tot&1)?MD-res:res;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		scanf("%d",&m[i]);
		for (int j=1;j<=m[i];j++) a[i][j].read();
	}
	for (int s=0;s<(1<<n-1);s++){
		cl(kir,0);int tot=0;
		for (int i=1;i<=n;i++)
		 if (s&(1<<i-1)){tot++;
		  for (int j=1;j<=m[i];j++){
		  	int x=a[i][j].x,y=a[i][j].y;
		  	A(kir[x][y],-1);A(kir[y][x],-1);A(kir[x][x],1);A(kir[y][y],1);
		  }}
		A(ans,((n-1-tot&1)?-1:1)*det(kir,n-1));
	}
	printf("%lld",ans);
	return 0;
}