矩阵-树定理（Matrix Tree）

LawrenceSivan · 2021-06-03 21:53:32 · 题解

矩阵-树定理

（Kirchhoff's matrix tree theorem）

前言：

首先这个玩意集训的时候就已经讲过了。

但是当时并没有认真听。

现在回头看这玩意……

前置知识：

然后 ，不开 long long 就没有然后了。

CODE：

//#define LawrenceSivan

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define re register
const int N=150;
const int mod=1e9;
#define INF 0x3f3f3f3f

#define int long long//记得long long

struct matrix {//这里是矩阵的板子
    int n,m;
    int tmp;
    int a[N][N];

    matrix(){}
    matrix(const int &_n,const int &_m):n(_n+1),m(_m+1){
        memset(a,0,sizeof(a));
    }

    inline void clear(){
        memset(a,0,sizeof(a));
        for(int i=0;i<=n;i++){
            a[i][i]=1;
        }
    }

    inline void id(){
        for(int i=0;i<=n;i++){
            a[i][i]=1;
        } 
    } 

    inline matrix operator + (const matrix &b)const{
        matrix res(n,b.m);
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                res.a[i][j]=(a[i][j]+b.a[i][j])%mod;
            }
        }
        return res;
    } 

    inline matrix operator - (const matrix &b)const{
        matrix res(n,b.m);
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                res.a[i][j]=(a[i][j]-b.a[i][j])%mod;
            }
        }
        return res;
    } 

    inline matrix operator * (int c)const{
        matrix res(n,m);
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                res.a[i][j]=(c*a[i][j])%mod;
            }
        }
        return res;
    }

    inline matrix operator * (const matrix &b)const{
        matrix res(n,b.m);
        for(int i=0;i<=n;i++){
            for(int j=0;j<=b.m;j++){
                for(int k=0;k<=m;k++){
                    res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%mod;        
                }
            }
        } 
        return res;
    }

    inline matrix operator ^ (int p)const{
        matrix res(n,m),x = *this; 
        res.clear();
        for(;p;p>>=1,x=x*x){
            if(p&1)res=res*x;
        }
        return res;
    }

    inline matrix trans(){
        matrix res(m,n);
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                res.a[i][j]=a[j][i];
            }
        }
        return res;
    }

    inline int det(){//高斯消元与求行列式
        int ans=1;
        for(re int i=1;i<=tmp;i++){
            for(re int j=i+1;j<=tmp;j++){
                while(a[j][i]){//辗转相除
                    int t=a[i][i]/a[j][i];
                    for(re int k=i;k<=tmp;k++){
                        a[i][k]=(a[i][k]-a[j][k]*t%mod+mod)%mod;

                    }
                    swap(a[i],a[j]);
                    ans*=-1;//交换以后需要变号
                }
            }
            ans=(ans*a[i][i]%mod+mod)%mod;//勤处理负数
        }
        return (ans%mod+mod)%mod;
    }
}W,D,A;
//W 基尔霍夫矩阵（拉普拉斯矩阵）
//D 度数矩阵（对角线矩阵）
//A 邻接矩阵

int n,m;

char a[15][15];

int id[15][15],cnt;//id 用于重新编号

inline void add(int u,int v){
    A.a[u][v]=1;
    A.a[v][u]=1;
}

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

signed main(){
#ifdef LawrenceSivan
    freopen("aa.in","r",stdin);
    freopen("aa.out","w",stdout);
#endif
    n=read();m=read();
    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='.')id[i][j]=++cnt;
        }
    }

    W=matrix(cnt,cnt);//初始化矩阵
    D=matrix(cnt,cnt);
    A=matrix(cnt,cnt);

    for(re int i=1;i<=n;i++){//构造邻接矩阵
        for(re int j=1;j<=m;j++){
            if(id[i][j]&&id[i][j-1])add(id[i][j],id[i][j-1]); 
            if(id[i][j]&&id[i-1][j])add(id[i][j],id[i-1][j]);   
        }
    }

    for(re int i=1;i<=cnt;i++){//构造度数矩阵
        for(re int j=1;j<=cnt;j++){
            if(A.a[i][j]) D.a[i][i]++;
        }
    }

    W=D-A;//两者作差得到基尔霍夫矩阵（拉普拉斯矩阵）

    W.tmp=--cnt;//除掉最后一行与最后一列

    /*for(re int i=1;i<=cnt;i++){
        for(re int j=1;j<=cnt;j++){
            cout<<W.a[i][j]<<" ";
        }
        cout<<endl;
    }*/

    printf("%lld\n",W.det());//求行列式

    return 0;
}

关于拉普拉斯矩阵的有向图情况：

像我们上面所说的，只考虑入度或者出度就可以了。

但是考虑这两种是不一样的。

设有向图 G（允许重边，可以扩展到加权，但是不能有自环） 有 n 个节点。出度矩阵 D=(l_{i,j})_{n\times n} 定义如下：

• 若 i==j 则 l_{i,j}=\deg^{out}(v_i) , \deg^{out}(v_i) 为定点 v_i 的出度。

• 若 i\neq j ，则 l_{i,j}=0

类似地可以定义入度矩阵。

定义 edge(i,j) 为点 i 指向点 j 的有向边数。

定义邻接矩阵 A=(l_{i,j})_{n\times n}

• 若 i\neq j , l_{i,j}=edge(i,j)

于是 就可以定义 Laplace 矩阵 L^{out} 和 L^{in} 。

• 当为 L^{in} 时，统计的是外向树。（所有边指向叶节点）

• 当为 L^{out} 时，统计的是内向树。（所有边指向根节点）

内向是出度，外向是入度（一定要记牢，不要混淆）

如果指定了根节点为root 那么要在计算行列式的时候要去掉的就不是任意一行和一列了，而是第 root 行和第 root 列。

inline void add(int t,int u,int v,int w){
    if(t==0){//内向树，出度矩阵
        (D.a[u][u]+=w)%=mod;
        (A.a[u][v]+=w)%=mod;
    }

    else{//外向树，入度矩阵
        (D.a[v][v]+=w)%=mod;
        (A.a[u][v]+=w)%=mod;
    }
}

因此如果要统计一张图所有的内向树形图，只要枚举所有的根 root 并对所有的行列式求和即可。

如果要统计一张图所有的外向树形图，只要枚举所有的根 root 并对所有的行列式求和即可。

关于拉普拉斯矩阵扩展到带权

• 求生成树边权积之和

将上述中的 D , A 改为记录相应边边权和，则行列式从生成树个数变为对应的生成树所有边权之积的和。

于是可以发现，只要把边权全都看成 1 ，就是上面这道题我们解决的情况：求生成树个数。