Kirchhoff's theorem or Kirchhoff's matrix tree theorem
- G的度数矩阵DG是一个n*n的矩阵,并且满足:当i≠j时,Di,j=0;当i=j时,Di,j等于Vi的度数。
- G的邻接矩阵AG也是一个n*n的矩阵,并且满足:如果Vi、Vj之间有边直接相连,则Ai,j=1,否则为0。
定义G的 Kirchhoff 矩阵CG为CG=DG−AG。
Matrix-Tree 定理:G的所有不同的生成树的个数等于其 Kirchhoff 矩阵 CG任何一个n-1阶主子式(去掉第行第i列的新矩阵)的行列式的绝对值。
运用高斯消元计算行列式绝对值。高斯消元过程中除法运用辗转相消实现。
Reference:
https://www.cnblogs.com/wuyuhan/p/5238652.html
https://www.cnblogs.com/GerynOhenz/p/4450417.html
http://blog.csdn.net/u010182633/article/details/45225179
代码如下: