Gabrijel Boduljak

Theory of the Minimum Spanning Tree Problem [Part 1]

πŸ“…December 30, 2020 | β˜•οΈ25 minutes read

a connected graph with its minimum spanning tree

mst wikipedia

This example was taken from taken from Wikipedia

In this blog post, I will discuss the inner structure and some theoretical results behind the minimum spanning tree problem in the context of undirected graphs. Firstly, we define a spanning subgraph and a minimum spanning subgraph. After proving some results regarding the structure of the minimum spanning tree problem, we develop two famous algorithms - Prim’s algorithm and Kruskal’s algorithm using the inner structure of the problem discussed in results proved before. The point of this approach which firstly develops the theory and then develops the algorithm is to shed some light on the key ideas behind those algorithms. After having discussed the structure of this problem, both algorithms seem completely natural and their correctness suddenly becomes evident. This is particularly important since both of these algorithms belong to the category of greedy algorithms, which gradually build the optimal solution to the original problem by making only the locally optimal choices. Clearly, it is common that the correctness proof of such algorithms becomes quite involved.

Definition 1: a spanning subset and a spanning tree

Let G=(V,E)G=(V,E) be an undirected connected graph having the vertex set VV and edge set EE. Then a subgraph Gβ€²=(V,A)G' = (V,A) where AβŠ†EA \subseteq E is a spanning subgraph of the graph G if the graph Gβ€²=(V,A)G'=(V, A) is connected. If Gβ€²G' is a tree, we say Gβ€²G' is a spanning tree of the graph G.

Now, we state and prove two important theorems which guarantee existence of minimum spanning tree for every connected graph.

Theorem 1: Every connected graph has a spanning tree.

Claim: Let G=(V,E)G=(V,E) be an undirected connected graph having the vertex set VV and edge set EE. Then GG has a spanning tree and hence a spanning subgraph.

Proof: We will prove by induction on the number of vertices ∣V∣|V|.
Basis: Suppose ∣V∣|V| = 1. Trivially, GG is connected. The graph (V,βˆ…)(V, \emptyset) is trivially a spanning tree. This establishes the basis.
Induction Hypothesis: Suppose that for all graphs G=(V,E)G=(V,E), with ∣V∣=nβˆ’1|V| = n - 1, the claim holds.
Induction Step: Now consider an undirected connected graph G=(V,E)G=(V, E) with the vertex set VV such that ∣V∣=n,n>1|V| = n, n > 1. Since ∣V∣β‰₯1|V| \ge 1, let u∈Vu \in V. Since the graph GG is connected, βˆ€v∈V\forall v \in V, there exists a path v⇝uv \rightsquigarrow u. Now, by the previous statement, there exists an edge (v,u)(v, u) for some v∈V,vβ‰ uv \in V, v \neq u. Consider the subgraph Gβ€²=(Vβ€²,Eβ€²)G' = (V', E') where: Vβ€²=Vβˆ’{u}V' = V - \{ u \}
Eβ€²=Eβˆ’{(v,u)∣(v,u)∈E}E' = E - \{ (v, u) | (v, u) \in E \}
Observe that Gβ€²G' is a subgraph of GG. Since GG was connected, so is Gβ€²G' because otherwise GG cannot be connected. By Induction Hypothesis, Gβ€²G' has a spanning tree, say T=(Vβ€²,A)T = (V', A) for some AβŠ†EA \subseteq E. Now consider Tβ€²=(V,Aβ€²)T' = (V, A') where Aβ€²=Aβˆͺ{(v,u)}A' = A \cup \{ (v, u) \}. We claim that Tβ€²T' is a spanning tree of the graph GG. Since u∉Vβ€²u \not \in V', Aβ€²A' does not induce a cycle in Tβ€²T' and connects VV. Since TT was a tree which is a subgraph of GG, all vertices in Vβ€²V' are also connected in TT and the edge (u,v)(u,v) connected uu to all of vertices in Vβ€²V'. Therefore, since Tβ€²T' is a connected graph without cycles, we deduce it is a tree. Since vertices of Tβ€²T' are VV, Tβ€²T' is a spanning tree of GG.
This completes the proof. β– \blacksquare

Remark: Does every undirected graph have a spanning tree? The answer is no, because any graph without edges and more than one vertex does not have a spanning tree. Therefore, the connectedness assumption of the graph is a crucial assumption which cannot be dropped.

Definition 2: a minimum spanning subset and a minimum spanning tree

Let w:Eβ†’Rw : E \to \mathbb{R} be a positive edge cost function. Define w(A)=βˆ‘(u,v)∈Aw((u,v))w(A)= \sum_{(u,v) \in A} w((u, v)). We say that a spanning subset AβŠ†EA \subseteq E of GG is minimal if w(A)w(A) is minimal amongst all possible spanning subgraphs of GG.

Corollary 1: Every connected graph has a minimum spanning tree.

Proof: By Theorem 1, every connected graph has a spanning tree. Since the number of spanning trees of any connected graph is finite, we deduce that for every connected graph there exists at least one minimum spanning tree. β– \blacksquare

Theorem 2: Assuming the strictly positive edge cost function, every minimal spanning subgraph is a tree.

Claim: Let G=(V,E)G=(V,E) be an undirected connected graph having the vertex set VV and edge set EE. Let w:E→Rw : E \to \mathbb{R} be a positive edge cost function. Then every minimal spanning subgraph of G is a tree.

Proof: (By contradiction)

