其实挺没用的, 简单记录一下

对于一个无向图G,它的生成树个数等于其基尔霍夫\text{Kirchhoff} 矩阵任何一个N-1阶主子式的行列式的绝对值.

  • \text{Kirchhoff} 矩阵:
    定义为图中度数矩阵D – 邻接矩阵A

这里邻接矩阵可以有不同形式
1. 如果A_{i,j}表示ij之间边的数量,则\det等于生成树的数量
2. 如果A_{i,j}表示ij之间边的长度,则\det=\sum_T\prod T_{e_i},也就是每个生成树的边权积之和

  • 求行列式的值
  1. 交换行列式两行, \det值取反
  2. 一行加上另一行的若干倍, 行列式值不变
  3. 对角矩阵的行列式值为对角线的乘积

于是就可以高斯消元了…

模板题: sdoi2014 重建…

Leave a Reply