『算法-ACM 竞赛-疯子的算法总结』9.2 图论中的矩阵应用 Part2 矩阵树基尔霍夫矩阵定理生成树计数 Matrix-Tree

疯子的算法总结(九) 图论中的矩阵应用 Part 2 矩阵树 基尔霍夫矩阵定理 生成树计数 Matrix-Tree

定理：

1.设 G 为无向图，设矩阵 D 为图 G 的度矩阵，设 C 为图 G 的邻接矩阵。

2.对于矩阵 D，D[i][j]当 i!=j 时，是一条边，对于一条边而言无度可言为 0，当 i==j 时表示一点，代表点 i 的度。

即：

3.对于矩阵 C 而言，C 表示两点之间是否存在边，当 i==j 时为一点无边可言为 0，即：

4.定义基尔霍夫矩阵 J 为度数矩阵 D-邻接矩阵 C，即 J=D-C;

5.G 图生成树的数量为任意矩阵 J 的 N-1 阶主子式的行列式的绝对值。

证明：

伪证明，不是证明基尔霍夫定理，而是讲一下原理，证明超过我们所需要使用的范畴。

首先明确一点就是若图 G 是一颗树，他的基尔霍夫矩阵的 N-1 阶行列式的值 1；因为是一棵树，所以不含有环，且两点之间就只有一条边相连，任意列任意行只有 1，且度数矩阵与之对应密切，一个点的度数只和自己的变数有关，且不与其他边相连，度数和为 2*N，边数为 N,且能通过高斯消元化为上三角行列式，即讨论 J 矩阵中能够构成多少个该子树，即为求矩阵 N-1 阶主子式的行列式，注意任意一个图的 J 基尔霍夫矩阵的行列式值都为 0；

实现方式：

就是求这个行列，行列式求得方法是高斯消元，其实就是将行列式化为上三角行列式，这个那份线性代数里讲的挺清楚的，不要被名字吓到。

bool zero(double a)
{
    return a>-eps && a<eps;
}
double Gauss()
{
    double mul,Result=1;
    int i,j,k,b[n];
    for(i=0;i<n;i++) b[i]=i;
    for(i=0;i<n;i++){
        if(zero(a[b[i]][i]))
            for(j=i+1;j<n;j++)
                if(!zero(a[b[j]][i])) { swap(b[i],b[j]); Result*=-1; break;  }
        Result*=a[b[i]][i];
        for(j=i+1;j<n;j++)
            if(!zero(a[b[j]][i])){
                mul=a[b[j]][i]/a[b[i]][i];
                for(k=i;k<n;k++)
                    a[b[j]][k]-=a[b[i]][k]*mul;
            }
    }
    return Result;
}