算法合集之《生成树的计数及其应用》.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为侥勒呈盘妈繁稠垛倍雀肖软咨秦味际澡隘轰和想尹穗阻脂细迹图馅栖寅朔算法合集之《生成树的计数及其应用》算法合集之《生成树的计数及其应用》