Question

What is the minimum spanning tree problem and how do we implement a solution? Discuss several graph problems and explore related algorithms.

Answer 1

Minimum spanning tree: A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

There are quite a few use cases for minimum spanning trees. One example would be a telecommunications company trying to lay cable in a new neighbourhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the triangle inequality. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable.

Minimum spanning Tree (MST) is an important topic for GATE. Therefore, we will discuss how to solve different types of questions based on MST. Before understanding this article, you should understand basics of MST and their algorithms

Type 1.

Conceptual questions based on MST: There are some important properties of MST on the basis of which conceptual questions can be asked as:

• The number of edges in MST with n nodes is (n-1).
• The weight of MST of a graph is always unique. However there may be different ways to get this weight (if there edges with same weights).
• The weight of MST is sum of weights of edges in MST.
• Maximum path length between two vertices is (n-1) for MST with n vertices.
• There exists only one path from one vertex to another in MST.
• Removal of any edge from MST disconnects the graph.
• For a graph having edges with distinct weights, MST is unique.

Que-1: Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false? (GATE CS 2000)
(A) Every minimum spanning tree of G must contain emin.
(B) If emax is in a minimum spanning tree, then its removal must disconnect G
(C) No minimum spanning tree contains emax
(D) G has a unique minimum spanning tree

Sol: As edge weights are unique, there will be only one edge emin and that will be added to MST, therefore option (A) is always true.
As spanning tree has minimum number of edges, removal of any edge will disconnect the graph. Therefore, option (B) is also true.
As all edge weights are distinct, G will have a unique minimum spanning tree. So, option (D) is correct.
Option C is false as emax can be part of MST if other edges with lesser weights are creating cycle and number of edges before adding emax is less than (n-1).

Type 2. How to find the weight of minimum spanning tree given the graph:
This is the simplest type of question based on MST. To solve this using kruskal’s algorithm,

• Arrange the edges in non-decreasing order of weights.
• Add edges one by one if they don’t create cycle until we get n-1 number of edges where n are number of nodes in the graph.

Que-2: Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

(A) 7
(B) 8
(C) 9
(D) 10

Solution: In the adjacency matrix of the graph with 5 vertices (v1 to v5), the edges arranged in non-decreasing order are:

(v1,v2), (v1,v4), (v4,v5), (v3,v5), (v1,v5),
(v2,v4), (v3,v4), (v1,v3), (v2,v5), (v2,v3)

As it is given, vertex v1 is a leaf node, it should have only one edge incident to it. Therefore, we will consider it in the end. Considering vertices v2 to v5, edges in non decreasing order are:

(v4,v5), (v3,v5), (v2,v4), (v3,v4), (v2,v5), (v2,v3)

Adding first three edges (v4,v5), (v3,v5), (v2,v4), no cycle is created. Also, we can connect v1 to v2 using edge (v1,v2). The total weight is sum of weight of these 4 edges which is 10.

Type 3. How many minimum spanning trees are possible using Kruskal’s algorithm for a given graph

• If all edges weight are distinct, minimum spanning tree is unique.
• If two edges have same weight, then we have to consider both possibilities and find possible minimum spanning trees.

Que – 3. The number of distinct minimum spanning trees for the weighted graph below is ____

(A) 4
(B) 5
(C) 6
(D) 7

Solution: There are 5 edges with weight 1 and adding them all in MST does not create cycle.
As the graph has 9 vertices, therefore we require total 8 edges out of which 5 has been added. Out of remaining 3, one edge is fixed represented by f.

For remaining 2 edges, one is to be chosen from c or d or e and another one is to be chosen from a or b. Remaining black ones will always create cycle so they are not considered. So, possible MST are 3*2 = 6.

Type 4. Out of given sequences, which one is not the sequence of edges added to the MST using Kruskal’s algorithm –
To solve this type of questions, try to find out the sequence of edges which can be produced by Kruskal. The sequence which does not match will be the answer.

Que – 4. Consider the following graph:

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm? (GATE-CS-2009)
(A) (b,e), (e,f), (a,c), (b,c), (f,g), (c,d)
(B) (b,e), (e,f), (a,c), (f,g), (b,c), (c,d)
(C) (b,e), (a,c), (e,f), (b,c), (f,g), (c,d)
(D) (b,e), (e,f), (b,c), (a,c), (f,g), (c,d)

Solution: Kruskal algorithms adds the edges in non-decreasing order of their weights, therefore, we first sort the edges in non-decreasing order of weight as:

(b,e), (e,f), (a,c), (b,c), (f,g), (a,b), (e,g), (c,d), (b,d), (e,d), (d,f).
First it will add (b,e) in MST. Then, it will add (e,f) as well as (a,c) (either (e,f) followed by (a,c) or vice versa) because of both having same weight and adding both of them will not create cycle.
However, in option (D), (b,c) has been added to MST before adding (a,c). So it can’t be the sequence produced by Kruskal’s algorithm.