周冬生成树的计数及其应用.ppt
《周冬生成树的计数及其应用.ppt》由会员分享,可在线阅读,更多相关《周冬生成树的计数及其应用.ppt(31页珍藏版)》请在三一文库上搜索。
1、生成树的计数及其应用,芜湖一中 周冬,引入,最小(大)生成树 最小(大)度限制生成树 最优比率生成树 ,生成树,生成树的计数,例一高速公路,一个国家需要在n座城市之间建立通信网络。 某些城市之间可以铺设通信线路。 要求任意两座城市之间恰好有一条通讯路线,试求方案个数。 满足:1n 12。,分析,首先将问题抽象成图论模型 点:城市 边:通讯线路 任意两点之间恰好只有一条路径 这是一颗树! 问题转化为:给定一个n个点的无向图,其中无重边和自环,试求其生成树的个数。,分析,由于原题规模较小,因此我们可以使用一些复杂度较高的算法来解决它,如指数级的动态规划算法。 但是,如果规模更 一些呢? 预备知识
2、关联矩阵、Kirchhoff矩阵,大,图的关联矩阵,对于无向图G,我们定义它的关联矩阵B是一个n*m的矩阵,并且满足: 如果ek=(vi,vj),那么Bik和Bjk一个为1,另一个为-1,而第k列的其他元素均为0。 图G的关联矩阵如右下角所示:,图的关联矩阵,图的关联矩阵有什么特殊的性质呢?我们不妨来考察一下B和它的转置矩阵BT的乘积。,图的关联矩阵,根据矩阵乘法的定义,我们可以得到: 也就是说,BBTij是B第i行和第j行的内积。 因此,当i=j时, BBTij=vi的度数;而当ij时,如果存在边(vi,vj),那么BBTij=-1,否则BBTij=0。 我们通常将BBT称为图的Kirchh
3、off矩阵。,图的Kirchhoff矩阵,对于无向图G,它的Kirchhoff矩阵C定义为它的度数矩阵D减去它的邻接矩阵A。显然,这样的定义满足刚才描述的性质。 有了Kirchhoff矩阵这个工具,我们可以引入Matrix-Tree定理: 对于一个无向图G,它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。 所谓n-1阶主子式,就是对于任意一个r,将C的第r行和第r列同时删去后的新矩阵,用Cr表示。,Matrix-Tree定理,让我们通过一个例子来解释一下定理。如图所示,G是一个由5个点组成的无向图。 它的Kirchhoff矩阵C为,Matrix-Tree定理,
4、我们取r=2,根据行列式的定义易知|detC2 | =11,这11颗生成树如下图所示。,这个定理看起来非常“神奇”,让我们尝试着去证明一下吧!,定理的证明,经过分析,我们可以发现图的Kirchhoff矩阵C具有一些有趣的性质: C的行列式总是0。 如果图是不连通的,则C的任一个n-1阶主子式的行列式均为0。 如果图是一颗树,那么C的任一个n-1阶主子式的行列式均为1。 证明略。,定理的证明,我们知道,C=BBT,因此,我们可以把C的问题转化到BBT上来。 设Br为B去掉第r行得到的矩阵,容易知道Cr =Br Br T。这时,根据Binet-Cauchy公式,我们可以将Cr的行列式展开。 其中,
5、 是把Br中属于x的列抽出后形成的新矩阵。,定理的证明,注意观察上面的式子, 实际上是图Gx的Kirchhoff矩阵的一个n-1主子式。其中Gx是由所有的顶点和属于x的边组成的一个G的子图。,若属于x的n-1条边形成了一颗树时,由Kirchhoff矩阵的性质可知 等于1。 若属于x的n-1条边没有形成树,则Gx中将至少含有两个连通块,这时 等于0。 因此,我们认为:每次从边集中选出n-1条边,若它们形成了生成树,则答案加1,否则不变。,定理的理解,当x取遍边集所有大小为n-1的子集后,我们就可以得到原图生成树的个数。这样我们成功证明了定理! 刚才的证明过程看起来有些“深奥”,下面就让我们从直观
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 生成 计数 及其 应用
链接地址:https://www.31doc.com/p-2723331.html