運用矩陣樹定理進行生成樹計數

給定一個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

總結

以上是生活随笔為你收集整理的图论数学：矩阵树定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。