Matrix-Tree 定理作用:给定 n 个点 m 条边的无向图,求图的生成树个数。
定义矩阵K[i][j]=D[i][j]-A[i][j],(其中D为度数矩阵(即当i==j时,D[i][j]=节点 i 的度数,其余为0),A为邻接矩阵,有边相邻即为1,其余为0)
结论:对于已经得出的基尔霍夫矩阵,去掉其随意一行一列得出的矩阵的行列式,其绝对值为生成树的个数
注:行列式的绝对值:先用高斯消元消成上三角矩阵,把对角线乘起来
原文:https://www.cnblogs.com/starve/p/12849726.html