680 views
0 votes
0 votes
Suppose, the MST of a graph of n vertices has already been constructed. Now, if one new vertex is added to the graph along with 'i' incident edges. What is the max number of edges that can change in MST of new graph w.r.t to old MST?

a) 1    b) n       c) Number of incident edges on new vertex n-i

d) none of these

1 Answer

0 votes
0 votes
Maximum will be N,when i=N.Because suposse the newly added node can join all the vertex with mimimum cost,then we will have to replace all older edges.

Related questions

1 votes
1 votes
1 answer
2
0 votes
0 votes
0 answers
4