大概……会很简洁吧 qwq。
矩阵树定理
对于无自环无向图 \(G=(V,E)\),令其度数矩阵 \(D\),邻接矩阵 \(A\),令该图的 \(\text{Kirchhoff}\) 矩阵 \(K=D-A\)。取其任意一个 \(n-1\) 阶主子式 \(K'\),则 \(G\) 的生成树个数 \(s=\det K'\)。
证明先咕掉 qwq。
一些推广
对于有向图以 \(r\) 为根的内向生成树,取 \(D\) 为初度矩阵,取主子式时删去 \(r\) 行 \(r\) 列,再求行列式即可。
外向生成树则相反。
呃……真的好简洁。例题看标签里吧。