Generating Uniformly Random Trees
Description of the Problem
Today, I would like to write an algorithm that would generate a random tree on \(n\) vertices so that every such randomly created tree shows up equally likely among all possible trees on \(n\) vertices.
The Algorithm
I will construct the tree as a topologically ordered directed graph and then remove the direction information.
I will call an undirected graph topologically ordered if there is an orientation of the edges such that the resulting directed graph is topologically ordered. In other words, if \(G\) is a topologically ordered undirected graph if there is a topologically ordered directed graph \(H\) such that when we forget about the directions of the edges of \(H\) we get \(G\).
Assume we already have a random tree \(T\) on \(n-1\) vertices. Pick a vertex \(i\) uniformly random, and connect an edge \((i,n)\) to form a new graph \(S\). Since \(T\) was a tree, it does not contain any cycles. Since \(n\) is a new vertex added to \(T\), the new graph \(S\) does not contain a cycle either.
As for the likelihood of our trees: There is only one tree on 2 vertices. So, picking a topologically ordered tree on 2 vertices by our algorithm is uniformly random with probability 1. Now, assume by induction that picking a topologically ordered tree on \(n\>1\) vertices with the algorithm we described above is uniformly random. Assume on the contrary that there is a topologically ordered tree \(S\) on \(n+1\) vertices which is more likely to appear from our algorithm. We know that \(S\) is obtained from a topologically ordered tree \(T\) on \(n\) vertices by adding a single vertex \(n+1\) and a single edge \((i,n+1)\) where \(i=1,\ldots,n\). We also know that picking an edge \((i,n+1)\) is uniformly random for \(i=1,\ldots,n\) with probability \(\frac{1}{n}\). This means that \[ P(S) = \frac{P(T)}{n} \] and \(T\) would have to appear more likely among all topologically ordered trees on \(n\) vertices. This is a contradiction.
The Lisp Code
The lisp code is pretty straightforward.
(defun random-tree (n)
(loop for i from 1 below n
collect (list (random i) i)))
RANDOM-TREE
(random-tree 7)
((0 1) (0 2) (1 3) (0 4) (1 5) (2 6))