Nptel Assignment Question

Question

Consider the following algorithm on a graph with edge weights.

• 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.

Comments

Hi, what graph are you starting with? If it is simple connected graph then A, B & C options are true, D is not true.

Answer 1

A. A tree is always connected.So this is correct option.…

 

B. The graph is sorted in descending order.thus after deleting an edge from the cycle , the graph that we receive is not a MST.Thus wrong option....

 

C. Since a tree is always connected so exactly m-n+1 needs to be deleted … Otherwise if m-n+2 edges are deleted the graph becomes disconnected and it no longer remains a tree...so option (3) is true...

 

D. Option 4 not be true because if the graph is a complete graph with four vertices then we need to delete at most 3 edges (n-1= 4 -1= 3) ...

 

1. https://gateoverflow.in/119398/Consider-the-following-algorithm-on-graph-with-edge-weights