生成树计数问题：

对于一个有n个点的无向图，由图中n-1条边构成一个边集，这n-1条边恰好连接图中全部的点并构成一棵树，称为生成树，求这样的边集的个数。

从上面的描述中，我们知道两个不同的生成树之间是允许有重复的边的，比如：

他就有三个生成树：

Matrix-Tree定理：

预备概念：

  • 度矩阵 ：一个n个顶点的无向图G，定义它的度数矩阵D，D是一个n*n的矩阵。对于顶点u，设度数为deg[u]，如果i=j，那么D[i][j]=deg[i],否则D[i][j]=0
  • 邻接矩阵：一个n个顶点的无向图G，定义它的邻接矩阵A，A是一个n*n的矩阵。如果i和j之间有边，那么A[i][j]=1,否则等于0
  • 关联矩阵：一个n个顶点m条边的无向图G，定义它的关联矩阵B，B是一个n*m的矩阵。对于第i条边e[i]=(u,v)，那么B[u][i]和B[v][i]中一个是1，一个是-1，第i列其他值为0，那么我们有：

    所以对于，如果i=j，它是顶点i的度数，否则，如果i和j之间有边，那么它等于-1，否则它等于0
  • Kirchhoff矩阵：对于一个n个顶点m条边的无向图G，定义它的Kirchhoff矩阵C,C是一个n*n的矩阵，，显然，C = D - A。

Matrix-Tree定理：
对于一个无向图G，它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。
所谓n-1阶主子式就是对行列式中任何一个元素，去掉它本身以及与他同行同列的元素后，剩下的元素构成的行列式。

举个例子，对于如下的无向图，三个矩阵分别为：

图的生成树的个数一般就用这个定理做就可以，行列式的求取方法一般就是按行（列）展开，或者高斯消元（化为上三角型），套模板就可以，模板见我另一篇博客，链接：
https://blog.csdn.net/Izayoi_w/article/details/81514248
至于这个定理的证明。。。我线代刚及格，就不证了吧。。。。