疯子的算法总结(九) 图论中的矩阵应用 Part 2 矩阵树 基尔霍夫矩阵定理 生成树计数 Matrix-Tree

定理：

1.设G为无向图，设矩阵D为图G的度矩阵，设C为图G的邻接矩阵。

2.对于矩阵D，D[i][j]当 i!=j 时，是一条边，对于一条边而言无度可言为0，当i==j时表示一点，代表点i的度。

即：

$$ f(x)=\left\{ \begin{aligned}D[i][j]=0 \ \ \ \ \ \ \ \ \ i\neq j \\ D[i][j]="DS" \ \ \ i=j \end{aligned} \right. $$

3.对于矩阵C而言，C表示两点之间是否存在边，当i==j时为一点无边可言为0，即：

$$ f(x)=\left\{ \begin{aligned}D[i][j]=0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i= j \\ D[i][j]=1 \ \ \ i=j,i\ conect \ j\end{aligned} \right. $$

4.定义基尔霍夫矩阵J为度数矩阵D-邻接矩阵C，即J=D-C;

5.G图生成树的数量为任意矩阵J的N-1阶主子式的行列式的绝对值。

证明：

伪证明，不是证明基尔霍夫定理，而是讲一下原理，证明超过我们所需要使用的范畴。

首先明确一点就是若图G是一颗树，他的基尔霍夫矩阵的N-1阶行列式的值1；因为是一棵树，所以不含有环，且两点之间就只有一条边相连，任意列任意行只有1，且度数矩阵与之对应密切，一个点的度数只和自己的变数有关，且不与其他边相连，度数和为2*N，边数为N,且能通过高斯消元化为上三角行列式

\begin{bmatrix} 1& ?&?&...\\ 0& 1& ?&...\\ 0& 0& 1&...\\ ...& ...& ...& 1 \end{bmatrix}

，即讨论J矩阵中能够构成多少个该子树，即为求矩阵N-1阶主子式的行列式，注意任意一个图的J基尔霍夫矩阵的行列式值都为0；

实现方式：

就是求这个行列，行列式求得方法是高斯消元，其实就是将行列式化为上三角行列式，这个那份线性代数里讲的挺清楚的，不要被名字吓到。

bool zero(double a)
{
	return a>-eps && a<eps;
}
double Gauss()
{
	double mul,Result=1;
	int i,j,k,b[n];
	for(i=0;i<n;i++) b[i]=i;
	for(i=0;i<n;i++){
		if(zero(a[b[i]][i]))
			for(j=i+1;j<n;j++)
				if(!zero(a[b[j]][i])) { swap(b[i],b[j]); Result*=-1; break;  }
		Result*=a[b[i]][i];
		for(j=i+1;j<n;j++)
			if(!zero(a[b[j]][i])){
				mul=a[b[j]][i]/a[b[i]][i];
				for(k=i;k<n;k++)
					a[b[j]][k]-=a[b[i]][k]*mul;
			}
	}
	return Result;
}