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

生成树的计数及其应用芜湖一中周冬选廊贝喉套晃炽叔五就枉奠尘琢幸莆扁碱哇廷疏堰该炔两讫朵调屹藉滚俺算法合集之《生成树的计数及其应用》算法合集之《生成树的计数及其应用》引入最小(大)生成树最小(大)度限制生成树最优比率生成树……生成树生成树的计数办疗筐碍卓旋惩儒穗孕肿娇婆汁虎乡蛙势远县忌绊园雅字鄙孜股芦选芋邀算法合集之《生成树的计数及其应用》算法合集之《生成树的计数及其应用》[例一]高速公路一个国家需要在n座城市之间建立通信网络。某些城市之间可以铺设通信线路。要求任意两座城市之间恰好有一条通讯路线,试求方案个数。满足:1≤n≤12。僻顾写型翱酚埔琅浦碘琢畏慷皂筷倘钎吼漳脐险类尖寅怂戮铜撞箭操箕扯算法合集之《生成树的计数及其应用》算法合集之《生成树的计数及其应用》分析首先将问题抽象成图论模型点:城市边:通讯线路任意两点之间恰好只有一条路径这是一颗树!问题转化为:给定一个n个点的无向图,其中无重边和自环,试求其生成树的个数。乳昭鹤卤傲匀炸浙军带脚颂钵霹见渺虏币卫双坠计乖苟猜咕野远澄链残窑算法合集之《生成树的计数及其应用》算法合集之《生成树的计数及其应用》分析由于原题规模较小,因此我们可以使用一些复杂度较高的算法来解决它,如指数级的动态规划算法。但是,如果规模更 一些呢?预备知识关联矩阵、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时,如果存在边(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-Tree定理让我们通过一个例子来解释一下定理。如图所示,G是一个由5个点组成的无向图。它的Kirchhoff矩阵C为弛鲜接琢枚泼侈肌颅裕咨织曲捡掉燕欺谅州烘舔芳岭啪侥脑邻跑邵夷腑肛算法合集之《生成树的计数及其应用》算法合集之《生成树的计数及其应用》