基尔霍夫矩阵

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

【基尔霍夫矩阵】
1.基本定义
1）无向图 (G)：给定 (n) 个点，(m) 条边的无向图，设点集为 (V)，边集为 (E)，则其记为 (Gleft ( V,E ight ))

2）度数矩阵 (Dleft [ G ight ])：当 (i eq j) 时，(Dleft [ i ight ]left [ j ight ]=0)，当 (i= j) 时，(Dleft [ i ight ]left [ j ight ]=点v的度数)

3）邻接矩阵 (Aleft [ G ight ])：当 (v_{i})、(v_{j}) 有边连接时，(Aleft [ i ight ]left [ j ight ]=1)，当 (v_{i})、(v_{j}) 无边连接时，(Aleft [ i ight ]left [ j ight ]=0)

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

例如：

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

1.基尔霍夫矩阵 (K) 的每一行或每一列上的元素和都是 (0)
2.基尔霍夫矩阵 (K) 的行列式的值为 (0)
3.基尔霍夫矩阵 (K) 的任意一个代数余子式值都相同
4.如果图 (G) 不连通，基尔霍夫矩阵 (K) 的任意主子式行列式值为 (0)
5.如果图 (G) 是一棵树，基尔霍夫矩阵 (K) 的任意一个 (n-1) 阶主子式的行列式为 (1)

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

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

基尔霍夫矩阵裸题：here

模板：（AC_Code）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 20;
 5 const int inf = 0x3f3f3f3f;
 6 #define rep(i,first,second) for(ll i=first;i<=second;i++)
 7 #define dep(i,first,second) for(ll i=first;i<=second;i++)
 8 int degree[maxn];
 9 ll a[maxn][maxn];
10 int vis[maxn][maxn];
11 
12 void init(){
13     memset(degree,0,sizeof(degree));
14     memset(a,0,sizeof(a));
15     memset(vis,0,sizeof(vis));
16 }
17 
18 ll det(int n){
19     ll ret=1;
20     for(int i=2;i<=n;i++){
21         for(int j=i+1;j<=n;j++){
22             while(a[j][i]){
23                 ll t=a[i][i]/a[j][i];
24                 for(int k=i;k<=n;k++){
25                     a[i][k]=(a[i][k]-a[j][k]*t);
26                 }
27                 for(int k=i;k<=n;k++){
28                     swap(a[i][k],a[j][k]);
29                 }
30                 
31                 ret=-ret;
32             }
33         }
34         if( a[i][i]==0 ) return 0;
35         ret*=a[i][i];
36     }
37     if( ret<0 ) ret=-ret;
38     return ret;
39 }
40 
41 int main()
42 {
43     int t;
44     scanf("%d",&t);
45     while( t-- ){
46         init();
47         int n,m;
48         scanf("%d%d",&n,&m);
49         while( m--){
50             int u,v;
51             scanf("%d%d",&u,&v);
52             a[u][u]++;
53             a[v][v]++;
54             a[u][v]--;
55             a[v][u]--;
56         }
57         printf("%lld
",det(n));
58     }
59     return 0;
60 }

参考博客：here