算法合集之《生成树的计数及其应用》

《算法合集之《生成树的计数及其应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、生成树的计数及其应用芜湖一中周冬引入最小（大）生成树最小（大）度限制生成树最优比率生成树……生成树生成树的计数[例一]高速公路一个国家需要在n座城市之间建立通信网络。某些城市之间可以铺设通信线路。要求任意两座城市之间恰好有一条通讯路线，试求方案个数。满足：1≤n≤12。分析首先将问题抽象成图论模型点：城市边：通讯线路任意两点之间恰好只有一条路径这是一颗树！问题转化为：给定一个n个点的无向图，其中无重边和自环，试求其生成树的个数。分析由于原题规模较小，因此我们可以使用一些复杂度较高的算法来解决它，如指数级的动态规划算法。但是，如果规模更一

2、些呢？预备知识关联矩阵、Kirchhoff矩阵大图的关联矩阵对于无向图G，我们定义它的关联矩阵B是一个n*m的矩阵，并且满足：如果ek=(vi，vj)，那么Bik和Bjk一个为1，另一个为-1，而第k列的其他元素均为0。图G的关联矩阵如右下角所示：v1v2v3图Ge1e2e3v1v2v3e1e2e3图的关联矩阵图的关联矩阵有什么特殊的性质呢？我们不妨来考察一下B和它的转置矩阵BT的乘积。图的关联矩阵根据矩阵乘法的定义，我们可以得到：也就是说，BBTij是B第i行和第j行的内积。因此，当i=j时，BBTij=vi的度数；而当i≠j时，如果

3、存在边(vi，vj)，那么BBTij=-1，否则BBTij=0。我们通常将BBT称为图的Kirchhoff矩阵。图的Kirchhoff矩阵对于无向图G，它的Kirchhoff矩阵C定义为它的度数矩阵D减去它的邻接矩阵A。显然，这样的定义满足刚才描述的性质。有了Kirchhoff矩阵这个工具，我们可以引入Matrix-Tree定理：对于一个无向图G，它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式，就是对于任意一个r，将C的第r行和第r列同时删去后的新矩阵，用Cr表示。Matrix-Tr

4、ee定理让我们通过一个例子来解释一下定理。如图所示，G是一个由5个点组成的无向图。它的Kirchhoff矩阵C为Matrix-Tree定理我们取r=2，根据行列式的定义易知

5、detC2

6、=11，这11颗生成树如下图所示。这个定理看起来非常“神奇”，让我们尝试着去证明一下吧！定理的证明经过分析，我们可以发现图的Kirchhoff矩阵C具有一些有趣的性质：C的行列式总是0。如果图是不连通的，则C的任一个n-1阶主子式的行列式均为0。如果图是一颗树，那么C的任一个n-1阶主子式的行列式均为1。证明略。定理的证明我们知道，C=BBT，因此，我们

7、可以把C的问题转化到BBT上来。设Br为B去掉第r行得到的矩阵，容易知道Cr=BrBrT。这时，根据Binet-Cauchy公式，我们可以将Cr的行列式展开。其中，是把Br中属于x的列抽出后形成的新矩阵。定理的证明注意观察上面的式子，实际上是图Gx的Kirchhoff矩阵的一个n-1主子式。其中Gx是由所有的顶点和属于x的边组成的一个G的子图。若属于x的n-1条边形成了一颗树时，由Kirchhoff矩阵的性质可知等于1。若属于x的n-1条边没有形成树，则Gx中将至少含有两个连通块，这时等于0。因此，我们认为：每次从边集中选出n-1条边，

8、若它们形成了生成树，则答案加1，否则不变。定理的理解当x取遍边集所有大小为n-1的子集后，我们就可以得到原图生成树的个数。这样我们成功证明了定理！刚才的证明过程看起来有些“深奥”，下面就让我们从直观上来理解一下这个定理的原理。定理的理解试求方程x1+x2+x3=2所有非负整数解的个数。这是大家都很熟悉的一道组合计数问题。通常的解法是，设有2个1和两个△，我们将这4个元素任意排列，那么不同的排列的个数就等于原方程解的个数，即。为什么要这样做呢？定理的理解我们将所有6种排列列出后发现，一种排列就对应了原方程的一个解：△△11对应x1=0，x

9、2=0，x3=2△1△1对应x1=0，x2=1，x3=1△11△对应x1=0，x2=2，x3=0……也就是说，我们通过模型的转化，找出了原问题和新问题之间的对应关系，并利用有关的数学知识解决了转化后的新问题，也就同时解决了原问题。这种转化的重要意义在于：在不同问题之间的架起了互相联系的桥梁。定理的理解回到我们讨论的Matrix-Tree定理上来。我们同样是经过模型的转化后（将图模型转化为矩阵模型），发现Binet-Cauchy公式展开式中的每一项对应着边集一个大小为n-1的子集。其中，值为1的项对应一颗生成树，而没有对应生成树的项值为0

10、。这样，将问题转化为求展开式中所有项之和。再利用已有的数学知识，就可以成功解决这个问题。两个问题的对比方程的解图的生成树类似排列方案展开式的项类似对应对应不同之处在于：相互之间的对应关系更加隐蔽、复杂需要更