运用基尔霍夫矩阵树定理计算图的生成树个数
基尔霍夫（Kirchhoff）矩阵树定理
- 给定一个有n个节点的G，令它的为Q，Q*的行列式即为图G的生成树的个数。
- 若图G为，矩阵Q做如下修改：
- 当i ≠ j，令qi,j等于m (m为i节点和j节点之间边的数量)。
- 当i = j，令qi,j等于点i的度减去i的自环。
简单图：无重边无自环的无向图。
拉普拉斯矩阵：给定一个有n个节点的简单图G，它的拉普拉斯矩阵Ln*n定义为：
L=D−A
其中D为
，A为
。
度矩阵：给定图 G = (V,E)，G的度矩阵D定义为一个n*n的矩阵：
di,j={deg(vi)ifi=j 0otherwise
其中 deg(vi) 为节点 vi 边的数量。
邻接矩阵：对于一个有n个节点的简单图，它的邻接矩阵是这样一个n*n的矩阵：当节点i和节点j之间有边相连时，Ai,j 为1；否则为0。
多图：有自环，有重边的图。
