prufer编码与Cayley公式学习(洛谷P4430 小猴打架)

purfer 编码

purfer编码是一种无根树的表示方式,对于一棵无根树,有着为一的prufer编码。如何把一棵树转化成为purfer编码呢?我们用删点乱搞 的方式。在第i步时,移去所有叶子节点中标号最小的顶点和相连的边,并把与它相邻的点的编号加入Prufer序列中,重复以上步骤直到原图仅剩2个顶点。

将Prufer数列转化成树的方法:
设{a1,a2,…an-2}为一棵有n个节点的树的Prufer序列,另建一个集合G含有元素{1…n},找出集合中最小的未在Prufer序列中出现过的数,将该点与Prufer序列中首项连一条边,并将该点和Prufer序列首项删除,重复操作n-2次,将集合中剩余的两个点之间连边即可。

Cayley公式:n个节点带标号的无根树有n^(n-2)个。

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-07 18:24
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议