What is a Minimum Spanning Tree?


Reading time: 15 minutes

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted 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 edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

mst

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.

  • Minimum-cost subgraph
    If the weights are positive, then a minimum spanning tree is in fact a minimum-cost 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 cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.

  • Minimum-cost 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, single-linkage clustering (a method of hierarchical clustering), graph-theoretic 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 tree-based 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 socio-geographic areas, the grouping of areas into homogeneous, contiguous regions.
  • Comparing ecotoxicology data.
  • Topological observability in power systems.
  • Measuring homogeneity of two-dimensional materials.
  • Minimax process control.
  • Minimum spanning trees can also be used to describe financial markets.