矩阵树定理

· · 算法·理论

简介

基尔霍夫矩阵树定理（简称作矩阵树定理）用于对给定图的生成树数量进行计数。

该定理使得只需要进行一次行列式求值就可以得到一个图的生成树数量。

本文旨在直观的理解矩阵树定理，如果希望得到较为严格的定义与证明，可以阅读 这篇文章。

定理内容

在该定理中不允许自环，允许重边。

给定图的邻接矩阵为 A。在有向图中，A_{i,j} 的值表示有 A_{i,j} 条从 i 连向 j 的边。在无向图中，A_{i,j}=A_{j,i} 表示 i 与 j 之间的双向边数量。

给定图的度数矩阵为 D。无向图中，D_{i,i} 的值等于 i 的度数。有向图中，D_{i,i} 的值等于 i 的入度或出度，相应地得到入度矩阵 D^{in} 和 D^{out}。并且有 D_{i,j}=0,\forall i\not=j。

定义无向图的拉普拉斯 (Laplace) 矩阵 L=D-A。

有向图的入度拉普拉斯矩阵 L^{in}=D^{in}-A，出度拉普拉斯矩阵为 L^{out}=D^{out}-A。

那么，有结论：

定理1：无向图的拉普拉斯矩阵的任意 n-1 阶 主子式 的行列式相等，且其值等于该图的生成树个数。（选定不同的重边得到的生成树认为是不同的生成树）。

定理2：有向图以 r 为根的根向生成树（所有边指向父亲）的数量等于出度拉普拉斯矩阵删去第 r 行与第 r 列得到的 n-1 阶主子式的行列式。

定理3：有向图以 r 为根的叶向生成树（所有边指向儿子）的数量等于入度拉普拉斯矩阵删去第 r 行与第 r 列得到的 n-1 阶主子式的行列式。

证明

不会

参考代码

下面给出 模板题 的参考代码。

#include<bits/stdc++.h>
using namespace std;
const int N=305,mod=1e9+7;
int n;
int a[N][N];
int main(){
  int n,m,t;
  scanf("%d%d%d",&n,&m,&t);
  for(int i=1;i<=m;++i){
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    if(t){
      a[v][v]+=w;
      if(a[v][v]>=mod)a[v][v]-=mod;
      a[u][v]-=w;
      if(a[u][v]<0)a[u][v]+=mod;
    }else{
      a[u][u]+=w;
      if(a[u][u]>=mod)a[u][u]-=mod;
      a[v][v]+=w;
      if(a[v][v]>=mod)a[v][v]-=mod;
      a[u][v]-=w;
      if(a[u][v]<0)a[u][v]+=mod;
      a[v][u]-=w;
      if(a[v][u]<0)a[v][u]+=mod;
    }
  }
  int neg=1;
  for(int i=2;i<=n;++i){
    for(int j=i+1;j<=n;++j){
      while(a[i][i]){
        int t=a[j][i]/a[i][i];
        for(int k=i;k<=n;++k){
          a[j][k]-=1ll*t*a[i][k]%mod;
          if(a[j][k]<0)a[j][k]+=mod;
        }
        swap(a[i],a[j]);
        neg*=-1;
      }
      swap(a[i],a[j]);
      neg*=-1;
    }
  }
  int ans=1;
  for(int i=2;i<=n;++i)ans=1ll*ans*a[i][i]%mod;
  ans=(ans*neg%mod+mod)%mod;
  printf("%d\n",ans);
}