Minimum Spanning Tree Algorithm Mock Test – 1


Question 1
Suppose we run Prim's algorithm and Kruskal's algorithm on a graph G and the two algorithms produce minimum-cost spanning trees TP and TK, respectively. Which of the following is true?
A
TP must be identical to TK.
B
If e is a minimum cost edge in G, e belongs to both TP and TK.
C
If TP is different from TK, some pair of edges in G have the same weight.
D
If e is a maximum cost edge in G, e belongs to neither TP nor TK.
   Algorithm
Question 1 Explanation: 
For a graph having more than one edges having same weight, different MST can be possible using kruskal's and prim's algorithm. Hence option A is false.
Here more than one edges possible with minimum cost weight. So it might possible that e will not be selected in resultant MST. Hence, option B is false.
It might possible that graph having maximum cost edge connect the vertice and removal of it disconnect the graph, then that edge must be part of MST. Hence, option D is false.
If prim's and kruskal's algorithm results in different MST but cost of MST must be same. To satisfy this, option C must be true.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 2
Consider the following algorithm on a graph with n vertices and m edges.

Sort the edges as [e1,e2,...,em] in decreasing order of cost.
Start with the original graph. Consider each edge ej. If this edge is part of a cycle delete it.

Which of the following is not true?
A
After processing all m edges, the resulting graph is connected
B
What remains at the end is a minimum cost spanning tree
C
Exactly m-n+1 edges will be deleted.
D
At most n-1 edges will be deleted.
   Algorithm
Question 2 Explanation: 
This is reverse version of Kruskal's algorithm. Any edge that is part of a cycle can be deleted without disconnecting the graph. In the end we get a minimum cost spanning tree with exactly n-1 edges. Hence, total edges deleted = m-(n-1)=m-n+1.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE


Question 3
Suppose we have a graph with negative edge weights. We take the largest magnitude negative edge weight -k and reset each edge weight w to w+k+1. Which of the following is true?
A
Kruskal's algorithm will identify the same spanning tree on the new graph as on the old graph.
B
Minimum cost spanning trees in the original graph will not correspond to minimum cost spanning trees in the new graph.
C
Prim's algorithm will not work on the original graph but will work on the modified graph
D
There are more minimum cost spanning trees in the modified graph than in the original graph.
   Algorithm
Question 3 Explanation: 
The ascending order of edge weights is unchanged if each edge weight is increased by k+1, so Kruskal's algorithm runs in exactly same way as before and produces the same tree. In general, since every spanning tree has exactly n-1 edges, the increase in weight uniformly affects all spanning trees, so the minimum cost spanning trees are unchanged. Prim's algorithm is not affected by negative weights.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 4
Which of the following is not a greedy algorithm?
A
Dijkstra's algorithm for single source shortest paths
B
Bellman-Ford algorithm for single source shortest paths
C
Prim's algorithm for minimum cost spanning tree
D
Kruskal's algorithm for minimum cost spanning tree
   Algorithm
Question 4 Explanation: 
Bellman-Ford implicitly tests all possible paths of length upto n-1 from the source node to every other node, so it is not greedy.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 5
Let G be a weighted connected graph. Assume that the weights are all distinct positive integers. Which of the following statements are true?

[MSQ]
A
The least weighted edge is part of every MST.
B
The maximum weighted edge is not part of any MST.
C
The second smallest weighted edge is part of every MST.
D
The third smallest weighted edge is part of every MST.
   Algorithm
Question 5 Explanation: 
As given that the weights are all distinct positive integers, least weight edge always becomes part of MST
It might possible that graph having maximum cost edge connect the vertex and removal of it disconnect the graph, then that edge must be part of MST.
second smallest weighted edge can never eliminated while removing the edges which create loops in MST. Hence, it is always part of MST.
Third smallest edge might create loop with two edges with minimum cost. So, resulting MST will not select this edge.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE


There are 5 questions to complete.

Leave a Comment