Prüfer序列和cayley定理
参考资料:
1.matrix67 《经典证明:Prüfer编码与Cayley公式》
2.百度百科
3.Forget_forever prufer序列总结
4.维基百科
5.dirge的学习笔记
一、Cayley定理
我们先讲讲Cayley公式/定理?。
凯莱定理,是所有群 G 同构于在 G 上的对称群的子群。
什么鬼?!
其实定理还有另一种表述:过n个有标志顶点的树的数目等于n^(n-2),也即完全图K_n有n^(n-2)棵生成树。
此定理说明用n-1条边将n个一致的顶点连接起来的连通图的个数为n^(n-2),也可以这样理解,将n个城市连接起来的树状公路网络有n^(n-2)种方案。所谓树状,指的是用n-1条边将n个顶点构成一个连通图。当然,建造一个树状的公路网络将n个城市连接起来,应求其中长度最短、造价最省的一种,或效益最大的一种。Cayley定理只是说明可能方案的数目。
matrix67给出的用Prüfer序列证明Cayley定理的方式,第一步就是将树转换为Prüfer序列。
第一步:一种生成Prufer序列的方法是迭代删点,直到原图仅剩两个点。对于一棵顶点已经经过编号的树T,顶点的编号为{1,2,...,n},在第i步时,移去所有叶子节点(度为1的顶点)中标号最小的顶点和相连的边,并把与它相邻的点的编号加入Prufer序列中,重复以上步骤直到原图仅剩2个顶点。
摘自百度的例子:
以右边的树为例子,首先在所有叶子节点中编号最小的点是2,和它相邻的点的编号是3,将3加入序列并删除编号为2的点。接下来删除的点是4,5被加入序列,然后删除5,1被加入序列,1被删除,3被加入序列,此时原图仅剩两个点(即3和6),Prufer序列构建完成,为{3,5,1,3}。
二、Prüfer序列和cayley定理的推广和应用
1.(前言)有了这个好东西,我们可以直接得出n个点无向完全图的生成树计数。同时地,生成树问题就可以通过这一过程转化为排列组合问题了。
2.(推广1)Prüfer序列的性质:序列中某个编号的出现次数和此节点在无根树中的度数-1。这是不证自明的,看看步骤中的操作和最后仅剩2个点就停止的限定就可以简单得出了,是举不出反例的(不懂证明._.)。
3.(推广2)一个有趣的推广是,n个节点的度依次为D1, D2, …, Dn的无根树共有(n-2)! / [ (D1-1)!(D2-1)!..(Dn-1)! ]个,因为根据推广1此时Prüfer编码中的数字i恰好出现Di-1次。即n种元素,共n-2个位置来生成一个Prüfer序列(当然同时就生成了一棵与之对应的树),其中第i种元素有di-1个,求排列数。也就是将n-2个元素全排列后去重一下,这就是对公式中分母分子的理解了。
4.(来自bzoj1005明明的烦恼)n个节点的度依次为D1,D2...Dk,令有m个节点度数未知,求生成树计数。记已知点i个度数为di,有n个节点,m个未知数,那么剩下的游离度(我自己yy出的名词)为left=(n-2)-(d1-1)-(d2-1)-...-(dk-1)。有了之前巨大武器,可以简单地从一个组合推到一棵树,那么已知度数的节点可能的组合方式是:(n-2)!/[(d1-1)!(d2-1)!...(dk-1)!left!],那么此时剩下的left个可以用未知度数的节点随意填补,方案数为m^left(说明:即当前剩下了m个节点,考虑left个游离度的每一个度,与之一一对应的有m种情况,也就是left个关卡,每个关卡有m个选择咯)。最后得出ans=(n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left! * m^left
附:对这题,网上做法不一,一般是生成个质数表+暴力分解质因数+高精度来解决。
具体代码看我的博文吧,其实网上也很多
最新文章
- NetBeans建立跳过测试构建的快捷方式
- Tomcat不输入项目名进入自己项目(根目录指向自己的项目)
- JavaScript中 Promise的学习以及使用
- vsftp虚拟用户配置
- C++ 方法隐藏
- json的序列化和反序列化支持时间格式转换
- Centos6.6上源码安装Nodejs V4版本
- Codeforces 1120D Power Tree [最小生成树]
- 音频音乐播放 Service
- Web大前端面试题-Day9
- Android 开发规范
- java SE 入门之语言与环境(第一篇)
- CentOS使用EPEL YUM源
- programming-languages学习笔记--第7部分
- chrome 设置启动时打开特定一组网页
- RequestMaping url带参数及参数带“.";的解决办法
- 无归档情况下使用BBED处理ORA-01113错误
- TypeScript 映射类型
- puclic 页面公共CSS样式
- Python内置函数:read()
热门文章
- 认识BACnet协议
- Parameterized testing with any Python test framework
- 【洛谷3345_BZOJ3924】[ZJOI2015]幻想乡战略游戏(点分树)
- ASP.NET GridView 控件绑定 CheckBoxList
- PS如何批量整理图片大下
- leetcode377 Combination Sum IV
- Android学习笔记(五)Android框架
- 本地调试hbase
- 最优化方法系列:Adam+SGD—>AMSGrad
- 没搞错吧,我只是个web前端工程师,不是manager,也不是leader...