Editing Spanning tree (section)

===Randomization===
A spanning tree chosen [[random]]ly from among all the spanning trees with equal probability is called a [[uniform spanning tree]]. Wilson's algorithm can be used to generate uniform spanning trees in polynomial time by a process of taking a random walk on the given graph and erasing the cycles created by this walk.<ref>{{citation
 | last = Wilson | first = David Bruce
 | contribution = Generating random spanning trees more quickly than the cover time
 | doi = 10.1145/237814.237880
 | mr = 1427525
 | pages = 296–303
 | title = Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996)
 | year = 1996| title-link = Symposium on Theory of Computing
 | isbn = 0-89791-785-5
 }}.</ref>

An alternative model for generating spanning trees randomly but not uniformly is the [[random minimal 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.<ref>{{citation
 | last1 = McDiarmid | first1 = Colin
 | last2 = Johnson | first2 = Theodore
 | last3 = Stone | first3 = Harold S.
 | doi = 10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y
 | issue = 1–2
 | journal = Random Structures & Algorithms
 | mr = 1611522
 | pages = 187–204
 | title = On finding a minimum spanning tree in a network with random weights
 | url = http://www.stats.ox.ac.uk/~cstone/mst.pdf
 | volume = 10
 | year = 1997}}.</ref>