生成树
1.Prufer序列
- 对于一棵顶点已经经过编号的树T,顶点的编号为(1,…n),在第i步时，移去所有叶子结点（度为1的结点）中标号最小的顶点和相连的边（包括树根），并把与它相邻的点的编号加入 Purfer 序列中，重复以上步骤直到原图仅剩余2个顶点。
- 一个长度为n-2的$Purfer$序列，唯一对应一棵n个点固定形态的无根树
- 构造序列方法：
- 1.先找到编号最小的叶子结点，设其为 P
- 2.将 P 的父节点 F 加入序列
- 3.若删去 P 后，$F$ 结点变为叶子结点，且 $F < P$，此时可以将f直接选为新的叶子结点进行操作，(因为 P 已经是最小的叶子结点了，$F $是新增的叶子结点且 F 比 P 的编号更小，所以直接选中 F )
- 4.一直执行3直到找不到满足条件的 F ,再执行 1
- ( 复杂度 O(n) )
-
一些性质：
-
1、在构造完 Prufer 序列后原树中会剩下两个节点，其中一个一定是编号最大的点 n。
证明：一棵 结点数≥2 的无根树中必定存在两个叶子结点，所以最大的点必定不会
-
2、每个节点在序列中出现的次数是其度数减 1，因此没有出现的就是叶节点。
证明：该结点所连接的各个叶子结点会被弹出，而最后会留下一个叶子结点（因为最后留两个点）
-
题目：
左边有m个点，右边有n个点，仅允许左边向右边连边，求生成树的方案
我的想法：$(n+m-1)*…*n$
2.最小生成树
1.Kruscal
Kruscal重构树
· 在Kruscal过程中每当选出一条新边时，就让它作为连接的两个点\的父亲， 点权为那个边权
· 一个性质：比本点小的点一定在其子树内
· 原因：选点相当于选择边
CF1120D 一道上课讲的题
astyd
CF888T