Minimum Spanning Trees in Weighted Graphs

Section 5.3 Minimum Spanning Trees in Weighted Graphs

Our second example of an optimization problem involves the concept of a weighted graph and a minimum spanning tree.

Definition 5.3.1.

A weighted graph is a graph in which each edge is assigned a real value, called its weight. We will denote a weighted graph as a pair \((G,w)\text{,}\) where \(G = (V,E)\) is the underlying graph and \(w : E \to \mathbb{R}\) is the weight function that assigns a weight to each edge.

🔗

Definition 5.3.2.

Given a weighted graph \((G,w)\text{,}\) a minimum spanning tree is a spanning tree of \(G\) that has the smallest possible total weight among all spanning trees of \(G\text{.}\) In other words, if \(T = (V, E_T)\) is a spanning tree of \(G\text{,}\) then the total weight of \(T\) is given by

\begin{equation*} \sum_{e \in E_T} w(e)\text{,} \end{equation*}

and a minimum spanning tree is one that minimizes this sum.

🔗

Figure 5.3.3. A weighted graph and a minimum spanning tree.
🔗

Checkpoint 5.3.4.

How might you check that the spanning tree shown in the figure above is indeed a minimum spanning tree for the given weighted graph?

🔗

There is a well-known greedy algorithm, called Kruskal’s algorithm, that can be used to find a minimum spanning tree in a weighted graph. We will first need to establish some notation.

🔗

Definition 5.3.5.

Let \(S\subseteq E\) be a set of edges in a weighted graph \((G,w)\text{.}\) Let \(G:S\) denote the subgraph of \(G\) that contains all the vertices of \(G\) and the edges in \(S\text{,}\) which we call the spanning subgraph induced by \(S\text{.}\) We say \(S\) is independent if the spanning subgraph \(G:S\) is acyclic.

🔗

Note that an independent set of edges must be a union of trees, since each connected component of an acyclic graph is a tree. Also, note that if \(S\) is independent and has \(k\) edges, then the spanning subgraph \(G:S\) has \(n - k\) connected components, where \(n\) is the number of vertices in \(G\text{.}\)

🔗

Checkpoint 5.3.6.

Draw a picture of \(K_6:\{12,23, 45\}\text{.}\) What are the connected components of the spanning subgraph \(K_6:\{12, 23, 45\}\text{?}\) Is the set of edges \(\{12, 23, 45\}\) independent?
🔗

🔗
Is it possible to find a non-independent set of edges in the Petersen graph that has four edges? Why or why not?
🔗

🔗

🔗

Figure 5.3.7. Drawing of the Petersen graph.
🔗

🔗

Definition 5.3.8. Kruskal’s Algorithm.

Let \((G,w)\) be a weighted graph with \(n\) vertices. The algorithm proceeds as follows: Start with the empty set of edges \(S = \emptyset\text{.}\)

🔗

While \(|S| \lt n - 1\text{,}\) do the following:

Find an edge \(e \in E \setminus S\) of minimum weight \(w(e)\) such that adding \(e\) to \(S\) connects two components in the spanning subgraph \(G:S\text{.}\)

🔗
Add the edge \(e\) to the set \(S\text{.}\)

🔗

When the algorithm terminates, output the spanning tree \(T = (V, S)\text{.}\)

🔗

We will prove below that Kruskal’s algorithm always produces a minimum spanning tree, but for the moment let’s take this fact for granted and see how the algorithm works.

🔗

Example 5.3.9.

Let’s apply Kruskal’s algorithm to the weighted graph below.

🔗

We start with the empty set of edges \(S = \emptyset\text{.}\) Thus, \(G:S\) has eight connected components, each consisting of a single vertex.

There are three edges of minimum weight \(2\text{:}\) \(02,07,17\text{.}\) We can choose any of these edges to add to \(S\text{,}\) so we will choose \(02\text{.}\) Now, \(S = \{02\}\text{,}\) and \(G:S\) has seven connected components.
🔗

🔗
We will next select the edge \(17\text{,}\) which also has weight \(2\text{.}\) Now, \(S = \{02, 17\}\text{,}\) and \(G:S\) has six connected components.
🔗

🔗
We will next select the edge \(07\text{,}\) which also has weight \(2\text{.}\) Now, \(S = \{02, 17, 07\}\text{,}\) and \(G:S\) has five connected components.
🔗

🔗
Observation: At this point, we have selected all the edges of weight \(2\text{,}\) and we are not allowed in the future to select the edges \(01, 12, 27\) as these choices would introduce a cycle in the spanning subgraph.
🔗

🔗
We next select the edge \(05\text{,}\) as it has the next smallest weight of \(4\text{.}\) Now, \(S = \{02, 17, 07, 05\}\text{,}\) and \(G:S\) has four connected components.
🔗

🔗
We next select the edge \(14\text{,}\) as it has the next smallest weight of \(5\text{.}\) Now, \(S = \{02, 17, 07, 05, 14\}\text{,}\) and \(G:S\) has three connected components.
🔗

🔗
Observation: The smallest remaining edge weight is \(5\text{,}\) on the edge \(24\text{,}\) but adding this edge would create a cycle in \(G:S\text{,}\) so we cannot select this edge.
🔗

🔗
We next select the edge \(16\text{,}\) as it has the next smallest weight of \(8\) and does not introduce a cycle. Now, \(S = \{02, 17, 07, 05, 14, 16\}\text{,}\) and \(G:S\) has two connected components.
🔗

