生成树计数问题
给一副n个节点的无向图G，求一个包含n-1条边的边集使得边集的边构成一颗树，问这样的边集的数量。
矩阵树定理
以下我们都不对重边与自环进行讨论。 先定义度数矩阵D，是一个n*n的矩阵。 Di,i=节点i的度数，对于i不等于j，Di,j=0。 再定义邻接矩阵A，也是一个n*n的矩阵。 i与j有边相连就有Ai,j=1否则Ai,j=0。 最后定义基尔霍夫矩阵C=D-A。 那么，Ci,i=i的度数，对于i不等于j，若i与j间有边相连则Ci,j=-1否则Ci,j=0。 为了方便一些萌新，讲讲行列式吧。 我们都知道一个n*n矩阵a的行列式的定义： ∑b是一个n的排列(−1)b的逆序对个数∗Πni=1ai,bi 这个记作det(a)，或者说|a|。 行列式有一些性质： 1、|A|=|AT| 2、|AB|=|A||B| 我们知道矩阵乘法后位置(i,j)由A的第i行与B的第j列点积而来，即A的第i行与BT的第j行点积，容易得到|AB|=|A||BT|=|A||B| 3、两个矩阵都是n*n的，除了第一行完全相同，那么它们的行列式之和等于将它们第一行相加其余不变的新矩阵的行列式。 这个非常好懂。 同样根据性质能得到一些推论： 1、将A任意两行或两列交换得到新矩阵B，则|B|=-|A|。 根据定义看，容易证明交换后任意排列的逆序对个数改变了1。 而这样的话，重排对角线因为每次一定要同时交换行列，所以行列式是不变的。 2、将A任意一行同时乘上x得到新矩阵B，则|B|=x|A|。 易证 3、将A任意一行加到另一行上，得到新矩阵B，则|B|=|A| 我们假如是将第二行加到第一行上。 根据之前的性质3等同于|A|+|C| C是一个前两行完全相同的矩阵。 容易知道|C|=0，为什么？ 看行列式的定义，例如b1=i，b2=j，那么当b1=j而b2=i时逆序对个数刚好差1，正负形相反，而无论后面是什么，贡献完全正负抵消，因此为0。 这三个推论让我们可以使用高斯消元求解行列式。 4、每行每列和均为0的矩阵行列式为0。 高斯消元过程中这一性质仍然存在。 最后消出来，最后一行前n-1一定为0，又因和为0，所以最后一项也是0，那么行列式即为0。
来定义一个矩阵A的余子式Mi,j表示A去掉第i行与第j列后的行列式。 矩阵树定理：基尔霍夫矩阵C的任意余子式Mi,i就是图G的生成树个数。 接下来我们尝试证明吧。
先知道基尔霍夫矩阵的性质： 1、|C|=0 容易知道C的每行每列和均为0，那么根据推论4得出行列式也为0。 2、若图G不联通，则任意余子式Mi,i=0 我们进行重标号使联通的点在主对角线上连续。 因此同一个联通块对应了一个基尔霍夫矩阵（除了该联通块内部有边其余均为0）。 显然Mi,i是0，因为去掉任意第i行与第i列后，除i所在联通块的基尔霍夫矩阵外还有其他的基尔霍夫矩阵，而Mi,i等于所有这些矩阵行列式的积（这个易证），根据基尔霍夫矩阵性质1得证。 3、若图G是一颗树，则任意余子式Mi,i=1 未完待续
