Prüfer Labeled Tree Codes
Remove the smallest leaf to encode a labeled tree and reconstruct it exactly.
Free theory articleRemove the smallest leaf to encode a labeled tree and reconstruct it exactly.
Concept & interpretation
A Prüfer sequence is a unique sequence of integers associated with a labeled tree. For a tree with n vertices labeled 0 to n-1, the sequence has length n-2. This establishes a bijection between labeled trees and length n-2 sequences.
Experiment
Explore the presets using the interactive module:
- Select the Interactive Module and choose the "Path five" preset.
- Observe the computed degree array: `1, 2, 2, 2, 1` which is typical for a path graph.
- Select the "Star five" preset and notice that the center node has a high degree while all others are leaves with degree 1.
- Check the boundary cases such as "Pair", which has an empty Prüfer sequence.