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.

the options for the above question are:

1.After processing all m edges, the resulting graph is connected.

2. What remains at the end is a minimum cost spanning tree.

 3.Exactly m-n+1 edges will be deleted.

 4.At most n-1 edges will be deleted.

Comments

Wat u want in d above ques?

---

please specify option

---

the options for the above question are:

1.After processing all m edges, the resulting graph is connected.

2. What remains at the end is a minimum cost spanning tree.

 3.Exactly m-n+1 edges will be deleted.

 4.At most n-1 edges will be deleted.

Answer 1

The algorithm specified is similar to the algorithm to find the minimal spanning tree using Kruskal's Algorithm, which uses disjoint set data structure. But, the edges are sorted in descending order here.

So, option (1) is true and (2) is not true.

Since, in a tree, for n vertices, we have n-1 edges, so m-n+1 edges will be deleted from a graph with m edges. So, option (3) is true.

Hence, option (4) is not true.

Comments

Isn't it given "sort the edges in decreasing order of cost"? So how does it give an MST? Please explain

---

Yes you are right. I overlooked that part. corrected.

---

But what if only one option has to be chosen ,then which one is more correct ?

---

Yes a nice point bro! Then I think 2 is the most appropriate answer.

Answer 2

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

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

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

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

Comments

But what if only one option has to be chosen ,then which one is more correct ?

---

I think option 2 would be apt because if the graph is a complete graph with four vertices then we need to delete atmost 3 edges (n-1=4-1=3) .