Problem $3.$

Suppose we are given a undirected weighted graph G $=($V$,$ E; w$),$ where w : E $->$ R is the map to assign a

weight w$($e$)$ to each edgee in E$.$ Let T $$ be a minimum spanning tree of G$.$

a$)$ Now let G$1=($V$,$ E; w$1)$ be a modified version of G: In particular, G$1$ share the same vertex set and

edge set as G$.$ The only difference lies in the edge weights, where for any edge e in E$,$ the new weight

doubles the previous weight w$($e$)$; that is$,$ w$1($e$)=2$w$($e$).$

$($True or False$)$: The tree T $$ is still a minimum spanning tree for G$1$ as well. You do not need to

provide a justification.

b$)$ Now let G$2=($V$,$ E; w$2)$ be another modified version of G: In particular, G$1$ share the same vertex

set and edge set as G$.$ The only difference lies in the edge weights, where for any edge e in E$,$ the new

weight equals the previous weight w$($e$)+2$; that is$,$ w$2($e$)=$ w$($e$)+2.$

$($True or False$)$: The tree T $$ is still a minimum spanning tree for G$2$ as well. You do not need to

provide a justification.

c$)$ Let s in V be a source node. Let $$ T be a shortest path tree of G from the source s$.$ Consider the

modified graph G$2$ defined above.

$($True or False$)$: The tree $$ T is a shortest path tree for G$2$ from the source s as well.

Problem $3.$

Suppose we are given a undirected weighted graph $G=(V,E$;$w),$ where $w$:$ER$ is the map to assign a

weight $w(e)$ to each edgee inE. Let $T^{**}$ be a minimum spanning tree of $G.$

a$)$ Now let $G_1=(V,E$;$w_1)$ be a modified version of $G$ : In particular, $G_1$ share the same vertex set and

edge set as $G.$ The only difference lies in the edge weights, where for any edge einE, the new weight

doubles the previous weight $w(e)$; that is$,w_1(e)=2w(e).$

$($True or False$)$: The tree $T^{**}$ is still a minimum spanning tree for $G_1$ as well. You do not need to

provide a justification.

b$)$ Now let $G_2=(V,E$;$w_2)$ be another modified version of $G$ : In particular, $G_1$ share the same vertex

set and edge set as $G.$ The only difference lies in the edge weights, where for any edge einE, the new

weight equals the previous weight $w(e)+2$; that is$,w_2(e)=w(e)+2.$

$($True or False$)$: The tree $T^{**}$ is still a minimum spanning tree for $G_2$ as well. You do not need to

provide a justification.

c$)$ Let $sinV$ be a source node. Let widehat$(T)$ be a shortest path tree of $G$ from the source $s.$ Consider the

modified graph $G_2$ defined above.

$($True or False$)$: The tree widehat$(T)$ is a shortest path tree for $G_2$ from the source $s$ as well.