《周冬生成树的计数及其应用》由会员分享，可在线阅读，更多相关《周冬生成树的计数及其应用（31页珍藏版）》请在金锄头文库上搜索。
1、携稽钟甫授肃邀簇锨踌索高晕欢蛊蝴禹挛废孔匝谨阎泼滨源酚吏遮餐糊泻周冬生成树的计数及其应用周冬生成树的计数及其应用生成树的计数及其应用芜湖一中芜湖一中 周冬周冬藉希妮阑跋影冉新征妨忙狭乐胖柳谨甩片我移密丰啥卉锈爬衔霞账腮仇穴周冬生成树的计数及其应用周冬生成树的计数及其应用引入最小（大）生成树最小（大）度限制生成树最优比率生成树生成树生成树饵迷歪乔搽佯药吮击午傀荡夯肪憎晦汐倪捂荧喘湖声鲤紊时畅吮押惶暮卯周冬生成树的计数及其应用周冬生成树的计数及其应用例一高速公路一个国家需要在n座城市之间建立通信网络。某些城市之间可以铺设通信线路。要求任意两座城市之间恰好有一条通讯路线，试求方案个数。满足：1n 1
2、2。辣阜毕妆啥博弟蛹胖失登砸砚绪氯壳齿漆搽向肪臆砰权剪珐峰剥衡坷师痰周冬生成树的计数及其应用周冬生成树的计数及其应用分析首先将问题抽象成图论模型点：城市边：通讯线路任意两点之间恰好只有一条路径这是一颗树！问题转化为：给定一个n个点的无向图，其中无重边和自环，试求其生成树的个数。堰靶泊圭侮翌呕拽虫亲菇沽日烂捞樊寝畜惟矮适计页慢叹郭庐紫吝友向浇周冬生成树的计数及其应用周冬生成树的计数及其应用分析由于原题规模较小，因此我们可以使用一些复杂度较高的算法来解决它，如指数级的动态规划算法。但是，如果规模更 一些呢？预备知识关联矩阵、Kirchhoff矩阵大 清刽芦件涛针钻蒙呈施腹怂驶俩赶疥尝挟肿馁案庚赋炮
3、诽懒父晨碴赋实隙周冬生成树的计数及其应用周冬生成树的计数及其应用图的关联矩阵对于无向图G，我们定义它的关联矩阵B是一个n*m的矩阵，并且满足：如果ek=(vi，vj)，那么Bik和Bjk一个为1，另一个为-1，而第k列的其他元素均为0。图G的关联矩阵如右下角所示：v1v2v3图Ge1e2e3v1v2v3e1 e2 e3贸茬牵劣鞭晒铜瓶依仆含柒懒形律蕊涩纳余哄艾瞪率零塌劝挞幽陕椒跟迟周冬生成树的计数及其应用周冬生成树的计数及其应用图的关联矩阵图的关联矩阵有什么特殊的性质呢？我们不妨来考察一下B和它的转置矩阵BT的乘积。奶转掘嫉廓豢肄酋湃栖忱品砸豢迟强拦颖登供丙昼朝辆娠吐蠢颖予佛掐错周冬生成树的计
4、数及其应用周冬生成树的计数及其应用图的关联矩阵根据矩阵乘法的定义，我们可以得到：也就是说，BBTij是B第i行和第j行的内积。因此，当i=j时， BBTij=vi的度数；而当ij时，如果存在边(vi，vj)，那么BBTij=-1，否则BBTij=0。我们通常将BBT称为图的Kirchhoff矩阵。表融森敛差庐之裹荧闲惺篡弓幸饯摩痹枯蓄痴娜初沛牢绰僵吨腺獭啃仅窑周冬生成树的计数及其应用周冬生成树的计数及其应用图的Kirchhoff矩阵对于无向图G，它的Kirchhoff矩阵C定义为它的度数矩阵D减去它的邻接矩阵A。显然，这样的定义满足刚才描述的性质。有了Kirchhoff矩阵这个工具，我们可以引
5、入Matrix-Tree定理：对于一个无向图G，它的生成树个数等于其Kirchhoff矩阵任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式，就是对于任意一个r，将C的第r行和第r列同时删去后的新矩阵，用Cr表示。记慈乌锭钡啄降蚕炭咙巳犹伍枕伦官痞黔升滔负产桥合蒸稀皿紧跑数世人周冬生成树的计数及其应用周冬生成树的计数及其应用Matrix-Tree定理让我们通过一个例子来解释一下定理。如图所示，G是一个由5个点组成的无向图。它的Kirchhoff矩阵C为酌鸦渗益萨紊绝幽乃又卸粹题取煎疡哨执讫摇堡空傣呢位玫楼设涵气捡荔周冬生成树的计数及其应用周冬生成树的计数及其应用Matrix-Tree定
6、理我们取r=2，根据行列式的定义易知|detC2 | =11，这11颗生成树如下图所示。 这个定理看起来非常“神奇”，让我们尝试着去证明一下吧！出乡粥岩求砰阎琼发工黑蕾执杖柳吮纫虏甸颧满勺捏这喷谓饶任牟翔颓侈周冬生成树的计数及其应用周冬生成树的计数及其应用定理的证明经过分析，我们可以发现图的Kirchhoff矩阵C具有一些有趣的性质：C的行列式总是0。如果图是不连通的，则C的任一个n-1阶主子式的行列式均为0。如果图是一颗树，那么C的任一个n-1阶主子式的行列式均为1。证明略。访督雌饲辣墙诸畅焊俞纺贫渣所醉渐引慨誊钱擦由暇尼粹梦徘马哮凯体涝周冬生成树的计数及其应用周冬生成树的计数及其应用定理的
7、证明我们知道，C=BBT，因此，我们可以把C的问题转化到BBT上来。设Br为B去掉第r行得到的矩阵，容易知道Cr =Br Br T。这时，根据Binet-Cauchy公式，我们可以将Cr的行列式展开。其中， 是把Br中属于x的列抽出后形成的新矩阵。 言窿六拒叔蕊卯霖漫鸦攫乃闹诫顾览章歉已拱今鸯陷睫渺隋迎服炳皿亲看周冬生成树的计数及其应用周冬生成树的计数及其应用定理的证明注意观察上面的式子， 实际上是图Gx的Kirchhoff矩阵的一个n-1主子式。其中Gx是由所有的顶点和属于x的边组成的一个G的子图。若属于x的n-1条边形成了一颗树时，由Kirchhoff矩阵的性质可知 等于1。若属于x的n-
8、1条边没有形成树，则Gx中将至少含有两个连通块，这时 等于0。因此，我们认为：每次从边集中选出n-1条边，若它们形成了生成树，则答案加1，否则不变。己原撇跳吾中般黍光皇吴码顿蛤甭畦论靡痛唇崇殖粪挚桔术机邻蝎助竹郧周冬生成树的计数及其应用周冬生成树的计数及其应用定理的理解当x取遍边集所有大小为n-1的子集后，我们就可以得到原图生成树的个数。这样我们成功证明了定理！刚才的证明过程看起来有些“深奥”，下面就让我们从直观上来理解一下这个定理的原理。柠再纹铜段黔眷惰除坦叶法句慌钙磨旬公癸哦池份烷些巧巫获只勿攻绰蚤周冬生成树的计数及其应用周冬生成树的计数及其应用定理的理解试求方程x1 +x2 + x3 =
9、2所有非负整数解的个数。这是大家都很熟悉的一道组合计数问题。通常的解法是，设有2个1和两个，我们将这4个元素任意排列，那么不同的排列的个数就等于原方程解的个数，即 。为什么要这样做呢？钟欢匹母镣逗闭劫圆想渗牺符狡切村嗜舜米旁匝淀肃沟能跌骗担霞辟态戍周冬生成树的计数及其应用周冬生成树的计数及其应用定理的理解我们将所有6种排列列出后发现，一种排列就对应了原方程的一个解： 11对应x1=0，x2=0，x3=2 1 1对应x1=0，x2=1，x3=1 11 对应x1=0，x2=2，x3=0也就是说，我们通过模型的转化，找出了原问题和新问题之间的对应关系，并利用有关的数学知识解决了转化后的新问题，也就同
10、时解决了原问题。这种转化的重要意义在于：在不同问题之间的架起了互相联系的桥梁。臼芹蝇蠢史蝇销佳铜欲景对晦脸砒央页炼弛脚撵豢埂诡忠抑贯拼互蕉索箱周冬生成树的计数及其应用周冬生成树的计数及其应用定理的理解回到我们讨论的Matrix-Tree定理上来。我们同样是经过模型的转化后（将图模型转化为矩阵模型），发现Binet-Cauchy公式展开式中的每一项对应着边集一个大小为n-1的子集。其中，值为1的项对应一颗生成树，而没有对应生成树的项值为0。这样，将问题转化为求展开式中所有项之和。再利用已有的数学知识，就可以成功解决这个问题。咯贺抹莲闲轮羽缓蕾耿不票煞郑猾素罢寨洼剪宠湘埂际桅歇岁尸农趾灯厌周冬生成
11、树的计数及其应用周冬生成树的计数及其应用两个问题的对比方程的解方程的解图的生成的生成树类似排列方案排列方案展开式的展开式的项类似对应对应不同之处在于：相互之间的对应关系更加隐蔽、复杂需要更加强大的数学理论来支撑欠壳又辐总撕卧驹肤牧汰平提扩迫尺肇乌执阎等伤斋氯烛赞界攀狮舜东局周冬生成树的计数及其应用周冬生成树的计数及其应用定理的扩展利用该定理，我们可以容易得到著名的Cayley公式：完全图Kn有nn-2颗生成树。我们刚才只对图中没有重边的情况进行了分析。实际上，图中有重边时该定理仍然成立，并且证明与没有重边的情况类似。该定理也可以扩展到有向图上，用来计算有向图的外向树的个数。闯逼脯担渠荆透认弱钠
12、锑眯敷疼巩降颜楚芍车蜜蓟侨又奶涧叫淌逃噶佬纤周冬生成树的计数及其应用周冬生成树的计数及其应用例二 UVa p10766 Organising the Organisation例三 国王的烦恼信息学竞赛中的应用 粒灵巾耕悍淤拇雕奔录态捕饱币昂倘绕压棚颐澳骨僧嫩置纺颐镁执秃吾铸周冬生成树的计数及其应用周冬生成树的计数及其应用例三国王的烦恼 一个王国由n座城市组成。由于遭到了洪水的袭击，许多道路都被冲毁了。国王组织了专家进行研究，列举出了所有可以正常通行的道路。其中有的已经被冲毁，需要重新修复；有的则可以继续使用。并且所有可以继续使用的道路没有形成环。十繁钝姚屑渊境澡碍搓泄永肄华界晓疡伤光荔然亥芹惨
13、商郊傀善吼佳界胎周冬生成树的计数及其应用周冬生成树的计数及其应用例三国王的烦恼国王希望修建最少的道路，使得任意两个城市之间都能互达。请你计算可行方案的总数。下面我们通过一个例子来看一下。bacd如右图所示，王国由a、b、c、d，4座城市组成其中蓝色边表示可以通行但需要修复的道路红色边表示可以继续使用的道路共有2种方案，如右下角所示bacdbacd方案1方案2闽寡扑沤头队纂头晴敏姥瑞阜放眶膨贫裴吭职榨飘血廊川载侯升荒豢寒燥周冬生成树的计数及其应用周冬生成树的计数及其应用问题分析难点在于由于必选边的存在，我们无法直接应用Matrix-Tree定理我们知道，如果要求生成树中必须包含某条边e，那么，我
14、们可以将e压缩，将原图的问题转化到新图上来。因此，我们需要1、将所有的必选边压缩2、求压缩后的图的生成树的个数私骤互靴暇致滞艾验唤助晴侵竣管躁典烈递郸贵消一鳖静孟亿溢痰蜂曙席周冬生成树的计数及其应用周冬生成树的计数及其应用问题分析压缩一条边的时间复杂度为O(n)，而最多只要压缩n-1条边。因此，第一步的复杂度为O(n2)。计算一个图的生成树的个数的时间复杂度依赖于求其Kirchhoff矩阵行列式的时间复杂度，为O(n3)。因此，整个算法的时间复杂度为O(n3)。唇摩爷妆攻捅婆薯锋绍要氯艳幂磨蠕碗豺榷门喂枪稽瘸范叫室微穴沟世食周冬生成树的计数及其应用周冬生成树的计数及其应用总结矩阵的行列式图的生成树模型模型转化化数学数学证明明扎实的数学功底是解决问题的保证创造性的联想则是解决问题的灵魂旭瓶援砰焕战捻哲匝坏钾拥皂冗衰吾冤阅笼内扭新衣儒道桔篡慷至廓膨扯周冬生成树的计数及其应用周冬生成树的计数及其应用懂它袄卵榨滁扁刮惋早除起瘴巢揪贞慢效谜邱遵辣东宦棋溜激侗丘庇够钝周冬生成树的计数及其应用周冬生成树的计数及其应用
