1
$\begingroup$

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 ?

Improve this question
$\endgroup$
4
  • $\begingroup$ Welcome to CS.SE! What have you tried? Have you tried working out what distribution on trees this approach produces, for $n=3$ or $n=4$ (where $n$ is the number of vertices in the tree)? Is that the same as the uniform distribution on spanning trees or different? You'll probably need to decide exactly what process you have in mind for random minimum spanning tree, and in particular, what range/set/distribution the weights on each edge will be chosen from. Have you checked en.wikipedia.org/wiki/Random_minimum_spanning_tree and the references there to see if they have anything? $\endgroup$
    – D.W. ♦
    Commented Jan 23, 2017 at 14:41
  • $\begingroup$ To see the answer, visit here. $\endgroup$
    – H.H
    Commented Jan 23, 2017 at 18:46
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/2109978/14578, cs.stackexchange.com/q/69171/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W. ♦
    Commented Jan 23, 2017 at 18:55
  • $\begingroup$ I'm voting to close this question, even though it is on-topic, because it was cross-posted. $\endgroup$
    – D.W. ♦
    Commented Jan 23, 2017 at 18:55

0

Reset to default

Browse other questions tagged or ask your own question.