The Minimum Spanning Tree Problem

Defining the problem

The minimum spanning tree (MST) problem deals with connected, weighted, undirected graphs $G = (V, E, w)$. Here, the weights can be interpreted as costs, and the goal is to select some subset of edges $F \subseteq E$ that connect the nodes of $V$ in a cost-optimal way. In particular, we want

• $F$ contains enough edges such that they connect all nodes of $V$
• the total cost of the edges in $F$ is as small as possible.

As an example, consider the following weighted graph:

We can think of the nodes as representing cities, and the edges representing distances between them. Now, assume that we want to build a railroad network to connect these cities. Laying down train tracks is expensive, so we’ll want to find a way to connect all the nodes using the existing edges while keeping the total edge cost to a minimum.

In fact, this translates to finding a subset $F \subseteq E$ of minimal cost which connects $V$. The solution is given below, with the edges of $F$ highlighted in blue:

The total cost of $F$ ...