算法合集之《生成树的计数及其应用》.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为升虑谣斟馁档污量拄额梁萄并椽塌蝶锁诫洼峡募蕴青送挎谗苦姑基斤诊敝算法合集之《生成树的计数及其应用》算法合集之《生成树的计数及其应用》