A spanning tree chosen randomly from among all the spanning trees with equal probability is called a uniform spanning tree.

A model for generating spanning trees randomly but not uniformly is the random minimum spanning tree. In this model, the edges of the graph are assigned random weights and then the minimum spanning tree of the weighted graph is constructed [Wikipedia].

Why a random minimum spanning tree is not an uniform spanning tree ?


Random minimum spanning tree is a spanning tree that was obtained via Kruskal's algorithm starting with a random permutation. Take a graph that is a square with one diagonal (4 vertices, 5 edges). There are 8 spanning trees (4 that include the diagonal, and 4 that don't), each should be picked with probability $1/8$. However, that is no so for random minimum spanning tree. Consider the following 5 cases (each happens with equal probability):

  1. The diagonal is first. - The diagonal edge is certainly picked.
  2. The diagonal is second. - The diagonal edge is certainly picked.
  3. The diagonal is third. - First edge is irrelevant, 3 cases for the second edge:
    • same side - no diagonal.
    • other side, adjacent - with diagonal.
    • other side, not adjacent - with diagonal.
  4. The diagonal is fourth. - The first 3 edges form a spanning tree, no diagonal.
  5. The diagonal is fifth. - Same as above, no diagonal.

All in all, we get the following distribution, as you can see, the split is not equal:

  • no diagonal: $\frac{2}{5} + \frac{1}{5}\cdot\frac{1}{3} = \frac{7}{15}$.
  • diagonal: $\frac{2}{5} + \frac{1}{5}\cdot \frac{2}{3} = \frac{8}{15}$.

I hope this helps $\ddot\smile$


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.