I need some assistance on a Prim's algorithm problem:
Let T be a minimum spanning tree of graph G obtained by Prim's algorithm. Let Gnew be a graph obtained by adding to G a new vertex and some edges with weights, connecting the new vertex to some vertices in G. Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T? If you answer yes, explain how; if no, explain why.
Thank you in advance!!
Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T?
No. Not in general.
Assume T has been generated by considering verteices in order v1,v2,...,vn-1
Let vn be the new vertex and (v1,vn) be a weighted edge (v1 is the root of T), if the weight of (v1,vn) is smaller than the weight of (v1,v2) in T, this would not be MST anymore.
not in all cases we can add new edge in T , it depends on the weight of new edges, because sometimes the old MST(T) will changes if the new edges weight is small than other weight in graph
No, this might be easier to visualize with a counter example:
as seen from above, not only is the new MST missing an edge compared to the original MST. It also uses both vertices instead of just one.
