《Matlab实现生成树计数》由会员分享，可在线阅读，更多相关《Matlab实现生成树计数（1页珍藏版）》请在金锄头文库上搜索。
1、Matlab实现生成树计数摘要在信息学竞赛中，有关生成树的最优化问题如最小生成树等是我们经常遇到的，而对生 成树的计数及其相关问题则少有涉及。事实上，生成树的计数是十分有意义的，在许多方面 都有着广泛的应用。本文首先介绍了行列式的基本概念、性质，并在此基础上引入 Matrix Tree 定理。关键字：生成树的计数、Matrix-Tree定理Matrix-Tree定理（Kirchhoff矩阵-树定理）。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先0d (v )G ii = j；i丰j.明确几个概念:1、G的度
2、数矩阵DG是一个n阶矩阵，并且满足：d = ijv v没直接连接;I jv v直接连接;I j顶点v的度数（度数即与顶点V关联的边的个数）。 ii2、G的邻接矩阵AG也是一个n阶矩阵，并且满足：a =ij我们定义G的Kirchhoff矩阵（也称为拉普拉斯算子）CG为C G =DG AG，则Matrix Tree定理可以描述为：G的所有不同的生成树的个数等于其Kirchhoff矩阵CG任何一个n 1阶主子式的行列式的绝对值。所谓n 1阶主子式,就是对于r（1 r n），将CG的第r行、第r列同时去掉后得到的新矩阵，用Cr G 表示。Matlab程序:n=size(C);C(:,n)=;%删除矩阵C的第n列C(n,:)=;%删除矩阵C的第n行,变量Cr，用C代替Crn=abs(det(C);%这里C表示Cr.function n=STREEC( D,A ) C=D-A;end形成了Cr,为了节约空间，这里没有定义新的
