Editing Minimum spanning tree (section)

{{Short description|Least-weight tree connecting graph vertices}}
{{Use American English|date = April 2019}}
[[File:Minimum spanning tree.svg|thumb|300px|right|A [[planar graph]] and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to its length.]]
A '''minimum spanning tree''' ('''MST''') or '''minimum weight spanning tree''' is a subset of the edges of a [[connected graph|connected]], edge-weighted undirected [[Graph (discrete mathematics)|graph]] that connects all the [[Vertex (graph theory)|vertices]] together, without any [[cycle (graph theory)|cycle]]s and with the minimum possible total edge weight.<ref name="Numpy and Scipy Documentation — Numpy and Scipy documentation">{{cite web | title=scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 Manual | website=Numpy and Scipy Documentation — Numpy and Scipy documentation | url=https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html | access-date=2021-12-10 | quote=A minimum spanning tree is a graph consisting of the subset of edges which together connect all connected nodes, while minimizing the total sum of weights on the edges.}}</ref> That is, it is a [[spanning tree]] whose sum of edge weights is as small as possible.<ref name="NetworkX 2.6.2 documentation">{{cite web | title=networkx.algorithms.tree.mst.minimum_spanning_edges | website=NetworkX 2.6.2 documentation | url=https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_edges.html | access-date=2021-12-13 | quote=A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.}}</ref> More generally, any edge-weighted undirected graph (not necessarily connected) has a '''minimum spanning forest''', which is a union of the minimum spanning trees for its [[connected component (graph theory)|connected components]].

There are many use cases for minimum spanning trees. One example is a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the [[triangle inequality]]. A ''spanning tree'' for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A ''minimum spanning tree'' would be one with the lowest total cost, representing the least expensive path for laying the cable.