Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Random Trees

by dmitri (Curate)
on Feb 11, 2003 at 20:16 UTC ( #234519=note: print w/ replies, xml ) Need Help??


in reply to Random Trees

++. As far as your "googly" comments go, you can substitute German umlaut letters with that letter followed by 'e', so Prüfer becomes Pruefer:

http://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=pruefer+trees&btnG=Google+Search


Comment on Re: Random Trees
Re(2): Random Trees
by FoxtrotUniform (Prior) on Feb 11, 2003 at 21:10 UTC

    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!

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://234519]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (19)
As of 2014-07-31 14:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (249 votes), past polls