526互联

Prüfer 序列

发布时间 2023-07-04 19:10:19作者: qzhwlzy

简介

Prüfer 序列（以下为方便写作 “prufer 序列”）可以将一个带标号的 \(n\) 个结点的树用 \([1,n]\) 中的 \(n-2\) 个整数表示，也可以理解为完全图的生成树与数列之间的双射。

定义

prufer 序列的简历过程为：选取树中所有叶子节点中编号最小的，将其的父节点加入序列末并删除该叶子节点。重复直至只剩最后两个节点。