Generate all unique acyclic graphs (trees) given n nodes.

algorithmsgraph theorysagemathtrees

I'd like to generate the complete set of unordered acyclic graphs (trees) given n nodes. By "unique", I mean that for every graph in the set, no two graphs can be isomorphic. Below I have the set of all unique trees given 4 nodes. Assuming there's some known procedure to do this, I'd also greatly appreciate any specifics about whether or not there's an easy way to generate these sets in sage. For clarity, these sets should NOT be limited to binary trees; there is no limit to the degree of any vertex apart that imposed by the number of vertices available to connect to (while remaining acyclic). If there's no known way to generate just the unique trees given n nodes, but there is a way to generate all trees given n nodes where some number of graphs in the set are isomorphic to other graph(s) in the set, details on how to generate that set would also be appreciated.

example trees

Update

Did some more looking at sage, found a generator: https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.trees

Best Answer

The basic approach to generating unrooted trees is to generate rooted trees and then apply the theorem that every tree has either a centre or a bicentre.

In slightly more detail, you generate rooted trees of up to $\frac n2$ vertices and categorise them by the tuple (number of vertices, depth). Give each one a distinct integer label as a way of totally ordering them. Then the unrooted trees of $n$ are the union over $d$ of the unrooted trees of $n$ vertices and diameter $d$.

If $d$ is even then you take the centre, attach to it two or more rooted trees of depth $\frac d2$, and make the number of vertices up to $n$ by attaching rooted trees of lower depth. The total order serves to ensure you generate each tree only once.

Similarly, if $d$ is odd you have a bicentre, and each of its two vertices has at least one rooted tree of depth $\frac{d-1}2$ and none which are deeper.

Related Question