🔗
The final step in our algorithm is to select the edge \(13\text{,}\) which has weight \(11\) and connects the two remaining components.
🔗

🔗

Thus, the minimum spanning tree produced by Kruskal’s algorithm is the spanning tree with edge set \(S = \{02, 17, 07, 05, 14, 16, 13\}\text{.}\)

🔗

Checkpoint 5.3.11.

Run Kruskal’s algorithm on the weighted graph below and verify that the minimum spanning tree is correct.

🔗

Figure 5.3.12. A weighted graph and a minimum spanning tree.
🔗

🔗

Note that Kruskal’s algorithm can produce different minimum spanning trees depending on the choices made when there are multiple edges of the same minimum weight. For example, if every weight in the graph is equal to \(1\text{,}\) then any spanning tree is a minimum spanning tree, and Kruskal’s algorithm could produce any of them.

🔗

Theorem 5.3.13.

Kruskal’s algorithm always produces a minimum spanning tree for a given weighted graph \((G,w)\text{.}\)

🔗

Proof.

Let \((G,w)\) be a weighted graph with \(n\) vertices, and let \(T = (V,S)\) be the spanning tree produced by Kruskal’s algorithm. We will first show that \(T\) is indeed a spanning tree of \(G\text{.}\) Since the algorithm terminates when \(|S| = n - 1\text{,}\) and since we only add edges that connect two components in the spanning subgraph \(G:S\text{,}\) it follows that \(G:S\) is connected and acyclic. Therefore, \(T\) is a spanning tree of \(G\text{.}\)

🔗

We will now show that \(T\) is a minimum spanning tree. Let \(T'= (V, S')\) be any other spanning tree of \(G\text{.}\) Write

\begin{equation*} S=\{e_1,e_2,\ldots,e_{n-1}\} \end{equation*}

where the edges are listed in the order they were added by Kruskal’s algorithm, i.e.,

\begin{equation*} w(e_1) \leq w(e_2) \leq \cdots \leq w(e_{n-1})\, . \end{equation*}

We will write

\begin{equation*} S_k:=\{e_1,\ldots,e_k\}\, . \end{equation*}

Let \(T'\) have edges

\begin{equation*} S' = \{f_1, f_2, \ldots, f_{n-1}\}\text{,} \end{equation*}

written in the order

\begin{equation*} w(f_1) \leq w(f_2) \leq \cdots \leq w(f_{n-1})\, . \end{equation*}

We will show that

\begin{equation*} w(e_i) \leq w(f_i) \end{equation*}

for all \(1 \leq i \leq n - 1\text{,}\) which will imply that the total weight of \(T\) is less than or equal to the total weight of \(T'\text{.}\) We go by contradiction and suppose that there exists an index \(k\) such that

\begin{equation*} w(e_k) \gt w(f_k)\text{,} \end{equation*}

and let \(k\) be the smallest such index. Since none of \(f_1, f_2, \ldots, f_{k}\) were chosen by Kruskal’s algorithm to be \(e_k\text{,}\) it follows that they were already in the components of \(G:S_{k-1}\text{.}\) Since \(G:S_{k-1}\) has \(n-(k-1)\) components, we see that \(G:S'_k\) has at least \(n-(k-1)=n-k+1\) components as well. But, if \(G:S'_k\) were acyclic, it would be a union of trees, and hence would have \(n-k\) components. This is not possible, and therefore \(G:S'_k\) is not acyclic, contradicting the assumption that \(T'\) is a spanning tree. Thus, we conclude that

\begin{equation*} w(e_i) \leq w(f_i) \end{equation*}

for all \(1 \leq i \leq n - 1\text{,}\) and hence that \(T\) is a minimum spanning tree.

🔗

Checkpoint 5.3.14.

Discuss the proof above. Does it make sense? Why or why not?

🔗

There are many amazing applications of minimum spanning trees. We will explore one such application to data clustering. Suppose that you have a set of data points in \(\mathbb{R}^n\) and you want to group them into clusters that are similar to each other. One way to do this is to construct a weighted complete graph where each vertex represents a data point and the weight of an edge between two vertices represents the distance between the corresponding data points. By finding a minimum spanning tree of this weighted complete graph, we can identify clusters of data points that are closely related to each other.

🔗

Let’s look at an example (with artificial data) to illustrate this idea. The following figure shows a set of data points in \(\mathbb{R}^2\) which I generated using Gaussian distributions around four points in the plane.

🔗

Figure 5.3.15. Data of four Gaussian clusters.
🔗

Consider the weighted complete graph with \(400\) vertices corresponding to these data points and \(\binom{400}{2}=79,800\) edges corresponding to pairs of points, where the weight of each edge is given by the Euclidean distance between the corresponding data points. The next figure shows a minimum spanning tree of this weighted graph, which has \(399\) edges.

🔗

Figure 5.3.16. MST for data of four Gaussian clusters.
🔗

If we remove the three edges with the largest weights (distances) from this spanning tree, we obtain four connected components, which correspond to the four observable clusters of data points.

🔗

Figure 5.3.17. Cut MST for data of four Gaussian clusters.
🔗

This simple example illustrates how minimum spanning trees can be used for data clustering, though in practice there are other much more robust algorithms used to identify clusters in data: https://en.wikipedia.org/wiki/Cluster_analysis

🔗

Prev Top Next