edited by
2,695 views
3 votes
3 votes
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.
edited by

2 Answers

1 votes
1 votes
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.
edited by
0 votes
0 votes
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) .
edited by

Related questions

0 votes
0 votes
0 answers
2
Malusi asked Jan 12
89 views
Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex r to u hasw...
0 votes
0 votes
1 answer
3
syedasafoora asked Nov 8, 2023
222 views
Consider the following algorithm for Build-Max-heap and the given array A=[ 47,96, 35, 54, 77, 65, 83]. Run this algorithm on the given array and redraw the heap and the ...
0 votes
0 votes
1 answer
4
LavTheRawkstar asked Feb 28, 2017
12,838 views
Consider the Knapsack incidence with n=3(items) with weights {w1,w2,w3}={2,3,4} and profits are {p1,p2,p3}={1,2,5}Given the capacity is 5,{W/M = 5 } Find the optimal solu...