prufer序列笔记
2024-09-09 09:08:05
prufer序列
度娘的定义
Prufer数列是无根树的一种数列。在组合数学中,Prufer数列由有一个对于顶点标过号的树转化来的数列,点数为n的树转化来的Prufer数列长度为n-2。
对于一棵确定的无根树,对应着唯一确定的prufer序列
构造方法
无根树转化为prufer序列
- 找到编号最小的度数为\(1\)的点
- 删除该节点并在序列中添加与该节点相连的节点的编号
- 重复\(1,2\)操作,直到整棵树只剩下两个节点
如下图的prufer序列为\(3,5,1,3\)
prufer序列转化为无根树
- 每次取出prufer序列中最前面的元素\(u\)
- 在点集中找到编号最小的没有在prufer序列中出现的元素\(v\)
- 给\(u,v\)连边然后分别删除
- 最后在点集中剩下两个节点,给它们连边
例如,对于prufer序列\(3,5,1,3\)
连边顺序为
\(2,3\),
\(5,4\),
\(1,5\),
\(3,1\),
\(3,6\)
(实际上与构建prufer序列时相同)
以上两种操作都可以用set维护,时间复杂度\(O(nlogn)\)
性质
prufer序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数-1
一棵n个节点的无根树唯一地对应了一个长度为n-2的数列,数列中的每个数都在1到n的范围内。
\(n\)个点的无向完全图的生成树的计数:\(n^{(n-2)}\),即\(n\)个点的有标号无根树的计数
- n个节点的度依次为\(d_1,d_2,…,d_n\)的无根树共有\(\frac{(n-2)!}{ \prod_{i=1}^n(d_i-1)!}\)个,因为此时Prufer编码中的数字\(i\)恰好出现\(d_i-1\)次,\((n−2)!\)是总排列数
n个点的 有标号有根树的计数:\(n^{(n-2)}*n = n^{(n-1)}\)
暂且写这些吧,先做做题,然后继续整理
最新文章
- 基于轻量型Web服务器Raspkate的RESTful API的实现
- Android Studio解决未识别Java文件(出现红J)问题
- web前端性能优化指南(转)
- JAVA中SERIALVERSIONUID的解释
- AX 2012 在Grid 中添加image标识状态
- 研华外触发实验PCI1714板卡安装事项
- [moka收藏]php正则表达式验证
- C#抽象类及其方法的学习
- 在keil 4中添加stc系列芯片的方法--【sky原创】
- flex数据交互方式 转
- 黑马程序员-hashtable
- maven简单工具命令
- kotlin, 一种新的android平台一级开发语言
- iKcamp出品|全网最新|微信小程序|基于最新版1.0开发者工具之初中级培训教程分享
- linux ftp及C/S服务架构
- zookeeper的搭建和简单的使用
- little kernel 小结
- 1: Myeclipse10 优化设置
- leetcode题库解答源码(python3)
- git reset与git revert比較
热门文章
- Linux下CenOS系统 安装Redis
- Android APK 瘦身 - JOOX Music项目实战
- IIS集中化管理与编程REST API
- 【DFS】n皇后问题
- [Swift]LeetCode7. 反转整数 | Reverse Integer
- [Swift]LeetCode473. 火柴拼正方形 | Matchsticks to Square
- [Swift]LeetCode680. 验证回文字符串 Ⅱ | Valid Palindrome II
- TLS 1.3 VS TLS 1.2,让你明白 TLS 1.3 的强大
- oracle常用命令收集
- Elasticsearch 分词器