Skip to content

2.1 The minimum spanning tree problem

Part 2 · Trees and paths · Chapter 2 · Chapter 2: Spanning trees · Lecture notes, volume 2 (PDF) · Exercises: Spanning trees · App: Minimum spanning trees: Kruskal and Prim

Definition 2.1: minimum spanning tree problem

Let \(G=(V,E)\) be a connected undirected graph with \(n=|V|\) vertices and \(m=|E|\) edges, and let every edge \(e \in E\) have a weight \(w_e \in \R\). The weight of a set of edges \(F \subseteq E\) is

\[ w(F)=\sum_{e \in F} w_e . \]

The minimum spanning tree problem (MST) asks for a spanning tree \(\tilde{T}=(V,\tilde{F})\) of \(G\) of minimum weight:

\[ w(\tilde{F}) \le w(F) \qquad \text{for every spanning tree } (V,F) \text{ of } G . \]

A spanning tree of minimum weight is a minimum spanning tree. We write \(w_{uv}\) for the weight of the edge \(\{u,v\}\), and we identify a spanning tree with its set of edges.

  • A connected graph has a spanning tree, and it has finitely many of them: a minimum spanning tree always exists. Every spanning tree has \(n-1\) edges.

  • The weights can be negative. Adding the same constant to every weight adds \((n-1)\) times that constant to the weight of every spanning tree, so the minimum spanning trees do not change.

  • A maximum spanning tree is a minimum spanning tree for the weights \(-w_e\).

Example 2.1: the weighted reference graph

We take the underlying undirected graph of the reference graph of the chapter «Graphs», with \(n=6\) vertices, \(m=9\) edges and the weights

edge \(\{1,2\}\) \(\{1,3\}\) \(\{2,3\}\) \(\{2,4\}\) \(\{3,4\}\) \(\{3,5\}\) \(\{4,5\}\) \(\{4,6\}\) \(\{5,6\}\)
\(w_e\) \(4\) \(1\) \(3\) \(6\) \(5\) \(8\) \(2\) \(9\) \(7\)

Figure 1

We call this graph the weighted reference graph: all the examples of the chapter use it. The weights are the distinct integers \(1,2,\dots,9\).

Example 2.2: the minimum spanning tree of the reference graph

The weighted reference graph has \(55\) spanning trees. Enumerating all of them, the minimum weight is \(18\), attained only by the tree (blue in the figure)

\[ \tilde{F}=\big\{\{1,3\},\{2,3\},\{3,4\},\{4,5\},\{5,6\}\big\}, \qquad w(\tilde{F})=1+3+5+2+7=18 . \]

Figure 2

The spanning tree \(\{1,2\},\{1,3\},\{2,4\},\{3,5\},\{4,6\}\) found by the breadth-first search in the chapter «Graphs» weighs \(4+1+6+8+9=28\), and a maximum spanning tree weighs \(34\).

  • Enumerating the spanning trees is practical only on tiny graphs: the reference graph, with \(6\) vertices and \(9\) edges, already has \(55\). The algorithms of this chapter find a minimum spanning tree in polynomial time.

2.1.1 Applications

  • Network design. Vertices are sites (offices, houses, plants) and \(w_{uv}\) is the cost of a direct link (a cable, a pipe, a road); the cheapest network connecting all the sites is a minimum spanning tree.

  • Clustering. Removing the \(k-1\) heaviest edges of a minimum spanning tree splits the vertices into \(k\) groups of close points (single-linkage clustering).

  • Subproblem. Minimum spanning trees give lower bounds for the travelling salesman problem and a starting point for heuristic algorithms for network design.

A minimum spanning tree connects all the vertices of a connected weighted graph with \(n-1\) edges of minimum total weight; on the weighted reference graph it is unique and weighs \(18\).

Next: 2.2 Cuts and cycles