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?
TP must be identical to TK.
| |
If e is a minimum cost edge in G, e belongs to both TP and TK. | |
If TP is different from TK, some pair of edges in G have the same weight. | |
If e is a maximum cost edge in G, e belongs to neither TP nor TK.
|
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
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?
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?
After processing all m edges, the resulting graph is connected | |
What remains at the end is a minimum cost spanning tree | |
Exactly m-n+1 edges will be deleted. | |
At most n-1 edges will be deleted.
|
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
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?
Kruskal's algorithm will identify the same spanning tree on the new graph as on the old
graph. | |
Minimum cost spanning trees in the original graph will not correspond to minimum cost spanning trees in the new graph. | |
Prim's algorithm will not work on the original graph but will work on the modified graph | |
There are more minimum cost spanning trees in the modified graph than in the original
graph. |
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
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?
Dijkstra's algorithm for single source shortest paths | |
Bellman-Ford algorithm for single source shortest paths | |
Prim's algorithm for minimum cost spanning tree | |
Kruskal's algorithm for minimum cost spanning tree |
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
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]
[MSQ]
The least weighted edge is part of every MST. | |
The maximum weighted edge is not part of any MST. | |
The second smallest weighted edge is part of every MST. | |
The third smallest weighted edge is part of every MST. |
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
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
Question 6 |
Let G(V,E) be a connected graph with n vertices and m edges, and positive edge costs that you may assume are all distinct.
Let T=(V,E') be a spanning tree of G. We define the bottleneck edge of T to be the edge of T with greatest cost.
A spanning tree T of G is a minimum bottleneck spanning tree if there is no spanning tree T/ of G with a cheaper bottleneck edge.
Which of the following statement true?
S1: Every minimum bottleneck spanning tree of G a minimum spanning tree.
S2: Every minimum spanning tree of G is a minimum bottleneck spanning tree of G.
Let T=(V,E') be a spanning tree of G. We define the bottleneck edge of T to be the edge of T with greatest cost.
A spanning tree T of G is a minimum bottleneck spanning tree if there is no spanning tree T/ of G with a cheaper bottleneck edge.
Which of the following statement true?
S1: Every minimum bottleneck spanning tree of G a minimum spanning tree.
S2: Every minimum spanning tree of G is a minimum bottleneck spanning tree of G.
S1 is True and S2 is False | |
S1 is False and S2 is True | |
S1 and S2 are False | |
S1 and S2 are True |
Question 6 Explanation:
For S2 , MST select edges with minimum cost first. So, Every minimum spanning tree of G is a minimum bottleneck spanning tree of G.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 7 |
If a graph has n vertices, how many edges will be there in its Minimum Spanning Tree?
n | |
n-1 | |
n-2 | |
n+1 |
Question 7 Explanation:
Any tree has the basic properties are
1. It must be connected
2. total edges are n-1 with n vertices
3. No cycle or loop are there in tree.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
1. It must be connected
2. total edges are n-1 with n vertices
3. No cycle or loop are there in tree.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 8 |
What is the time complexity of Prims algorithm, provided the data structure used is an Array?
O(V^2) | |
O(\log V) | |
O(1) | |
O(V \log V) |
Question 9 |
Suppose we have computed a minimum spanning tree (MST) of a graph and its weight. If we make a new graph by doubling the weight of every edge in the original graph,
S1: we still need \Omega (E) time to compute the cost of the MST of the new graph.
S2: MST of original graph and new graph is unchanged.
S1: we still need \Omega (E) time to compute the cost of the MST of the new graph.
S2: MST of original graph and new graph is unchanged.
S1 is True and S2 is False | |
S1 is False and S2 is True | |
S1 and S2 are False | |
S1 and S2 are True |
Question 9 Explanation:
Consider sorting the edges by weight. Doubling the weight does not change the sorted order. But this means that Kruskal's and Prim's algorithm will do the same thing, so the MST is unchanged. Therefore the weight of the new tree is simply twice the weight of the old tree and can be computed in constant time if the original MST and weight are known.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 10 |
Consider the following Statements for a weighted connected undirected graph.
S1: If we use a max-queue instead of a min-queue in Kruskal's MST algorithm, it will return the spanning tree of maximum total cost (instead of returning the spanning tree of minimum total cost).
S2 : If we negating all the edge weights and running Kruskal's algorithm will return the spanning tree of maximum total cost (instead of returning the spanning tree of minimum total cost).
S1: If we use a max-queue instead of a min-queue in Kruskal's MST algorithm, it will return the spanning tree of maximum total cost (instead of returning the spanning tree of minimum total cost).
S2 : If we negating all the edge weights and running Kruskal's algorithm will return the spanning tree of maximum total cost (instead of returning the spanning tree of minimum total cost).
S1 is True and S2 is False | |
S1 is False and S2 is True | |
S1 and S2 are False | |
S1 and S2 are True |
Question 10 Explanation:
By using the max-queue, edges are inserted in MST in decreasing order of their weight. This will results in maximum spanning tree. Hence, S1 is true.
If we negating all the edge weights, then edge with higher weight (Ex. 10 becomes -10) become less weight and reverse for smaller weight edge (Ex. 1 becomes -1). Now, is we find MST based on this modification, we get maximum spanning tree. Hence, S2 is true.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
If we negating all the edge weights, then edge with higher weight (Ex. 10 becomes -10) become less weight and reverse for smaller weight edge (Ex. 1 becomes -1). Now, is we find MST based on this modification, we get maximum spanning tree. Hence, S2 is true.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
There are 10 questions to complete.