Matlab实现生成树计数

Matlab实现生成树计数摘要在信息学竞赛中，有关生成树的最优化问题如最小生成树等是我们经常遇到的，而对生成树的计数及其相关问题则少有涉及。事实上，生成树的计数是十分有意义的，在许多方面都有着广泛的应用。本文首先介绍了行列式的基本概念、性质，并在此基础上引入MatrixTree定理。关键字：生成树的计数、MatrixTree定理MatrixTree定理(Kirchhoff矩阵-树定理)。MatrixTree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念：1、G的度数矩阵DG是一个n阶矩阵，并且满足：0;().ijGiijddvij，()Gidv为顶点iv的度数（度数即与顶点iv关联的边的个数）。2、G的邻接矩阵AG也是一个n阶矩阵，并且满足：01ijijijvvavv；；没直接连接直接连接我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)CG为CGDGAG，则MatrixTree定理可以描述为：G的所有不同的生成树的个数等于其Kirchhoff矩阵CG任何一个1n阶主子式的行列式的绝对值。所谓1n阶主子式，就是对于1rrn，将CG的第r行、第r列同时去掉后得到的新矩阵，用CrG表示。Matlab程序：functionn=STREEC(D,A)C=D-A;n=size(C);C(:,n)=[];%删除矩阵C的第n列C(n,:)=[];%删除矩阵C的第n行，形成了Cr，为了节约空间，这里没有定义新的变量Cr,用C代替Crn=abs(det(C));%这里C表示Cr.end