Let G$=($V$,$E$,$w$)$

be a connected weighted graph in which each edge e in E

has weight w$($e$)>0$

$.$ 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 consider keeping the same set of vertices and edges, but modifying the edge weights to get a modified graph G$^=($V$,$E$,$w$^)$

$,$ where the modified edge weights are defined as w$^($e$)=(4+$w$($e$))(7+$w$($e$))$

$,$ for each edge e in E

$.$

Then, as a set of edges in G$^$

$,$

Question $29$Answer

a$.$

T$1$

is an SPT of G$^$

$,$ and T$2$

is an MST of G$^$

$.$

b$.$

T$1$

may not be an SPT of G$^$

$,$ but T$2$

is an MST of G$^$

$.$

c$.$

T$1$

is an SPT of G$^$

$,$ but T$2$

may not be an MST of G$^$

$.$

d$.$

T$1$

may not be an SPT of G$^$

$,$ and T$2$

may not be an MST of G$^$

$.$