1,933 views
2 votes
2 votes
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?
 1. Kruskal's algorithm will identify the same spanning tree on the new graph as on the old graph.
 2. Minimum cost spanning trees in the original graph will not correspond to minimum cost spanning trees in the new graph.
 3. Prim's algorithm will not work on the original graph but will work on the modified graph.
4.  There are more minimum cost spanning trees in the modified graph than in the original graph.

is the correct answer 3 ?

1 Answer

1 votes
1 votes
I think ans is 1 (A)

In Kruskal's algorithm the safe edge added to A (subset of a MST) is always a least weight edge in the graph that connects two distinct components. So, if there are negative weight edges they will not affect the evolution of the algorithm.

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
3
Dulqar asked Jan 24, 2017
4,945 views
if T(n) = n2 √ n thenT(n) = O(n2)T(n) = O(n2 log n)T(n) = O(n3)None of the aboveIm getting option 2 is it correct ?