图论数学：矩阵树定理

运用矩阵树定理进行生成树计数

给定一个n个点m条边的无向图，问生成树有多少种可能

直接套用矩阵树定理计算即可

矩阵树定理的描述如下：

首先读入无向图的邻接矩阵，u-v G[u][v]++ G[v][u]++

度数矩阵： u-v D[u][u]++ D[v][v]++;

然后计算图G的基尔霍夫矩阵 C=D-G

接着去掉基尔霍夫矩阵的第i行和第i列（必须都是i,i取任意值）

计算剩下的子矩阵的行列式的值得绝对值即为生成树个数

然后对于有向图来说：

边 u->v G[u][v]++ 然后是D[v][v]++（有向图的度数矩阵指的是入度而不是出度）

这样根据上述步骤计算得来的是树形图的个数

在计算行列式的时候：

先用高斯消元消成上三角矩阵，再把对角线乘起来

（与乘法逆元相关的以后再展开）

下面介绍实现：

const int maxn=15; int A[maxn][maxn],B[maxn][maxn]; double a[maxn][maxn]; int T,n,m;

B是邻接矩阵，A是度数矩阵

a是基尔霍夫矩阵

我们在读入了n之后n--的目的是直接排除最后一行和最后一列将其变成余子式（是叫这个嘛？？）

然后是计算行列式：

void gauss() {int now=1;for(int i=1;i<=n;i++){int j=now;while(fabs(a[j][now])<eps&&j<=n) j++;if(j==n+1) {puts("0");return;}for(int k=1;k<=n;k++) swap(a[now][k],a[j][k]);for(int j=now+1;j<=n;j++){double t=a[j][now]/a[now][now];for(int k=1;k<=n;k++)a[j][k]-=t*a[now][k];}now++;}double ans=1;if(n&1) ans=-ans;for(int i=1;i<=n;i++) ans*=a[i][i];printf("%.0lf\n",abs(ans)); }

这里的高斯消元是消成上三角矩阵，然后就方便计算det了

完整的实现如下：

1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #define eps 1e-8 6 using namespace std; 7 const int maxn=15; 8 int A[maxn][maxn],B[maxn][maxn]; 9 double a[maxn][maxn]; 10 int T,n,m; 11 int read() 12 { 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();} 15 while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 void gauss() 19 { 20 int now=1; 21 for(int i=1;i<=n;i++) 22 { 23 int j=now; 24 while(fabs(a[j][now])<eps&&j<=n) j++; 25 if(j==n+1) {puts("0");return;} 26 for(int k=1;k<=n;k++) swap(a[now][k],a[j][k]); 27 for(int j=now+1;j<=n;j++) 28 { 29 double t=a[j][now]/a[now][now]; 30 for(int k=1;k<=n;k++) 31 a[j][k]-=t*a[now][k]; 32 } 33 now++; 34 } 35 double ans=1; 36 if(n&1) ans=-ans; 37 for(int i=1;i<=n;i++) ans*=a[i][i]; 38 printf("%.0lf\n",abs(ans)); 39 } 40 int main() 41 { 42 T=read(); 43 while(T--) 44 { 45 memset(A,0,sizeof(A)); 46 memset(B,0,sizeof(B)); 47 n=read();m=read(); 48 n--; 49 for(int i=1;i<=m;i++) 50 { 51 int u=read(),v=read(); 52 u--;v--; 53 A[u][u]++;A[v][v]++; 54 B[u][v]++;B[v][u]++; 55 } 56 for(int i=1;i<=n;i++) 57 { 58 for(int j=1;j<=n;j++) 59 a[i][j]=A[i][j]-B[i][j]; 60 } 61 gauss(); 62 } 63 return 0; 64 }

 

转载于:https://www.cnblogs.com/aininot260/p/9426134.html

总结

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

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