Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DSA - Grand Test -Q25

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

Consider the following statements about Minimum spanning tree problem :

1$.$ Prims and Kruskals algorithms work even if some edges have negative weights.

2$.$ Let e be an edge with minimum weight in a graph. Then it belongs to some MST.

3$.$ Consider a cycle C in a connected graph G. Let e be the edge with the maximum weight in the cycle. Remove e from the graph G. Consider a MST T in the new graph. T is a MST in the original graph G as well.

Which of the above statements is/are true ?

(A)$.$ Only 3

(B)$.$ Only 2,3

(C)$.$ Only 1,2

(D)$.$ ALL

edited Oct 7, 2020

Yes, all are true.

The cycle Cn has n vertices and n edges

For MST, we need n-1 edges.

So in the MST, we will never include the edge of max weight unless, all the edges are not distinct.

Option C is correct.

Option A and B are also correct as

Kruskals algorithm is a greedy algorithm. so it will always pick edges with less weight.

SO all the negative weight edges will be chosen if there is no cycle. and likewise we will go.

So it will work in case of undirected graph.

Likewise Prims algo will work

We will create a min heap and build our MST in O(ElogV) time and it will also work with negative weight edges.

Option B is also correct because

If you have a minimum weight edge, it will always be a part of MST

Proof: NPTEL IIT delhi lecture by Dr. Naveen Garg.
answered Sep 26, 2020 by (11,240 points)