Let (V,A),AβŠ†E(V,A), A \subseteq E be a minimal spanning subgraph of the graph GG. Assume, for the sake of contradiction, that (V,A)(V,A) is not a tree. By definition of AA, (V,A)(V,A) is connected. Since (V,A)(V,A) is connected and it is not a tree, it must be the case AA has a cycle. Suppose v1,v2,…vk=v1v_1, v_2, \ldots v_k = v_1 is a cycle in the graph (V,A)(V, A). Now select any edge (vi,vj),1≀i,j≀k(v_i, v_j), 1 \leq i, j \leq k. Consider Aβ€²=Aβˆ’{(vi,vj)}A' = A - \{ (v_i, v_j) \} and the graph Gβ€²=(V,Aβ€²)G'=(V, A'). Since v1,v2,…vk=v1v_1, v_2, \ldots v_k = v_1 is a cycle, vertices (vi,vj),1≀i,j≀k(v_i, v_j), 1 \leq i, j \leq k still remain connected in Gβ€²G' along some path vi⇝vi+1…⇝vjv_i \rightsquigarrow v_{i+1} \ldots \rightsquigarrow v_j in GG. Moreover, we claim that Gβ€²G' is connected. Select (u,v)∈VΓ—V(u, v) \in V \times V. Since AA is a spanning subset of GG, there exists a path u⇝vβŠ†Eu \rightsquigarrow v \subseteq E. We split in cases depending on whether (vi,vj)∈u⇝v(v_i, v_j) \in u \rightsquigarrow v.

Suppose (vi,vj)∉u⇝v(v_i, v_j) \not \in u \rightsquigarrow v. Then uu and vv remain connected in Gβ€²G' by existence of the path u⇝vu \rightsquigarrow v in GG. By construction of Gβ€²G', u⇝vu \rightsquigarrow v is in Gβ€²G'.

Suppose (vi,vj)∈u⇝v(v_i, v_j) \in u \rightsquigarrow v. Then uu and vv remain connected in Gβ€²G' by existence of the path u⇝vi⇝vi+1…⇝vj⇝vu \rightsquigarrow v_i \rightsquigarrow v_{i+1} \ldots \rightsquigarrow v_j \rightsquigarrow v in GG. By construction of Gβ€²G', u⇝vi⇝vi+1…⇝vj⇝vu \rightsquigarrow v_i \rightsquigarrow v_{i+1} \ldots \rightsquigarrow v_j \rightsquigarrow v is in Gβ€²G'.

Since (u,v)(u, v) was arbitrary, we deduce Gβ€²G' is connected so Gβ€²G' must be a spanning subgraph of GG. Observe that w(Aβ€²)=w(A)βˆ’w((vi,vj))w(A') = w(A) - w((v_i, v_j)). Since ww is a positive edge cost function, w((vi,vj))>0w((v_i, v_j)) > 0 so w(Aβ€²)<w(A)w(A') < w(A). This contradicts the minimality of AA. The assumption (V,A)(V,A) is not a tree was wrong. Hence (V,A)(V,A) must be a a tree. This completes the proof. β– \blacksquare

Definitions stated above ensure the (minimum) spanning trees or subgraphs are precisely defined while above proved theorems guarantee the existence of spanning tree in connected graphs. Although these results may be basic, they outline a general setup for more interesting results, such as the following one.

Theorem 3: Uniqueness of a minimum spanning tree

Claim: Let G=(V,E)G=(V,E) be an undirected connected graph having the vertex set VV and edge set EE. Let w:E→Rw : E \to \mathbb{R} be an injective edge cost function. Then the minimum spanning tree of the graph GG must be unique.

Proof: (By contradiction)

Suppose, for the sake of contradiction, that there exist two distinct minimum spanning trees T=(V,A)T=(V,A) and Tβ€²=(V,Aβ€²)T'=(V, A'). Since TT and Tβ€²T' are distinct, let (u,v)(u,v) be the minimum cost edge that is not present in both AA and Aβ€²A'. By the fact ww is injective, the edge (u,v)(u,v) is the unique edge that is not present in both AA and Aβ€²A' of the minimum cost. Assume, without loss of generality, that (u,v)(u,v) is present in AA and hence not present in Aβ€²A'. Since Tβ€²T' is a spanning tree, there exists the unique path u⇝vu \rightsquigarrow v. We claim there exists an edge (x,y)(x, y) such that (x,y)∈u⇝v(x,y) \in u \rightsquigarrow v where u⇝vu \rightsquigarrow v is a path in Tβ€²T' and (x,y)∉A(x, y) \not \in A.
By construction of (u,v)(u,v), the path u⇝v∈Tβ€²u \rightsquigarrow v \in T' can be decomposed as u⇝xβ†’y⇝vu \rightsquigarrow x \rightarrow y \rightsquigarrow v where yy is possibly vv and uβ‰ xu \neq x. If the path u⇝xβ†’y⇝vu \rightsquigarrow x \rightarrow y \rightsquigarrow v is entirely included in TT, we obtain a cycle u⇝xβ†’y⇝vβ†’uu \rightsquigarrow x \rightarrow y \rightsquigarrow v \rightarrow u which contradicts the fact TT was a tree. Hence it must be the case there exists (x,y)∈Aβ€²(x, y) \in A' such that (x,y)∈u⇝v(x,y) \in u \rightsquigarrow v where u⇝vu \rightsquigarrow v is a path in Tβ€²T' and (x,y)∉A(x, y) \not \in A. Observe that w((x,y))>w((u,v))w((x,y)) > w((u,v)).
Now consider the graph Tβ€²β€²=(V,Aβ€²β€²)T''=(V, A'') where Aβ€²β€²=(Aβ€²βˆ’{(x,y)})βˆͺ{(u,v)}A'' = (A' - \{ (x,y) \}) \cup \{(u,v)\}. We claim that Tβ€²β€²T'' is as spanning tree of GG. By the fact u⇝vu \rightsquigarrow v is the unique path from uu to vv in the tree Tβ€²T', the graph (V,(Aβ€²βˆ’{(x,y)}))(V,(A' - \{ (x,y) \})) is split into two disjoint connected components, one containing uu and the other one containing vv, say TuT_u and TvT_v respectively. Observe that TuT_u and TvT_v are actually subtrees of Tβ€²T'. Since u,vu,v reside in disjoint connected components of (V,(Aβ€²βˆ’{(x,y)}))(V,(A' - \{ (x,y) \})), TuT_u and TvT_v, addition of an edge (u,v)(u,v) to (Aβ€²βˆ’{(x,y)})(A' - \{ (x,y) \}) connects uu and vv without induction of cycle so the graph Tβ€²β€²T'' must be connected. Moreover, since TuT_u and TvT_v were subtrees and are joined by a single edge (u,v)(u,v) without cycle, we deduce Tβ€²β€²T'' is a tree. Since the vertex set of Tβ€²β€²T'' is VV and Tβ€²β€²T'' is a tree, we deduce Tβ€²β€²T'' is spanning so Tβ€²β€²T'' is a spanning tree of the graph GG.
Now consider w(Tβ€²β€²)w(T'').

w(Tβ€²β€²)=w(Tβ€²)βˆ’w((x,y))+w((u,v))(ByΒ definitionΒ ofΒ Tβ€²β€²)<w(Tβ€²)(SinceΒ w((x,y))>w((u,v))) \begin{aligned} w(T'') &= w(T') - w((x, y)) + w((u, v)) & (\text{By definition of $T''$}) \\ &< w(T') & (\text{Since $w((x,y)) > w((u,v))$}) \\ \end{aligned}

Since w(Tβ€²β€²)<w(Tβ€²)w(T'') < w(T') and Tβ€²β€²T'' is a spanning tree, Tβ€²T' cannot be a minimum spanning tree. This is a contradiction. The assumption GG has distinct minimum spanning trees was wrong, so we deduce GG has the unique minimum spanning tree, as claimed. β– \blacksquare

It turns out that in case of connected graphs, there always exists a minimum spanning tree containing the minimum cost edge.

Theorem 4: There exists a minimum spanning tree containing minimum cost edge.

Claim: Let G=(V,E)G=(V,E) be an undirected connected graph having the vertex set VV and edge set EE. Let w:E→Rw : E \to \mathbb{R} be an edge cost function. Let (u,v)(u,v) be a not necessarily unique edge with the minimum cost ww amonst all edges in EE. Then there exists a minimum spanning tree of the graph GG containing (u,v)(u,v).

Proof: (By contradiction)

Let T=(V,A)T=(V,A) be a minimum spanning tree of the graph GG which does not include an edge (u,v)(u,v), that is, (u,v)∉A(u,v) \not \in A. Since TT is a tree, there exists an unique path u⇝vu \rightsquigarrow v. Since (u,v)∉A(u,v) \not \in A, we decompose the path above as u⇝xβ†’y⇝vu \rightsquigarrow x \rightarrow y \rightsquigarrow v where yy possibly equals vv and xβ‰ ux \neq u. Now consider Tβ€²=(V,Aβˆ’{(x,y)}βˆͺ{(u,v)})T' = (V, A - \{ (x, y)\} \cup \{ (u,v) \}). We will show that Tβ€²T' is a tree and that is spanning. Since the path u⇝xβ†’y⇝vu \rightsquigarrow x \rightarrow y \rightsquigarrow v is unique path from uu to vv in TT, removing an edge (x,y)(x,y) from TT disconnects TT into two disjoint components (trees), one containing uu and the other one containing vv. Say TuT_u and TvT_v respectively. Now since uu and vv reside in distinct disjoint components TuT_u, TvT_v, addition of the edge (u,v)(u,v) connects TuT_u and TvT_v into a singe component Tβ€²T', since (u,v)(u,v) cannot induce a cycle. Since TuT_u and TvT_v are subtrees of TT, connecting them via (u,v)(u,v) produces a tree Tβ€²T'. Since Tβ€²T' is a tree with the vertex set VV, Tβ€²T' is a spanning tree of the graph GG. We also have:

w(Tβ€²)=w(T)βˆ’w((x,y))+w((u,v))(ByΒ definitionΒ ofΒ Tβ€²)≀w(T)(SinceΒ w((x,y))β‰₯w((u,v))) \begin{aligned} w(T') &= w(T) - w((x, y)) + w((u, v)) & (\text{By definition of $T'$}) \\ &\leq w(T) & (\text{Since $w((x,y)) \geq w((u,v))$}) \\ \end{aligned}

Since TT is a minimum spanning tree, w(T)β‰₯w(Tβ€²)w(T) \geq w(T'). Combining this result with the previous one, we obtain w(Tβ€²)=w(T)w(T')=w(T). Hence Tβ€²T' is a minimum spanning tree of GG containing an edge (u,v)(u,v) of the minimum cost. This completes the proof. β– \blacksquare.

Theorem 5: Elementary cycle properties of a minimum spanning tree

Claim: Let G=(V,E)G=(V,E) be an undirected connected graph having the vertex set VV and edge set EE. Let w:Eβ†’Rw : E \to \mathbb{R} be an edge cost function. Suppose v1,v2,…,vk=v1v_1, v_2,\ldots, v_k=v_1 is a cycle in GG. The following holds:

  1. Suppose an edge (vi,vi+1),1≀i<k(v_i, v_{i+1}), 1 \leq i < k is the edge of the maximum cost in the cycle above. If (vi,vi+1)(v_i, v_{i+1}) has strictly larger cost then any other edge in the cycle above, (vi,vi+1)(v_i, v_{i+1}) cannot be included in a minimum spanning tree of GG.
  2. Suppose (vi,vi+1),1≀i<k(v_i, v_{i+1}), 1 \leq i < k is the edge of the minimum cost from the cycle above. Then (vi,vi+1)(v_i, v_{i+1}) may not be included in some minimum spanning tree of GG.

Proof of 1: (By contradiction)

Let T=(V,A)T=(V,A) be a minimum spanning tree of the graph GG which does include an edge (vi,vi+1)(v_i,v_{i+1}). Consider the graph Tβ€²=(V,Aβˆ’{(vi,vi+1)})T'=(V, A - \{ (v_i,v_{i+1})\}). Since TT was a tree, removing an edge (vi,vi+1)(v_i,v_{i+1}) disconnects TT into two disjoint connected components TviT_{v_i} and Tvi+1T_{v_{i+1}} such that TviT_{v_i} contains viv_i and Tvi+1T_{v_i+1} contains vi+1v_{i+1}. Now, since v1,v2,…,vk=v1v_1, v_2,\ldots, v_k=v_1 is a cycle, there exists some edge (u,v)(u, v) on the cycle v1,v2,…,vk=v1v_1, v_2,\ldots, v_k=v_1 such that u∈Tviu \in T_{v_i} and v∈Tvi+1v \in T_{v_{i + 1}}. By assumption regarding (vi,vi+1)(v_i,v_{i+1}), we have w((u,v))<w((vi,vi+1))w((u,v))<w((v_i,v_{i+1})). Now set Tβ€²β€²=(V,(Aβˆ’{(vi,vi+1)})βˆͺ{(u,v)})T'' = (V, (A - \{ (v_i,v_{i+1})\}) \cup \{ (u,v)\}). We claim Tβ€²β€²T'' is a spanning tree of GG. Since TviT_{v_i} and Tvi+1T_{v_{i+1}} are disjoint, adding an edge (u,v)(u,v) connects TviT_{v_i} and Tvi+1T_{v_{i+1}} into a single connected component. Since TviT_{v_i} and Tvi+1T_{v_{i+1}} were subtrees of TT, we deduce Tβ€²β€²T'' is also a tree. Since it includes all vertices from VV, we deduce Tβ€²β€²T'' is a spanning tree. We also have

w(Tβ€²β€²)=w(T)βˆ’w((vi,vi+1))+w((u,v))(ByΒ definitionΒ ofΒ Tβ€²β€²)<w(T)(SinceΒ w((u,v))<w(vi,vi+1)) \begin{aligned} w(T'') &= w(T) - w((v_i, v_{i+1})) + w((u, v)) & (\text{By definition of $T''$}) \\ &< w(T) & (\text{Since $w((u,v)) < w(v_i, v_{i+1})$}) \\ \end{aligned}

Since Tβ€²β€²T'' is a spanning tree, we deduce TT cannot be a minimum spanning tree. This is a contradiction to the fact TT was a minimum spanning tree. The assumption TT includes (vi,vi+1)(v_i, v_{i+1}) was wrong, so we deduce TT cannot contain (vi,vi+1)(v_i, v_{i+1}). Since TT was arbitrary, no minimum spanning tree of GG contains (vi,vi+1)(v_i, v_{i+1}). This completes the proof. β– \blacksquare

Counterexample for 2:

counterexample





In the graph above, consider the cycle x,y,u,w,xx,y,u,w,x. An edge of minimum cost is (x,w)(x,w). However, the minimum spanning tree of the graph above is:
T=({x,y,z,u,w},{(z,x),(z,y),(z,u),(z,w)})T=(\{ x, y, z, u, w\}, \{ (z,x), (z,y), (z,u), (z,w)\}). Observe that TT does not include (x,w)(x,w).

After having shown the previous results, to prove possibly the most important result regarding the structure of the minimum spanning tree problem, we need to define a concept of the graph cut.

Definition 3: a graph cut, crossing edge

Let G=(V,E)G=(V,E) be a graph having the vertex set VV and edge set EE. A cut (S,Vβˆ’S)(S, V-S) is a partition of VV. An edge (u,v)(u,v) crosses the cut if u∈S,v∈(Vβˆ’S)u \in S, v \in (V-S).

Now we state and prove the fundamental result regarding the structure of the minimum spanning tree problem. Consider again the Theorem 4. Theorem 4 indicates that it is always β€˜safe’ to include a minimum cost edge in a β€˜potential’ partial minimum spanning tree, because it must be a part of some minimum spanning tree. However, the step/s after this one are not immediatelly clear and we need a bit more insight into the structure of the minimum spanning tree problem to discover and justify what could be the next possible steps in the process of finding some minimum spanning tree.

Theorem 6: The fundamental cut property of the minimum spanning tree problem

Claim: Let G=(V,E)G=(V,E) be an undirected connected graph having the vertex set VV and edge set EE. Let w:Eβ†’Rw : E \to \mathbb{R} be an edge cost function. Let (S,Vβˆ’S)(S, V-S) be a cut of the graph GG. Let AA be the set of edges which belong to some minimum spanning tree and assume no edge in AA crosses the cut (S,Vβˆ’S)(S, V-S). Let (u,v)(u,v) be the edge crossing the cut (S,Vβˆ’S)(S, V-S) whose cost ww is minimal amongst edges crossing the cut (S,Vβˆ’S)(S, V-S). Then an edge (u,v)(u,v) belongs to some minimum spanning tree of GG.

Remark: The intuitive explanation of this claim is the following assertion: Suppose we somehow have a subset of edges AA of some minimum spanning tree TT. If we can find a suitable cut of the graph (S,Vβˆ’S)(S, V-S) and the minimum cost edge (u,v)(u,v) that crosses the cut, we can safely extend AA to Aβˆͺ{(u,v)}A \cup \{ (u,v) \}. By β€˜safely’ extending we mean that Aβˆͺ{(u,v)}A \cup \{ (u,v) \} is also a subset of some minimum spanning tree. This means that by iteratively finding suitable cuts and minimum weight crossing edges, we eventually construct a minimum spanning tree!

Proof: (By construction)

Let T=(V,ET)T=(V,E_T) be a minimum spanning tree whose edge set contains AA, AβŠ†ETA \subseteq E_T. It suffices to show there exists a minimum spanning tree containing edges Aβˆͺ{(u,v)}A \cup \{ (u,v) \}. If (u,v)∈ET(u,v) \in E_T then Aβˆͺ{(u,v)}∈ETA \cup \{ (u,v) \} \in E_T and the claim holds.
Thus, suppose (u,v)∉ET(u,v) \not \in E_T. We will construct a minimum spanning tree containing (u,v)(u,v). Since TT is a spanning tree, there exists the unique path between vertices uu and vv in TT. Since (u,v)∉ET(u,v) \not \in E_T, and since u∈Su \in S and v∈Vβˆ’Sv \in V - S that path decomposes into u⇝xβ†’y⇝vu \rightsquigarrow x \rightarrow y \rightsquigarrow v where x∈Sx \in S, y∈Vβˆ’Sy \in V - S and possibly x=ux = u or y=vy = v but not both x=ux = u and y=vy = v. Consider Tβ€²=(V,(ETβˆ’{(x,y)})βˆͺ{(u,v)})T' = (V, (E_T - \{ (x,y)\}) \cup \{ (u,v) \}). We will show Tβ€²T' is a tree which is also a spanning tree such that AβŠ†ETβˆ’{(x,y)}A \subseteq E_T - \{ (x,y)\}.
We will firstly show that Tβ€²T' is indeed a tree. Since TT is a tree, the path u⇝xβ†’y⇝vu \rightsquigarrow x \rightarrow y \rightsquigarrow v is unique so ETβˆ’{(x,y)}E_T - \{ (x,y)\} disconnects TT. More precisely, the graph (V,ETβˆ’{(x,y)})(V, E_T - \{ (x,y)\}) consists of precisely two disjoint connected components, one containing uu, say TuT_u, and the other one containing vv, say TvT_v. Since both TuT_u and TvT_v are in fact subgraphs of TT which is a tree, both of them are actually subtrees of TT. Now consider an edge (u,v)(u,v). Since (u,v)(u,v) is a minimum weight edge crossing the cut and since (x,y)(x,y) is crossing the cut, we have w((u,v))≀w((x,y))w((u,v)) \leq w((x,y)). Clearly, since (x,y)(x, y) is crossing the cut, (x,y)∉A(x,y) \not \in A. Also, since (u,v)(u,v) is connecting two disjoint connected components, the addition of (u,v)(u,v) to ETβˆ’{(x,y)}E_T - \{ (x,y)\} cannot induce a cycle and must connect TuT_u and TvT_v. The resulting graph Tβ€²T' is therefore a tree since it is connected and has no cycles. Moreover, since TT was spanning, so is Tβ€²T' since it is connected and has the same vertex set as TT. We deduce Tβ€²T' is also a spanning tree of GG.
Now, we examine the weight of the spanning tree Tβ€²T':

w(Tβ€²)=w(T)βˆ’w((x,y))+w((u,v))(ByΒ definitionΒ ofΒ Tβ€²)≀w(T)(SinceΒ w((u,v))≀w((x,y))) \begin{aligned} w(T') &= w(T) - w((x,y)) + w((u, v)) & (\text{By definition of $T'$}) \\ &\leq w(T) & (\text{Since $w((u,v)) \leq w((x, y))$}) \\ \end{aligned}

Since TT was a minimum spanning tree w(T)≀w(Tβ€²)w(T) \leq w(T'). By combining two above results we obtain w(T)=w(Tβ€²)w(T) = w(T'). Hence Tβ€²=(V,(ETβˆ’{(x,y)})βˆͺ{(u,v)})T'=(V, (E_T - \{ (x,y)\}) \cup \{ (u,v) \}) is a minimum spanning tree containing (u,v)(u,v). Since AβŠ†ETA \subseteq E_T and (x,y)∉A(x,y) \not \in A, we have that the set
(Aβˆͺ{(u,v)})∈Tβ€²(A \cup \{(u,v)\}) \in T', as desired. This completes the proof. β– \blacksquare

Prim’s Algorithm

Intuitive Minimum Spanning Tree Algorithm

Now, using the Theorem 6, we can think of an algorithm which gradually builds a minimum spanning tree. We start from some vertex v∈Vv \in V and consider the cut ({v},Vβˆ’{v})(\{v\}, V - \{v\}). Since A=βˆ…A=\emptyset must be present as a subset of any minimum spanning tree edge set, by selecting the least cost edge from vv, say (v,w),w∈V(v,w), w \in V we can safely consider {(v,w)}\{(v,w)\} as a subset of some minimum spanning tree which is justified by Theorem 6. We repeat the process until we do not obtain a minimum spanning tree. We have just described the hand-wavy Prim’s algorithm. A careful reader may question the convergence of the process discussed and that will be addressed in the proof of the correctness of Prim’s algorithm.

Prim’s Algorithm implementation

Assumptions

Assume that the variable QQ holds the instance of a priority queue abstract data type. In the context of this algorithm, we assume that the priority queue is implemented as a binary heap.

prim pseudocode







Theorem 7: Proof of Correctness of Prim’s algorithm

Claim: Procedure Prim correctly computes the cost and the edge set of some minimum spanning tree.

Proof: (By induction)

We will consider the following invariant and prove it by induction:

Prior to the ii-th iteration of the while loop, where 1≀iβ‰€βˆ£V∣1 \leq i \leq |V|, the set SS contains the vertices of the β€˜partial’ minimum spanning tree defining the cut (S,Vβˆ’S)(S, V-S), the set AA contains the edges of the β€˜partial’ minimum spanning tree which are subset of edges of some actual minimum spanning tree and no edge in the set AA crosses the cut (S,Vβˆ’S)(S, V-S). The priority queue QQ stores vertices in Vβˆ’SV-S whose key is the cost of the minimum cost edge crossing the cut entering each vertex.

Basis: Prior to the first iteration of the while loop, corresponding to i=1i=1, A=βˆ…A=\emptyset, S=βˆ…S=\emptyset. Trivially, (βˆ…,V)(\emptyset, V) is a cut while AA is a subset of the edge set of any minimum spanning tree. The for loop in the line 2 ensures QQ is initialised correctly. Since there are no edges crossing the graph cut (S,Vβˆ’S)(S, V-S) the initialisation of QQ is indeed correct, so the basis is established.
Induction Assumption: Assume that the stated invariant holds for all iterations upto the ii-th iteration of the while loop.
Induction Step: By the invariant, the set SS contains the vertices of the β€˜partial’ minimum spanning tree defining the cut (S,Vβˆ’S)(S, V-S) and the set AA contains the edges of the β€˜partial’ minimum spanning tree which are subset of edges of some actual minimum spanning tree and no edge in the set AA crosses the cut (S,Vβˆ’S)(S, V-S). In the while loop body, the vertex uu is extracted from the priority queue.
The cut (S,Vβˆ’S)(S, V-S) is updated to (Sβˆͺ{u},Vβˆ’(Sβˆͺ{u}))(S \cup \{ u\}, V - (S \cup \{ u\})).
Suppose u=su=s. Then uu is the start vertex and there was no incoming edge. Observe that since uu is the start vertex, the graph (S,βˆ…)(S, \emptyset) is a tree and since AA is empty, it remains the subset of some minimum spanning tree while it does not cross the cut (S,Vβˆ’S)(S, V-S). We conclude that the graph (Sβˆͺ{u},βˆ…)(S \cup \{ u\}, \emptyset) is a tree.
Suppose uβ‰ su \neq s. By the invariant, (u.parent,u)(u.parent, u) is the minimum cost edge crossing the cut (S,Vβˆ’S)(S, V-S) entering the vertex uu. By Theorem 6, Aβˆͺ{(u.parent,u)}A \cup \{(u.parent, u)\} is a subset of edges of some minimum spanning tree. Lines 14,15 correctly update the set AA to Aβˆͺ(u.parent,u)A \cup (u.parent, u) and correctly increment the cost of the β€˜partial’ minimum spanning tree built so far. Since (S,A)(S, A) was a tree and (u.parent,u)(u.parent, u) is a crossing edge, Aβˆͺ(u.parent,u)A \cup (u.parent, u) does not induce any cycle so the graph (Sβˆͺ{u},Aβˆͺ{(u.parent,u)})(S \cup \{ u\}, A \cup \{(u.parent, u)\}) remains a tree.
Now the for loop in the line 16 considers all possible outgoing edges of uu. Observe that all those edges (u,v)(u,v), where vv is a vertex adjacent to uu are actually crossing edges. The conditional in line 17 correctly updates values of the minimum cost edge entering any vertex in the set (Vβˆ’S)βˆ’{u}(V-S) - \{ u \} if the update is necessary. Observe that those updates maintain the statement regarding QQ in the invariant. It is possible that not all crossing edges affecting QQ are considered. This is fine since the invariant for ii-th iteration guarantees that crossing edges which are not updated are still the least cost crossing edges. Therefore, the invariant is established for the next iteration.

Now consider what happens at the termination of the while loop. The while loop terminates precisely when Q=βˆ…Q=\emptyset. But then S=VS=V. By the invariant proved before, the β€˜partial’ minimum spanning tree includes all vertices in VV. By the invariant, AA is the set of edges of the β€˜partial’ minimum spanning tree which is also subset of edges of some minimum spanning tree. By invariant, (S,A)(S,A) is a tree. Since S=VS=V, we deduce (S,A)(S,A) is a spanning tree. Since AA is the subset of edges of some minimum spanning tree, we deduce (S,A)(S,A) is a minimum spanning tree. By invariant, the cost ΞΊ\kappa of (S,A)(S,A) was computed correctly. This completes the proof. β– \blacksquare

Some observations

  • According to Theorem 4, there exists a minimum spanning tree containing the least cost edge. Observe that this will be the top edge in the priority queue, which will be the first edge used to connect source vertex ss in the Prim’s algorithm
  • It is possible to adapt Prim’s algorithm to count minimum spanning trees. Observe that Prim’s algorithm implicitely resolves ties with respect to the edge cost by taking the first discovered edge of the particular cost. By performing the process of considering all edges of particular cost in growing a β€˜partial’ minimum spanning tree, by using any complete graph search algorithm (BFS, DFS, …) we can enumerate all minimum spanning trees.

Running time analysis of Prim’s Algorithm

Claim: Procedure Prim executes O((∣E∣)β‹…log(∣V∣))O((|E|) \cdot log(|V|)) operations.

Proof: Let TPrim(∣E∣,∣V∣)T_{Prim}(|E|, |V|) be the number of operations executed in the procedure Prim.

  • The for loop in the line 2 executes precisely ∣V∣|V| times and its body performs only constant time operations. Hence, there are ΞΈ(∣V∣)\theta(|V|) operations performed in this loop
  • Line 5 is a constant time operation
  • Line 6 is a min heap heapify operation which takes O(∣V∣)O(|V|) operations
  • Lines 7 to 9 are constant time operations

Now we analyse the main while loop. Each vertex gets extracted once and only once from the heap QQ. Each extraction operation takes O(log∣V∣)O(log|V|) operations. Observe that once that regardless of whether or not the if in the line 13 passes, there are at most constant number of operations in the while loop body except the inner for loop. Observe that for loop executes once and only once for each edge in EE across the whole execution of the algorithm. There are O(log∣V∣)O(log |V|) operations spent in each heap update. Since each edge gets considered from both endpoints, there can be at most 2β‹…O(∣E∣)=O(∣E∣)2 \cdot O(|E|) = O(|E|) heap operations throughout the whole execution of the algorithm coming from processing edges. Each such operation itself causes rebalancing the heap and hence takes O(log∣V∣)O(log |V|) operations. Hence the inner for loop contributes with O(∣E∣log∣V∣)O(|E| log |V|) operations throughout the whole execution of the algorithm. Recall, since the graph GG is connected, ∣E∣β‰₯∣Vβˆ£βˆ’1|E| \geq |V| - 1.

By summing up all contributions, we get:

TPrim(∣E∣,∣V∣)=O(∣V∣)+O(∣V∣)+3O(1)+O(∣Vβˆ£β‹…log∣V∣)+O(∣Eβˆ£β‹…log∣V∣)=O((∣V∣+∣E∣)β‹…log(∣V∣))=O((∣E∣)β‹…log(∣V∣)) \begin{aligned} T_{Prim}(|E|, |V|) &= O(|V|) + O(|V|) + 3O(1) + O(|V| \cdot log|V|) + O(|E| \cdot log|V|) \\ &= O((|V| + |E|) \cdot log(|V|)) \\ &= O((|E|) \cdot log(|V|)) \end{aligned}

This completes the analysis. β– \blacksquare

Kruskal’s Algorithm

Unlike Prim’s algorithm, which constructs a minimum spanning tree by β€˜growing’ a single β€˜partial’ minimum spanning tree, Kruskal’s algorithm takes a different approach. Kruskal’s algorithm relies on cleverly merging subtrees of a β€˜forest’ until the β€˜forest’ becomes a tree. Main idea is to start from a forest of ∣V∣|V| leaves representing each vertex and in each step connect two disjoint forest components corresponding to the least cost β€˜crossing’ edge. Theorem 6 gives conditions which guarantee the components merged in the process remain subtrees of some minimum spanning tree.

Here is a bit deeper explanation. Clearly, every vertex must be included in some minimum spanning tree. Hence every component in the initial forest of singleton vertex trees is a part of some minimum spanning tree. We can think of this as a β€˜base’ case. Now, suppose that we have a forest of components (trees) {C1,C2,…,Ck},1≀kβ‰€βˆ£V∣\{ C_1, C_2, \ldots, C_k\}, 1 \leq k \leq |V| for some kk. Assume all {C1,C2,…,Ck}\{ C_1, C_2, \ldots, C_k\} are parts of some (not necessarily the same) minimum spanning tree. Suppose AA is the set of edges of the forest. Now let (u,v)(u,v) be the edge connecting two distinct components, Ci,Cj,1≀i,j≀kC_i, C_j, 1 \leq i, j \leq k where iβ‰ ji \neq j and u∈Ci,v∈Cju \in C_i, v \in C_j. Observe that (u,v)(u,v) is crossing the cut (Ci,Vβˆ’Ci)(C_i, V - C_i). By Theorem 6, Aβˆͺ{(u,v)}A \cup \{ (u,v) \} is a subset of some minimum spanning tree. Observe that the number of components decreases by one every time a merge is performed. Hence the process completes after exactly ∣Vβˆ£βˆ’1|V|-1 iterations. One challenge is quickly determining whether uu and vv belong to distinct components. It turns out there is a data structure solving exactly this problem - disjoint sets. This process is the main intuition behind Kruskal’s algorithm:

kruskal pseudocode




Theorem 8: Proof of Correctness of Prim’s algorithm

Claim: Procedure Kruskal correctly computes the cost and the edge set of some minimum spanning tree.

Proof: (By induction)

We will consider the following invariant and prove it by induction:

Prior to the ii-th considered edge in the for loop in line 10, where 1≀iβ‰€βˆ£E∣1 \leq i \leq |E|, the set AA contains the edges of the forest {C1,C2,…,Ck},1≀kβ‰€βˆ£V∣\{ C_1, C_2, \ldots, C_k\}, 1 \leq k \leq |V|. AA is a subset of edges of some minimum spanning tree. Furthermore, AA contains all and only the edges which were minimum cost crossing edges connecting disjoint components discoverable in the first iβˆ’1i - 1 edges of EE in the sorted order. Edges in AA are the first discovered such edges.

Basis: Consider i=1i=1. By the for loop in the line 5, there are precisely ∣V∣|V| disjoint singleton trees in the forest {C1,C2,…,Ck},k=∣V∣\{ C_1, C_2, \ldots, C_k\}, k = |V|. Since the edge set AA is βˆ…\emptyset, and βˆ…\emptyset is a subset of any minimum spanning tree edge set, the invariant holds.
Induction Assumption: Assume the claim holds for iβˆ’1,iβ‰₯1i-1, i \geq 1.
Induction Step: Consider ii-th iteration. Suppose u∈Ci,v∈Cj,1≀i,j,≀ku \in C_i, v \in C_j, 1 \leq i,j, \leq k. Firstly, we prove that e=(u,v)e=(u,v) causes the union operation β€…β€ŠβŸΊβ€…β€Š\iff ee is a minimum cost edge crossing the cut (Ci,Vβˆ’Ci)(C_i, V-C_i) where no edge in AA crosses (Ci,Vβˆ’Ci)(C_i, V-C_i).
(←)(\leftarrow) Suppose e=(u,v)e=(u,v) causes the union operation. Then the correctness of disjoint set FindSet\texttt{FindSet} means iβ‰ ji \neq j so uu and vv belong to disjoint components CiC_i and CjC_j. Now consider the cut (Ci,Vβˆ’Ci)(C_i, V-C_i). Since AA contains all and only the edges in current forest and iβ‰ ji \neq j, it must be the case uu and vv are not connected in the current forest. But then, AA contains no edge crossing the cut (Ci,Vβˆ’Ci)(C_i, V-C_i) because otherwise uu and vv would be connected. We claim that (u,v)(u,v) is the minimum cost edge to connect uu and vv directly or indirectly. By the sorted order of EE, if there existed an edge to connect connect uu and vv directly or indirectly, that edge had to have the strictly smaller cost than (u,v)(u,v) and had to appear before (u,v)(u,v). But then, by invariant, that edge had to cause the union operation in some previous iteration. This means that (u,v)(u,v) now belong to the same connected component. This contradicts the fact iβ‰ ji \neq j. Hence (u,v)(u,v) is indeed a minimum cost edge to connect uu and vv directly or indirectly.
(β†’)(\rightarrow) Suppose ee is an edge crossing the cut (Ci,Vβˆ’Ci)(C_i, V-C_i) where no edge in AA crosses (Ci,Vβˆ’Ci)(C_i, V-C_i). Then, by the correctness of disjoint set FindSet\texttt{FindSet}, FindSet(u)β‰ FindSet(v)\texttt{FindSet(u)} \neq \texttt{FindSet(v)} so the union occurs.

We condition on whether e=(u,v)e=(u,v) causes the union operation or it does not.
Suppose e=(u,v)e=(u,v) causes the union operation. By the proof of the previous claim, e=(u,v)e=(u,v) is a minimum cost edge crossing the cut (Ci,Vβˆ’Ci)(C_i, V-C_i) where no edge in AA crosses (Ci,Vβˆ’Ci)(C_i, V-C_i). Since AA is a subset of edges of some minimum spanning tree, by Theorem 6, Aβˆͺ{(u,v)}A \cup \{(u,v)\} is also a subset of edges of some minimum spanning tree. The algorithm correctly updates AA and ΞΊ\kappa in lines 13,14 while correctly merges CiC_i and CjC_j in line 12. This establishes the invariant for the next iteration.
Suppose e=(u,v)e=(u,v) does not cause the union operation. Then FindSet(u)=FindSet(v)\texttt{FindSet(u)} = \texttt{FindSet(v)}. Then uu and vv belong to the same component, so AA contains some edge crossing (Ci,Vβˆ’Ci)(C_i, V-C_i). By the invariant, that edge had smaller or equal cost then (u,v)(u,v) so (u,v)(u,v) cannot improve the current forest and can only induce a cycle. Hence AA must not contain (u,v)(u,v). Components remain untouched so the invariant for the next iteration holds by the previous invariant and the fact (u,v)(u,v) should not be included in the set AA.
This proves the induction step.

After the termination of the main for loop, AA is a subset of edges of some minimum spanning tree. We claim (V,A)(V, A) is a minimum spanning tree. There are precisely ∣Vβˆ£βˆ’1|V| - 1 edges in any minimum spanning tree and all of them are connecting some disjoint components since removal of each edge disconnects that minimum spanning tree. Furthermore, all those edges are the minimum cost edges crossing some cut, because otherwise we can contradict the optimality of the minimum spanning tree by replacing them with a better alternative. We will show AA contains ∣Vβˆ£βˆ’1|V| - 1 edges. Assume (u,v)(u,v) is a minimum cost edge crossing some cut (Ci,Vβˆ’Ci)(C_i, V-C_i). By the invariant, if (u,v)(u,v) is the first such an edge in the sorted order of ∣E∣|E| it will be included in AA. Otherwise, there existed some other edge (uβ€²,vβ€²)(u', v') crossing the same cut (Ci,Vβˆ’Ci)(C_i, V-C_i) which was discoverable before (u,v)(u,v) which was included in AA by the invariant. Since (u,v)(u,v) was arbitrary, ∣A∣=∣Vβˆ£βˆ’1|A| = |V| - 1. Now, since any minimum spanning tree contains precisely ∣Vβˆ£βˆ’1|V| - 1 edges and AA is a subset of edges of some minimum spanning tree with ∣A∣=∣Vβˆ£βˆ’1|A| = |V| - 1, we deduce (V,A)(V,A) is a minimum spanning tree. This implies the correctness of the Kruskal’s algorithm. β– \blacksquare

Some observations

  • According to Theorem 4, there exists a minimum spanning tree containing the least cost edge. Observe that this will be the first edge in sorted edge set, which will be the first edge used to connect two leaves in the Kruskal’s algorithm.
  • An efficient implementation of Kruskal’s algorithm relies on disjoint sets data structure, which is a very specific and interesting data structure that can be implemented in many ways (as linked lists, as trees …). There are several obstacles in the implementation of disjoint sets which are solved by using path compression and weighted union heuristics.
  • Kruskal’s algorithm relies on the fast implementation of some sorting algorithm, which is one of the fundamental problems in computer science. If the distribution of edge costs is known, a faster linear time sorting algorithm can be employed.
  • Handling ties in Kruskal’s algorithm is very transparent and its execution is entirely deterministic after the sorting completes. Different sorting sorting algorithms used to sort edges may result in different resulting minimum spanning trees.

Running time analysis

Claim: Procedure Kruskal executes O(∣Eβˆ£β‹…log(∣E∣))O(|E| \cdot log(|E|)) operations.

Proof: Let TKruskal(∣E∣,∣V∣)T_{Kruskal}(|E|, |V|) be the number of operations executed in the procedure Kruskal. Now:

  • Lines 2..4 are constant time operations
  • The for loop in the line 5 contributes to ∣V∣|V| disjoint set make operations
  • The for loop in the line 7 executes ∣E∣|E| times and its body is a constant time operation.
  • Assuming the usage of the optimal comparison based sorting algorithm, the operation in line 9 takes O(∣E∣log(∣E∣))O(|E|log(|E|)) operations.

Now we apply the aggregate analysis to the main for loop in the line 10. Clearly, the main for loop executes precisely ∣E∣|E| times and each FindSet\texttt{FindSet} operation takes constant number of operations (by the properties of disjoint set data structure). Hence each execution of the main for loop takes at least 2β‹…O(1)=O(1)2 \cdot O(1) = O(1) number of operations. Now we will count the number of executions of the if body throughout entire execution of the main for loop. By Correctness of Kruskal’s algorithm, there will be exactly ∣Vβˆ£βˆ’1|V|-1 edges in AA. But that means there are exactly ∣Vβˆ£βˆ’1|V|-1 disjoint set union operations corresponding to executions of if body throughout entire execution of the main for loop. Using the properties of disjoint set data structure with weighted union, throughout entire execution of the algorithm, all disjoint set operations take O(∣V∣+∣Vβˆ£βˆ’1+∣E∣+∣V∣log(∣V∣))=O(∣V∣log(∣V∣)O(|V| + |V|-1 + |E| + |V|log(|V|)) = O(|V|log(|V|) atomic operations. Assuming the graph is connected, we have ∣E∣β‰₯∣Vβˆ£βˆ’1|E| \geq |V| - 1 so ∣V∣=O(∣E∣)|V| = O(|E|).

By summing up all contributions, we get:

TKruskal(∣E∣,∣V∣)=O(∣V∣)+O(∣E∣)+3O(1)+O(∣Eβˆ£β‹…log∣E∣)+O(∣V∣log(∣V∣))=O(∣V∣)+O(∣E∣)+3O(1)+O(∣Eβˆ£β‹…log∣E∣)+O(∣E∣log(∣E∣))=O((∣E∣)β‹…log(∣E∣)) \begin{aligned} T_{Kruskal}(|E|, |V|) &= O(|V|) + O(|E|) + 3O(1) + O(|E| \cdot log|E|) + O(|V|log(|V|)) \\ &= O(|V|) + O(|E|) + 3O(1) + O(|E| \cdot log|E|) + O(|E|log(|E|)) \\ &= O((|E|) \cdot log(|E|)) \end{aligned}

This completes the analysis. β– \blacksquare


Built with a lot of β˜•
Β© 2021