CODEWITHSUNDEEP
graphhelperminimum-spanning-treeprims-algorithm
Steve
Steve

Reputation: 33

Minimum spanning tree of graph obtained by Prim's algorithm

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!!

Upvotes: 1

Views: 2456

Answers (3)

kitkatsim
kitkatsim

Reputation: 79

No, this might be easier to visualize with a counter example: MST 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.

Upvotes: 0

ahmed sayed
ahmed sayed

Reputation: 1

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

Upvotes: 0

Xline
Xline

Reputation: 812

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.

Upvotes: 2

Related Questions