Minimum-Spanning-Tree
Question 1 |
Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ε V x V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
 | |
 | |
 | |
 |
Question 1 Explanation:
Method-1:
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge .
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V)
Method-2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method-1 is the most appropriate answer for giving a question.
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge .
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V)
Method-2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method-1 is the most appropriate answer for giving a question.
Question 2 |
Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i - j|. The weight of the minimum spanning tree of G is ______.
99 |
Question 2 Explanation:
• If there are n vertices in the graph, then each spanning tree has n − 1 edges.
• N =100
• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So 99 edges of weight is 99
• N =100
• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So 99 edges of weight is 99
Question 3 |
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 _________.
4 | |
5 | |
6 | |
7 |
Question 3 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
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 4 |
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?
(I) only | |
(II) only | |
both (I) and (II) | |
neither (I) nor (II) |
Question 4 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.
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 5 |
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 __________.
7 | |
8 | |
9 | |
10 |
Question 5 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.
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 6 |
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
I only | |
II only | |
both I and II | |
neither I nor II |
Question 6 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.
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 7 |
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 ______________.
69 | |
70 | |
71 | |
72 |
Question 7 Explanation:
⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69
Question 8 |
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 __________.
995 | |
996 | |
997 | |
998 |
Question 8 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 9 |
The number of distinct minimum spanning trees for the weighted graph below is ____
6 | |
7 | |
8 | |
9 |
Question 9 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 10 |
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?
T' = T with total weight t' = t2 | |
T' = T with total weight t' | |
T' ≠ T but total weight t' = t2 | |
None of the above |
Question 10 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.
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 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.
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
1/12(11n2-5n) | |
n2 – n + 1 | |
6n – 11 | |
2n + 1 |
Question 11 Explanation:
Let take example of 5 vertices,
Cost of MST,
= 3+4+6+8 = 21
Only option (B) satisfies it.
Cost of MST,
= 3+4+6+8 = 21
Only option (B) satisfies it.
Question 12 |
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
The length of the path from v5 to v6 in the MST of previous question with n =10 is11
| |
25 | |
31 | |
41 |
Question 12 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
Now MST of above graph is,
∴ The length of path from v5 to v6 in the MST is,
8+4+3+6+10 = 31
Question 13 |
7 | |
8 | |
9 | |
10 |
Question 13 Explanation:
Here the point to be noted is that vertex 0 is a leaf node. So degree of vertex 0 cannot be more than or equal to 2.
So, the edges of the spanning tree given that vertex 0 is a leaf node in the tree,
So, the minimum possible weight of spanning tree will be
= 1 + 4 + 2 + 3
= 10
So, the edges of the spanning tree given that vertex 0 is a leaf node in the tree,
So, the minimum possible weight of spanning tree will be
= 1 + 4 + 2 + 3
= 10
Question 14 |
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?
Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
| |
(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)
| |
(b,e)(a,c)(e,f)(b,c)(f,g)(c,d) | |
(b,e)(e,f)(b,c)(a,c)(f,g)(c,d) |
Question 14 Explanation:
To find Minimum Spanning Tree(MST) using Kruskal’s algorithm we have to follow standard procedure is
1. It follows like forest structure(Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
As per the options below Option A,B,C, are following correct order but Option D is violating Kruskal’s procedure. The edge between a-c of weight 4 comes after b-c of weight 3.
1. It follows like forest structure(Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
As per the options below Option A,B,C, are following correct order but Option D is violating Kruskal’s procedure. The edge between a-c of weight 4 comes after b-c of weight 3.
Question 15 |
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?
(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h) | |
(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i) | |
(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i) | |
(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)
|
Question 15 Explanation:
Prims algorithm starts from any vertex and expands MST by adding one vertex in each step which is close to the intermediate MST (made till previous step).
(A) (d, f) is chosen but neither 'd' nor 'f' vertices are part of previous MST (MST made till previous step).
(B) (g, h) is chosen but neither g or h vertices are part of MST made till previous step.
(C) Correct.
(D) (f, c) is chosen, but at that point (f, d) had less weight. So, (f , d) should have been chosen.
(A) (d, f) is chosen but neither 'd' nor 'f' vertices are part of previous MST (MST made till previous step).
(B) (g, h) is chosen but neither g or h vertices are part of MST made till previous step.
(C) Correct.
(D) (f, c) is chosen, but at that point (f, d) had less weight. So, (f , d) should have been chosen.
Question 16 |
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?
There is a minimum spanning tree containing e.
| |
If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
| |
Every minimum spanning tree has an edge of weight w. | |
e is present in every minimum spanning tree. |
Question 16 Explanation:
To find minimum Spanning tree(MST), may not be present ‘e’ in every MST graph.
Question 17 |
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
1 | |
2 | |
3 | |
n |
Question 17 Explanation:
If graph is connected and contains n vertices and n edges means there is possibility of only one cycle.
→ If we create a different spanning tree by removing one edge at a time.
→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.
→ If we create a different spanning tree by removing one edge at a time.
→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.
Question 18 |
Consider a weighted complete graph G on the vertex set {v1, v2, ... vn} such that the weight of the edge (vi, vj) is 2|i - j|. The weight of a minimum spanning tree of G is:
n-1 | |
2n-2
| |
 | |
n2 |
Question 18 Explanation:
1) Including the initial call which means write the length of the spanning tree, a simple one it is. (Based on a particular graph)
2)Weight of the minimum spanning tree = 2|2 - 1| + 2|3 - 2| + 2|4 - 3| + 2|5 - 4| .... + 2| n - (n-1) | = 2n - 2
2)Weight of the minimum spanning tree = 2|2 - 1| + 2|3 - 2| + 2|4 - 3| + 2|5 - 4| .... + 2| n - (n-1) | = 2n - 2
Question 19 |
Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?
Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?
(a—b),(d—f),(b—f),(d—c),(d—e)
| |
(a—b),(d—f),(d—c),(b—f),(d—e) | |
(d—f),(a—b),(d—c),(b—f),(d—e)
| |
(d—f),(a—b),(b—f),(d—e),(d—c)
|
Question 19 Explanation:
To find Minimum Spanning Tree(MST) using Kruskal’s algorithm we have to follow standard procedure is
1. It follows like forest structure (Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
Note: The edge d-e cannot be considered before d-c.
1. It follows like forest structure (Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
Note: The edge d-e cannot be considered before d-c.
Question 20 |
What is the weight of a minimum spanning tree of the following graph ?
29 | |
31 | |
38 | |
41 |
Question 20 Explanation:
1+2+3+2+8+4+4+2+5 =31
Question 21 |
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?
Every minimum spanning tree of G must contain emin | |
If emax is in a minimum spanning tree, then its removal must disconnect G | |
No minimum spanning tree contains emax | |
G has a unique minimum spanning tree |
Question 21 Explanation:
Minimum Spanning Tree:
Question 22 |
Theory Explanation is given below. |
Question 22 Explanation:
(b) 2 distinct MST's.
(c) Yes, it always. Because 'the edge weight 2 is unique'.
(d) Yes, it always. Because 'the edge weight 9 is unique'.
(c) Yes, it always. Because 'the edge weight 2 is unique'.
(d) Yes, it always. Because 'the edge weight 9 is unique'.
There are 22 questions to complete.