Talk:Prüfer sequence

Latest comment: 6 years ago by Smalltalk2520 in topic Pseudocode

The figure on this page is not very useful for someone trying to understand Prüfer sequences. I believe it is too simple.

For instance, how would one proceed if the nodes labelled 3 and 4 were relabelled 4 and 3? Would the sequence then be 3335, or 3345? I presume the former because the later would result in a disconnected graph? It would be helpful if this were made explicit.

Ray 06:06, 26 February 2006 (UTC)Reply

It says explicitly "remove the leaf with the smallest label". Therefore there is no ambiguity.


How you get the tree from the code? 150.244.52.8 (talk) 16:34, 19 January 2008 (UTC)Reply


In the "Other Applications" section, there appears to be a mistake: in a complete n-order graph, every vertex has degree n-1. --Matt mcgill 15:44, 15 October 2007 (UTC)Reply

Proof there is a 1-1 corespondence

edit

Is someone willing to write the proof that indeed, each tree gets it own Prüfer sequence thus giving a injection? Stdazi (talk) 17:47, 19 June 2008 (UTC)Reply

Removed merge proposal

edit

I removed the merge proposal because Prüfer's code is entirely different concept than the one employed in Cayley's proof. —Preceding unsigned comment added by 86.3.42.126 (talk) 13:55, 14 August 2008 (UTC)Reply

Pseudocode

edit

That's not pseudo code, that's C without types. Tsuihark (talk) 21:24, 3 March 2009 (UTC)Reply


I tried to remedy that (and also put in an algorithm that works). aibyou_chan (talk) 22:26, 10 February 2010 (UTC)Reply


on line 10 of pseudocode, should we also check i's degree is greater than 1? writing a closely related program (https://open.kattis.com/problems/chopwood) and i thought that's the way you do it. Smalltalk2520 (talk) 02:31, 2 June 2018 (UTC)Reply

Algorithm to convert a Prüfer sequence into a tree

edit

For those interested, the French article proposes a second method to do the decoding. The array of degrees is replaced with an array of nodes that have not been examined yet.

In the hope that helps, --MathsPoetry (talk) 12:43, 16 March 2012 (UTC)Reply