Get this book > Problems on Array: For Interviews and Competitive Programming
Reading time: 15 minutes
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edgeweighted directed or undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. It is a spanning tree whose sum of edge weights is as small as possible.
More generally, any edgeweighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.
Properties
The properties of a minimum spanning tree are:

Possible multiplicity
If there are n vertices in the graph, then each spanning tree has n âˆ’ 1 edges. 
Uniqueness
If each edge has a distinct weight then there will be only one, unique minimum spanning tree. 
Minimumcost subgraph
If the weights are positive, then a minimum spanning tree is in fact a minimumcost subgraph connecting all vertices. 
Cycle property
For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to a MST. 
Cut property
For any cut C of the graph, if the weight of an edge e in the cutset of C is strictly smaller than the weights of all other edges of the cutset of C, then this edge belongs to all MSTs of the graph. 
Minimumcost edge
If the minimum cost edge e of a graph is unique, then this edge is included in any MST. 
Contraction
If T is a tree of MST edges, then we can contract T into a single vertex while maintaining the invariant that the MST of the contracted graph plus T gives the MST for the graph before contraction.
Applications
The applications of Minimum Spanning Tree are:
 Minimum Spanning tree is used to describe/ design a network.
 Taxonomy.
 Cluster analysis: clustering points in the plane, singlelinkage clustering (a method of hierarchical clustering), graphtheoretic clustering and clustering gene expression data.
 Constructing trees for broadcasting in computer networks. On Ethernet networks this is accomplished by means of the Spanning tree protocol.
 Image registration and segmentation (minimum spanning treebased segmentation).
 Curvilinear feature extraction in computer vision.
 Handwriting recognition of mathematical expressions.
 Circuit design: implementing efficient multiple constant multiplications, as used in finite impulse response filters.
 Regionalisation of sociogeographic areas, the grouping of areas into homogeneous, contiguous regions.
 Comparing ecotoxicology data.
 Topological observability in power systems.
 Measuring homogeneity of twodimensional materials.
 Minimax process control.
 Minimum spanning trees can also be used to describe financial markets.