Editing Spanning tree (section)

===Optimization===
In certain fields of graph theory it is often useful to find a [[minimum spanning tree]] of a [[weighted graph]]. Other optimization problems on spanning trees have also been studied, including the maximum spanning tree, the minimum tree that spans at least k vertices, the [[Minimum degree spanning tree|spanning tree with the fewest edges per vertex]], the [[maximum leaf spanning tree|spanning tree with the largest number of leaves]], the spanning tree with the fewest leaves (closely related to the [[Hamiltonian path problem]]), the [[minimum-diameter spanning tree]], and the minimum dilation spanning tree.<ref name="sts">{{citation |last=Eppstein |first=David |author-link=David Eppstein |contribution=Spanning trees and spanners |title=Handbook of Computational Geometry|editor1-first=J.-R.|editor1-last=Sack|editor1-link=Jörg-Rüdiger Sack|editor2-first=J.|editor2-last=Urrutia|editor2-link=Jorge Urrutia Galicia |publisher=Elsevier |year=1999 |pages=425–461 |contribution-url=http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf |url-status=live |archive-url=https://web.archive.org/web/20230802121548/https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf |archive-date= Aug 2, 2023 }}.</ref><ref>{{citation |last1=Wu |first1=Bang Ye |last2=Chao |first2=Kun-Mao |title=Spanning Trees and Optimization Problems |year=2004 |publisher=CRC Press |isbn=1-58488-436-3}}.</ref>

Optimal spanning tree problems have also been studied for finite sets of points in a geometric space such as the [[Euclidean plane]]. For such an input, a spanning tree is again a tree that has as its vertices the given points. The quality of the tree is measured in the same way as in a graph, using the Euclidean distance between pairs of points as the weight for each edge. Thus, for instance, a [[Euclidean minimum spanning tree]] is the same as a graph minimum spanning tree in a [[complete graph]] with Euclidean edge weights. However, it is not necessary to construct this graph in order to solve the optimization problem; the Euclidean minimum spanning tree problem, for instance, can be solved more efficiently in ''O''(''n''&nbsp;log&nbsp;''n'') time by constructing the [[Delaunay triangulation]] and then applying a linear time [[planar graph]] minimum spanning tree algorithm to the resulting triangulation.<ref name="sts" />