## Minimum-Spanning-Tree

 Question 1
Let G be any connected, weighted, undirected graph.
I. G  has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G  has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.
Which of the above statements is/are TRUE?
 A I only B II only C Both I and II D Neither I nor II
Algorithms       Minimum-Spanning-Tree       GATE 2019       Video-Explanation
Question 1 Explanation:
Given G be a connected, weighted and undirected graph,
I. TRUE: G Graph is unique, no two edges of the graph is same.

Step-1: Using Kruskal's algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step-2:

Step-3: 17 + 18 + 20 + 21 + 22 + 23 + 26 = 147
Step-4: Here, all the elements are distinct. So, the possible MCST is 1.
II. TRUE: As per the above graph, if we are cut the edge, that should the be the minimum edge.
Because we are already given, all minimum edge weights if graph is distinct.
 Question 2

Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is _________.

 A 4 B 5 C 6 D 7
Algorithms       Minimum-Spanning-Tree       GATE 2018       Video-Explanation
Question 2 Explanation:
Here, x = 5 because it is having maximum number of spanning trees.
If x = 5 then the total number of MWSTs are 4.
If r = 1

If r = 2

If r = 3

If r = 4

If r = 5

 Question 3
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
 A (I) only B (II) only C both (I) and (II) D neither (I) nor (II)
Algorithms       Minimum-Spanning-Tree       GATE 2017 [Set-1]       Video-Explanation
Question 3 Explanation:
If the graph has all positive and distinct (unique values no duplicates) then Statement-I definitely correct because if we are using either prim’s or kruskal’s algorithm it gives the unique spanning tree.
Let us take an example

Step 1:
Using kruskal’s algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step 2:

Step 3:
17+18+20+21+22+23+26 = 147
Step 4:
Here, all the elements are distinct. So the possible MCST is 1.
Statement-II: May or may not happen, please take an example graph and try to solve it. This is not correct always.
So, we have to pick most appropriate answer.
 Question 4

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is __________.

 A 7 B 8 C 9 D 10
Algorithms       Minimum-Spanning-Tree       GATE 2016 [Set-1]       Video-Explanation
Question 4 Explanation:
Let G be a complete undirected graph with 4 vertices & 6 edges so according to graph theory, if we use Prim’s / Kruskal’s algorithm, the graph looks like

Now consider vertex A to make Minimum spanning tree with Maximum weights.
As weights are 1, 2, 3, 4, 5, 6. AB, AD, AC takes maximum weights 4, 5, 6 respectively.
Next consider vertex B, BA = 4, and minimum spanning tree with maximum weight next is BD & BC takes 2, 3 respectively.
And the last edge CD takes 1.
So, 1+2+4 in our graph will be the Minimum spanning tree with maximum weights.
 Question 5
G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
 A I only B II only C both I and II D neither I nor II
Algorithms       Minimum-Spanning-Tree       GATE 2016 [Set-1]       Video-Explanation
Question 5 Explanation:
Statement-1: False
The MSTs of G may or may not include the lightest edge.
Take rectangular graph labelled with P,Q,R,S.
Connect with P-Q = 5, Q-R = 6, R-S = 8, S-P = 9, P-R = 7.
When we are forming a cycle R-S-P-R. P-R is the lightest edge of the cycle.
The MST abcd with cost 11
P-Q + Q-R + R-S does not include it.
Statement-2: True
Suppose there is a minimum spanning tree which contains e. If we add one more edge to the spanning tree we will create a cycle.
Suppose we add edge e to the spanning tree which generated cycle C.
We can reduce the cost of the minimum spanning tree if we choose an edge other than e from C for removal which implies that e must not be in minimum spanning tree and we get a contradiction.
 Question 6

The graph shown below 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ______________.

 A 69 B 70 C 71 D 72
Algorithms       Minimum-Spanning-Tree       GATE 2015 [Set-1]
Question 6 Explanation:

⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69

--> First we compare A-C and A-B we find 9 at A-C it means A-B must greater than A-C and for minimum possible greater value than 9 will be 10
-> Second we compare B-E and C-D in which we select B-E is 15 which C-D possible weight 16.
-> Third, we compare E-D and F-D in which we select F-D 6 means E-D must be greater than 6 so possible value greater than 6 is 7 .
 Question 7

Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes __________.

 A 995 B 996 C 997 D 998
Algorithms       Minimum-Spanning-Tree       GATE 2015 [Set-3]
Question 7 Explanation:
G has 100 vertices ⇒ spanning tree contain 99 edges given, weight of a minimum spanning tree of G is 500 since, each edge of G is increased by five. ∴ Weight of a minimum spanning tree becomes 500 + 5 ⨯ 99= 995
 Question 8

The number of distinct minimum spanning trees for the weighted graph below is _______.

 A 6 B 7 C 8 D 9
Algorithms       Minimum-Spanning-Tree       GATE 2014 [Set-2]
Question 8 Explanation:

Minimum Spanning Tree:

From the diagram, CFDA gives the minimum weight so will not disturb them, but in order to reach BE=1 we have 3 different ways ABE/ DBE/ DEB and we have HI=1, the shortest weight, we can reach HI=1 through GHI/ GIH.
So 3*2=6 ways of forming Minimum Spanning Tree with sum as 11.
 Question 9

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?

 A T' = T with total weight t' = t2 B T' = T with total weight t'2 C T' ≠ T but total weight t' = t2 D None of the above
Algorithms        Minimum-Spanning-Tree       GATE 2012
Question 9 Explanation:
Let graph G be

Then MST for G is,

Now let's square the weights,

Then MST for G' is,

So, from above we can see that T is not necessarily equal to T' and moreover (t1) < (t2).
So option (D) is correct answer.
 Question 10

An undirected graph G(V, E) contains n (n > 2) nodes named v1, v2, ….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| ≤ 2. Each edge (vi, vj) is assigned a weight i + j. A sample graph with n = 4 is shown below.

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

 A 1/12(11n2-5n) B n2 – n + 1 C 6n – 11 D 2n + 1
Algorithms        Minimum-Spanning-Tree       GATE 2011
Question 10 Explanation:
Let take example of 5 vertices,

Cost of MST,

= 3+4+6+8 = 21
Only option (B) satisfies it.
 Question 11

An undirected graph G(V, E) contains n (n > 2) nodes named v1, v2, ….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| ≤ 2. Each edge (vi, vj) is assigned a weight i + j. A sample graph with n = 4 is shown below.

The length of the path from v5 to v6 in the MST of previous question with n  =10 is

 A 11 B 25 C 31 D 41
Algorithms        Minimum-Spanning-Tree       GATE 2011
Question 11 Explanation:
Lets first draw graph with 10 vertices,

Now MST of above graph is,

∴ The length of path from v5 to v6 in the MST is,
8+4+3+6+10 = 31
There are 11 questions to complete.

Register Now