生成树计数

约定这张图为\(G=(V,E)\)，无向图，可以有重边，自环直接忽略。

Some Definitions

邻接矩阵

一张图的邻接矩阵\(\mathbf A\)满足\(\mathbf A_{i,j}=cnt((i,j))\)。
重边重算。

度数矩阵

一张图的度数矩阵\(\mathbf D\)满足\(\mathbf D_{i,j}=[i=j]deg_i\)。
重边重算。

关联矩阵

一张图的度数矩阵\(\mathbf B\)满足\(\mathbf B_{i,j}=[\exists(i,j)\in E]-1^{[i>j]}\)。

Laplace矩阵

一张图的Laplace矩阵\(\mathbf L=\mathbf D-\mathbf A\)。

Some Properties

\(1.\det(\mathbf L)=0\)
\(2.\mathbf L\)的所有\(C_{i,j}\)都相等。
\(3.\mathbf B^T\mathbf B=\mathbf L\)
\(4.\operatorname{rank}(\mathbf L)=n-1\)

Kirchhoff定理

一张图的生成树个数等于\(\mathbf L\)的任意一个\(C_{i,j}\)，也等于\(\prod\limits_{i=1}^{n-1}\lambda_i\)。

生成树计数

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12133724.html