$(20$ points$)$ In class we have talked about EXTEND algorithm that

computes the shortest path between pair of vertices. You can start.

with the following definition of EXTEND, if $=$ExTEND$(L,W)$ then

$a_{ij}^{LW}=mi{n}_{1}kn(l_{ik}+w_{kj})$

Prove that Exrend is associative. In other words, if you have $3$ ma$-$

trices $A,B,$ and $C,$ then

Extend$(A,$Extend$(B,C))=$Extend$((Extend(A,B),C)).$

Specifically, show if

$D=$Extend$(A,B),$

$E=$Extend$(D,C),$

$F=$ExTENn$(B,C),$ and

$G=$Extend$(A,F^{\text{'}}),$

then $E=G.$

$(5$ points each$)$ Consider the following flow network.

$($a$)$ Draw the residual network for this flow.

$($b$)$ Find an augmenting path that increases at the flow across at least.

one edge and decreases the flow across another edge. Make the

flow be as large as possible for the chosen path.

$($c$)$ Describe the augmenting path as a ordered list of vertices and

state how much flow goes through it$.$

$($d$)$ Finally, draw a new flow graph with the augmented flow.

Please draw when necessary