1. Prufer序列定义
初始序列 \(P = []\)
考虑无根树 \(T(V, E)\) ，每次选择权值最小的节点 \(u\in V\) 使 \(u\) 的度为 \(1\) ，\(p\) 所连的唯一一条边 \((u, v)\) 将 \(v\) 添加到序列 \(P\) 的末尾。然后删除点 \(u\) (即 \(T \leftarrow T'(V - u, E - (u, v))\) ) ，重复操作，直到 \(|V| = 2\) 。
易证该操作一定合法且 \(P\) 长度有限。
以上述操作得到的数字序列 \(P\) 定义为无根树 \(T\) 的Prufer序列。
2. Prufer序列性质
- Prufer序列中任意节点 \(p\) 的出现次数等于 \(p\) 的度减 \(1\) 。
对于任意节点 \(p\) ，节点 \(p\) 每在序列 \(P\) 中出现一次都意味着 \(p\) 所连向的一条边会在上述操作中被删除，那么节点 \(p\) 的度数会减少 \(1\) ，最终当节点 \(p\) 的度数为 \(1\) 时则不会再在 \(P\) 中出现（因为操作中任意度为 \(1\) 的节点所连向的都不可能是度为 \(1\) 的节点，否则整棵树就只有这两个节点，与终止条件 \(|V| = 2\) 矛盾），因此出现次数等于度数减 \(1\) 。 -
- 任意Prufer序列 \(P\) 有且仅有唯一的无根树与之对应。
考虑构造一个树 \(T(V, E)\) 使 \(P\) 是 \(T\) 的Prufer序列。 - 任意整数序列 \(P\) 满足 \(\forall p \in P, p\in [1, |P| + 2]\) 是Prufer序列。
- 任意Prufer序列 \(P\) 有且仅有唯一的无根树与之对应。