| [reply] |

That was actually the first thing I googled for. Apparently, though, "Prufer" is the more common Anglicism, and neither produced any useful introductory documents.
So what the hell, I'll give it a shot.
The idea is to generate a unique sequence for each labelled tree on N vertices. What you end up doing is removing vertices one at a time, starting with the highest label leaf vertex (you can start with the lowest, it doesn't matter, as long as you're consistent). When you remove a vertex, you add the label of *the vertex it was adjacent to* to the sequence. Keep going until you only have two vertices left. You've got a Prüfer sequence!
So, for example, if you have the tree:
` 1--3--2--4
|\
| 5
6
`
You'd start by removing vertex 6 (highest label leaf vertex). Add 3 to the Prüfer sequence (which is now 3), and you have the tree:
` 1--3--2--4
\
5
`
Now remove 5 and add 3, you have (3, 3) and the tree:
` 1--3--2--4
`
Remove 4, add 2, you get (3, 3, 2) -- eventually, you end up with (3, 3, 2, 3) and the tree `1--3`.
It turns out that there's a one-to-one correspondence between labelled trees and Prüfer sequences, so each Prüfer sequence uniquely determines a tree. (Which is why the code I posted earlier works.)
Going from a Prüfer sequence to a tree is left as an exercise for the reader. :-)
`-- `
F
o
x
t
r
o
t
U
n
i
f
o
r
m
Found a typo in this node? /msg me
The hell with paco, vote for Erudil!
| [reply] [d/l] [select] |