算法合集之《生成树计数其应用》.ppt

生成树的计数及其应用生成树的计数及其应用芜湖一中芜湖一中周冬周冬引入引入最小(大)生成树最小(大)度限制生成树最优比率生成树……生成树[ [例一例一] ]高速公路高速公路?一个国家需要在 n座城市之间建立通信网络。?某些城市之间可以铺设通信线路。?要求任意两座城市之间恰好有一条通讯路线,试求方案个数。?满足: 1≤ n ≤ 12 。分析分析?首先将问题抽象成图论模型–点:城市–边:通讯线路?任意两点之间恰好只有一条路径–这是一颗树! ?问题转化为:给定一个 n个点的无向图,其中无重边和自环,试求其生成树的个数。分析分析?由于原题规模较小,因此我们可以使用一些复杂度较高的算法来解决它,如指数级的动态规划算法。?但是,如果规模更一些呢? ?预备知识关联矩阵、 Kirchhoff 矩阵大图的关联矩阵图的关联矩阵?对于无向图 G,我们定义它的关联矩阵 B是一个 n*m的矩阵,并且满足: –如果 e k=(v i,v j),那么 B ik和B jk一个为 1,另一个为-1 ,而第 k列的其他元素均为 0。?图G的关联矩阵如右下角所示: v 1v 2v 3 图Ge 1e 2e 3?????????????110 101 011v 1v 2v 3e 1e 2e 3图的关联矩阵图的关联矩阵?图的关联矩阵有什么特殊的性质呢? 我们不妨来考察一下 B和它的转置矩阵 B T的乘积。图的关联矩阵图的关联矩阵?根据矩阵乘法的定义,我们可以得到: ?也就是说, BB T ij是B第i行和第 j行的内积。?因此,当 i=j时, BB T ij=v i的度数;而当 i≠j时,如果存在边(v i,v j),那么 BB T ij =- 1,否则 BB T ij =0 。?我们通常将 BB T称为图的 Kirchhoff 矩阵。?????? mk jk ik mk kj T ik ijBBBB BB T1 1图的图的 Kirchhoff Kirchhoff 矩阵矩阵?对于无向图 G,它的 Kirchhoff 矩阵 C定义为它的度数矩阵 D减去它的邻接矩阵 A。显然,这样的定义满足刚才描述的性质。?有了 Kirchhoff 矩阵这个工具,我们可以引入 Matrix-Tree 定理: –对于一个无向图 G,它的生成树个数等于其 Kirchhoff 矩阵任何一个 n -1 阶主子式的行列式的绝对值。–所谓 n -1 阶主子式,就是对于任意一个 r,将 C的第 r行和第 r列同时删去后的新矩阵,用 C r表示。 Matrix-Tree Matrix-Tree 定理定理?让我们通过一个例子来解释一下定理。如图所示, G是一个由 5个点组成的无向图。?它的 Kirchhoff 矩阵 C为????????????????????????????21100 12010 10311 01131 00112