【概述】

Matrix-Tree 定理又称基尔霍夫矩阵树定理，其用于解决：给定 n 个点 m 条边的无向图，求图的生成树个数的问题。

其利用线性代数中矩阵的行列式来进行求解，关于矩阵的行列式：点击这里

【基尔霍夫矩阵】

1.基本定义

1）无向图 G：给定 n 个点，m 条边的无向图，设点集为 V，边集为 E，则其记为 G(V,E)

2）度数矩阵 D[G]：当 i≠j 时，D[i][j]=0，当 i=j 时，D[i][i]=点 vi 的度数

3）邻接矩阵 A[G]：当 vi、vj 有边连接时，A[i][j]=1，当 vi、vj 无边连接时，A[i][j]=0

4）基尔霍夫矩阵(Kirchhoff) K[G]：也称拉普拉斯算子，其定义为 K[G]=D[G]-A[G]，即：K[i][j]=D[i][j]-A[i][j]

例如：

2.基尔霍夫矩阵性质

对于任意一个图 G，其基尔霍夫矩阵 K 具有以下性质：

基尔霍夫矩阵 K 的每一行或每一列上的元素和都是 0

基尔霍夫矩阵 K 的行列式的值为 0

基尔霍夫矩阵 K 的任意一个代数余子式值都相同

如果图 G 不连通，基尔霍夫矩阵 K 的任意主子式行列式值为 0

如果图 G 是一棵树，基尔霍夫矩阵 K 的任意一个 n-1 阶主子式的行列式为 1

3.Matrix-Tree 定理

Matrix-Tree 定理的内容为：对于已经得出的基尔霍夫矩阵，去掉其随意一行一列得出的矩阵的行列式，其绝对值为生成树的个数

因此，对于给定的图 G，若要求其生成树个数，可以先求其基尔霍夫矩阵，然后随意取其任意一个 n-1 阶行列式，然后求出行列式的值，其绝对值就是这个图中生成树的个数。

LL K[N][N]; LL gauss(int n){//求矩阵K的n-1阶顺序主子式LL res=1;for(int i=1;i<=n-1;i++){//枚举主对角线上第i个元素for(int j=i+1;j<=n-1;j++){//枚举剩下的行while(K[j][i]){//辗转相除int t=K[i][i]/K[j][i];for(int k=i;k<=n-1;k++)//转为倒三角K[i][k]=(K[i][k]-t*K[j][k]+MOD)%MOD;swap(K[i],K[j]);//交换i、j两行res=-res;//取负}}res=(res*K[i][i])%MOD;}return (res+MOD)%MOD; } int main(){int n,m;scanf("%d%d",&n,&m);memset(K,0,sizeof(K));for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);K[x][x]++;K[y][y]++;K[x][y]--;K[y][x]--;}printf("%lld\n",gauss(n));return 0; }

 

总结

以上是生活随笔为你收集整理的图论 —— 生成树 —— 生成树计数 —— 基尔霍夫矩阵的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。