Minimum Spanning Tree
A subset of the edges of a connected, undirected graph that connects all the vertices together, without any cycles, and with the minimum possible total edge weight. In other words, a spanning tree whose sum of edge weights is as small as possible.
Spanning tree
A subgraph that includes all the vertices of the original graph and is a single connected tree.
Out of all these spanning trees, MST is the one with the smallest total edge weight.
Steiner spanning tree
A tree that connects a subset of vertices while potentially adding additional vertices (called Steiner points or Steiner vertices) to minimize the total edge weight.
Minimum Steiner tree
A Steiner spanning tree that has the minimum weight. Finding a minimum Steiner tree is NP-hard, making it computationally more difficult than finding a minimum spanning tree. Useful in network design problems where new junction points can be added to reduce the overall cost of connecting required locations.
Definitions
Safe Edge
An edge that can be safely included in the growing MST subset without violating the MST property.
Cut
A partition of the vertices of a graph into 2 disjoint subsets.
Crossing Cut
An edge that has one endpoint in each subset of a cut is said to cross the cut.
Respecting Cut
Given a subset
Light Edge
For a given cut, the edge with the minimum weight among all edges crossing the cut. Prime candidates in MST algorithms.
Algorithms to Find MST
The general idea is to:
- Start with a subset of edges
- Add 1 safe edge to
at each iteration - Keep adding until an MST is found
Commonly used algorithms to find MST are:
Finding a Safe Edge
- Choose a cut that respects the current set of edges A
- Select the light edge crossing this cut
- This light edge is guaranteed to be safe for inclusion in the MST
Applications
- Network design (e.g., designing least-cost networks for telecommunication, electrical grids, etc.)
- Approximation algorithms for NP-hard problems
- Cluster analysis in machine learning