code that produces all possible trees with n nodes. - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-19T13:30:30Z http://mathoverflow.net/feeds/question/52371 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52371/code-that-produces-all-possible-trees-with-n-nodes code that produces all possible trees with n nodes. marvin 2011-01-18T02:34:35Z 2011-01-18T15:09:43Z <p>I'm looking for code that produces all possible trees with no self edges (or their adjacent matrices) with n nodes, anyone have any idea if this is written anywhere? </p> http://mathoverflow.net/questions/52371/code-that-produces-all-possible-trees-with-n-nodes/52374#52374 Answer by Chris Godsil for code that produces all possible trees with n nodes. Chris Godsil 2011-01-18T02:58:24Z 2011-01-18T02:58:24Z <p>In sage the command </p> <p>list(graphs.trees(9)) </p> <p>produces a list of all trees on 9 vertices. As sage is open source, the code is available for inspection. The command</p> <p>[tt.am() for tt in graphs.trees(9)]</p> <p>will provide the adjacency matrices.</p> http://mathoverflow.net/questions/52371/code-that-produces-all-possible-trees-with-n-nodes/52411#52411 Answer by Tony Huynh for code that produces all possible trees with n nodes. Tony Huynh 2011-01-18T15:09:43Z 2011-01-18T15:09:43Z <p>It is well known that there is a bijection between the set of trees on \$n\$ nodes and sequences of length \$n-2\$ with values in \$[n]\$. These sequences are called <a href="http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence" rel="nofollow">Prüfer sequences</a>. Indeed, the wikipedia page has code which will convert any Prüfer sequence into a tree. So a naïve algorithm would be to run the wikipedia algorithm over all Prüfer sequences. </p>