please help Problem 3. Consider an undirected graph G-(V, E) with positive weigh

Question

please help

Problem 3. Consider an undirected graph G-(V, E) with positive weights we. Suppose that you have computed a minimum spanning tree G, and that you have also computed shortest paths to all vertices from a particular vertex s e V. Now suppose each edge weight is increased by 1: the new weights are w -we +1 (a) (15 points) Does the minimum spanning tree change? Give an example where it changes or prove it can not change. (b) (15 points) Do the shortest paths change? Give an example where they change or prove they cannot change.

Explanation / Answer

Solution:

a)

The minimum spanning tree won't change at all,

it is because we are increasing the edge weight of all the edges in the graph which means along with the edges in the MST the edge weight of non-MST edges will also increase so there won't be any contender left after the change to replace the MST edges.

Proof:

Suppose a graph G(V, E), has the T as it's minimum spanning tree and T has set of edges named as E', and suppose n vertices are there this means that T' will have n-1 edges

now every edge in E has become E+1, so does in the E', that is E'+1.

So the set of edges E' was in MST, because of E'<E, which is still the case because E'+1<E+1

This proves that the MST is still the same.

b)

So, if the MST is not changing then we can conclude that the shortest path also doesn't change.

However, the cost of the MST changes and it will increase by (n-1).

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.