1
$\begingroup$

How can one generate all unlabeled trees with $\le n$ nodes?

That is, generate and store the adjacency matrices of those graphs? (not just count them)

Visualization of all unlabeled trees with $\le6$ nodes:

enter image description here

$\endgroup$
1
$\begingroup$

Start by considering rooted trees parametrised by vertex count and depth. These have an obvious recursive construction: a rooted tree of one vertex has depth $0$; a rooted tree of $n > 1$ vertices and depth $d \ge 1$ has a root and its children; at least one child has depth $d-1$, no child has depth $\ge d$, and the total number of vertices of the children is $n-1$.

Now, by a theorem of Jordan every tree either has a centre or bicentre. A tree with bicentre is formed by taking two rooted trees of equal depth and adding an edge between their roots. A tree with centre is a rooted tree where at least two children of the root have depth $d-1$.

$\endgroup$
0
$\begingroup$

Here is some python code https://gist.github.com/hagberg/7979081

I would start with all the trees size N-1 appending a new node to each of the nodes The tricky part is to identify whether each new tree is truly new and not isomorphic to previously generated trees. I'm guessing you need a system to code this topologies to detect symmetries. I'd try to find the longest path Longest path in an undirected tree with only one traversal and find a deterministic way to represent the graph

This now gone project to verify the graceful Tree conjecture contains some c++ code that might help you https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index_en.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.