这个东西首次出现在周冬的国家集训队论文里面,解决的问题叫做生成树计数问题。
顾名思义,就是让你求一张无向图中生成树的个数。
首先我们要知道三个概念。
- 邻接矩阵A
这个东西不用我说了吧,就是对于每一条边$Edge_{ij}$,矩阵的$i$行$j$列和$j$行$i$列设为1,其他设为0。 - 度数矩阵D
啥意思呢,就是将每一个点的度数,其中对于每一个不相等的$i,j$有$D[i][j] = 0$ - 基尔霍夫矩阵C
$C = D - A$
而Matrix-Tree定理就是说这个无向图的生成树个数就等于基尔霍夫矩阵的任意一个$N - 1$阶主子式的行列式的绝对值。