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 ?

$\endgroup$

closed as off-topic by D.W. Jan 23 '17 at 18:55

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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. Jan 23 '17 at 14:41
  • $\begingroup$ To see the answer, visit here. $\endgroup$ – H.H Jan 23 '17 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. Jan 23 '17 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. Jan 23 '17 at 18:55