Creating a random tree?

A tree with n nodes can be uniquely expressed by a sequence of n-2 integer numbers (in the range of [0, n-1]). This is called the Prüfer sequence.

Creating a random sequence should be no problem. Then you just have to transform the sequence to your tree structure and you're done.

Developing on the above idea, here is how we can generate a 20-node labeled random tree (in python):

1. start from a randomly generated length-18 sequence with each element chosen from the set {1,2,...,20}.
2. use the generated string as Prufer sequence for the spanning tree for the complete graph K20 on 20 vertices and generate the corresponding labeled tree (since there is a 1-1 correspondence always) using the following algorithm (from here).

The next code snippet implements the above algorithm to generate a labeled tree (by computing the edges) given the prufer sequence:

def get_tree(S):
    n = len(S)
    L = set(range(1, n+2+1))
    tree_edges = []
    for i in range(n):
        u, v = S[0], min(L - set(S))
        S.pop(0)
        L.remove(v)
        tree_edges.append((u,v))
    tree_edges.append((L.pop(), L.pop()))
    return tree_edges

Now, we can always generate a prufer sequence (of length n-2) randomly and subsequently generate the corresponding spanning tree (on n vertices), which can serve as our random tree (can be thought of to be randomly sampled from the set of n^(n-2) spanning trees of Kn).

n = 20 # Kn with n vertices
N = 25 # generate 25 random trees with 20 vertices (as spanning trees of K20)
for i in range(N):
    S = np.random.choice(range(1,n+1), n-2, replace=True).tolist()
    T_E = get_tree(S) # the spanning tree corresponding to S
    # plot the tree generated (with `networkx`, e.g.,)

The next animation shows a few such randomly generated labeled trees with 20 nodes.

Sign up or log in

Post as a guest