Let G be a connected weighted graph. Suppose T$1$

is a Shortest Path Tree $($SPT$)$ of G rooted at some source vertex s$,$ and T$2$

is a Minimum Spanning Tree $($MST$)$ of G$.$ Now suppose we add a positive constant w to the weight of each edge of G and call the resulting weighted graph G$.$ Then, as a set of edges in G$\text{'},$

Question $13$Answer

a$.$

T$1$

may not be an SPT of G$\text{'},$ and T$2$

may not be an MST of G$\text{'}$

b$.$

T$1$

is an SPT of G$\text{'},$ and T$2$

is an MST of G$\text{'}$

c$.$

T$1$

may not be an SPT of G$\text{'},$ but T$2$

is an MST of G$\text{'}$

d$.$

T$1$

is an SPT of G$\text{'},$ but T$2$

may not be an MST of G$\text{'}$