Minimum Spanning Tree

Question

Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree.

True/False

Comments

@joshi_nitish

1) Adding a constant value to each of the edges can change the shortest path. TRUE

2) Can multiplying each edge by a constant value(c ) change the shortest path ? I think no !

Only cost of the shortest path will be changed i.e = c * old shortest path value

3) Adding a constant value to each of the edges can change the MST. FALSE

Only cost of the MST will be changed i.e = c * (#vertices -1) + Old cost

4) Multiplying each edge by a constant value(c) change the MST. FALSE

Only cost of the MST  will be changed i.e = c * Old cost

Can you verify ?

---

@VS

yes, all correct.

---

Can multiplying each edge by a constant value(c ) change the shortest path ?

Multiplying each edge by a constant value(c) change the MST

Both Yes in case of -ve constant. Correct me if I’m wrong.

Answer 1

YES.....BUT MST WILL REMAIN SAME.

NEW COST=OLD COST*X

X=POSITIVE NO.

Comments

To add: In case negative number is multiplied, MST may change.

Answer 2

only you will get change in shortest path value according to your multiplicative value remains will be same