Further Reading for Minimum Spanning Tree

Introduction

This is a supplement to the posts for Minimum Spanning Tree and their Analysis. Check out the other related articles in the following section.

Further Reading for Minimum Spanning Tree

This section is meant to be read in conjunction to the post Minimum Spanning Tree – Prim’s Algorithm

The minimum spanning tree of a Graph is the union of minimum spanning trees of its connected components.

This is a very important observation and it must be discussed in length and breadth because this will help us design our algorithm for MST in a
better way.

Why is it so important to understand this property of minimum spanning tree?

If we can somehow prove that the sub-graph G1 of a graph G(V,E) has a minimum spanning tree TG1. Then TG1 is a sub-tree of TG where TG is the minimum spanning tree of G.

Proof

In the below graphs the solid edges are the ones which are included in the Minimum Spanning Tree where as the dotted edges are the edges of the graph excluded from the MST.
Minimum Spanning Tree
Let us say that the above graph G(V,E) has a minimum spanning tree TG. Now let me remove an edge(a,b) from TG such that we get two connected components TG1 and TG2. We argue that both the components are minimum spanning trees induced by their respective set of vertices. Then the weight of the spanning tree TG can also be defined by W = W(a,b) + W(TG1) + W(TG2).
Minimum Spanning Tree

Let us prove this by contradiction.

Let us say that TG1 is not the minimum spanning tree of G1, then there is some T’G1 in G1 which has a lesser weight than TG1. Notice that we removed the edge (m,n) from T(G1) and added edge (p,m) to get T'(G1)
mst_4
And now when we take a union of T’G1 and TG2 and the edge (a,b) we get the below spanning tree and we must get the weight W’ = W(a,b) + W(T’G1) + W(TG2) and this should be smaller than the weight W.
mst_5

But our initial assumption was that W is the weight of the minimum spanning tree, which means no spanning tree can have weight lesser than W. Hence, by contradiction it is not possible for T’G1 to be the minimum spanning tree of G1.

The optimal substructure nature of MST

Now the above proof demonstrates that the minimum spanning tree exhibits the nature of an optimal sub-structure. To know more about optimal substructure you can read it here in the details of Dynamic Programming

In short it means that the bigger problem can be divided into small problems and the optimal solution to the smaller problem is a part of the optimal solution to the bigger problem.
In terms of Minimum Spanning Tree, an MST T’ of a sub-graph G’ of graph G is a sub-tree of the MST T of a Graph G.

The overlapping sub-problem nature of MST

To read more about the Overlapping problems you can again read the details of Dynamic Programming.

Why am I even pointing this out?
These are some traits which if exhibited by a problem, then the problem can be solved by Dynamic Programming. So does this problem exhibit the trait of Overlapping Sub-problem. Let us see that.

Considering the same Minimum spanning tree and by the above argument in the above section, we realize that the minimum spanning tree of a Graph contains several spanning trees of its sub-graphs. So, we can say that T is the union of T1, T2, T3 … Tn.

Consider the below image
mst_6
We have three sub problems for which the respective solutions are T1, T2 and T3. Now if we combine solutions for T2 and T3 we have solutions for two sub problems T1 and (T2, T3 combined). Hence, T2 overlapped in the solution of (T2 and T3 combined).

Also, if we combine T1 and T3 first and leave T2 aside. the final solution will still be same and here T3 overlapped for the solution of T1 and T3 combined.
In both the cases we sag.w that there are multiple overlapping sub-problems and it becomes an ideal candidate to be solved by the Dynamic Programming.

The Greedy nature of the MST problem

Let us consider the below minimum spanning tree with weight W. The remark states that if there is a minimum spanning tree for a Graph G(V,E) and U is a subset of V. And if edge(u,v) is the least weight edge connecting a vertex in U to a vertex in V-U. Then edge(u,v) must be in the minimum spanning tree. To understand more clearly let us look at the below image. The orange dots are vertices in U and the black ones are vertices in V – U.
mst_7
We are talking about the edge(u, v) which connects an orange dot to a black dot. Let us assume that this edge is not the edge with minimum weight and there exists another edge(u’, v’) which has minimum weight and connects an orange dot with the black dot. So we can safely replace edge(u, v) with edge(u’, v’) and get another tree, which ideally should have weight smaller than the weight W.

But this would be a contradiction to our hypothesis that the minimum spanning tree has the weight W. This means that there is a contradiction about edge(u’, v’) and it cannot have weight smaller than edge(u, v).

Hope you enjoyed reading. Don’t forget to subscribe to TechieMe to get updates on latest posts.

  • Harikrishna Patibandla

    you remove the edge (a,b) which is part of minimum spanning tree of G. We can divide the graph into two connected subgraphs by removing two edges from the minimum spanning tree.
    Suppose instead of removing (a,b), remove the other two edges that are incident on b.The obtained two sub-graphs are connected. Now find the minimum spanning trees of the two connected sub-graphs.
    PS: You answer is wrong!