SECTION $1-$ Maximum Flow

$1.$ Max Flow with Ford$-$Fulkerson $(7$ points$)$

$1\mathrm{.}1$ Given this flow$/$capacity graph answer the following:

$($a$)$ Draw its associated $\backslash ($ G$\_\{$f$\}\backslash )$ indicating each $\backslash ($ c$\_\{$f$\}($u$,$ v$)\backslash ).[1$ point$]$

$($b$)$ Indicate what are the augmenting paths. Use a separate $\backslash ($ G$\_\{$f$\}\backslash )$ to identify each path. $[1$ point$]$

$1\mathrm{.}2$ Infer and draw the corresponding flow$/$capacity graph resulting if this augmenting path is chosen. Note that an edge in red in $\backslash ($ G$\_\{$f$\}\backslash )$ means $\backslash ($ c$\_\{$f$\}($u$,$ v$)$

otin E $\backslash ).[1$ point$]$

flow$/$capacity graph

$1\mathrm{.}3$ For this subsection, consider the following instances.

Ins

Show ALL steps of the following flow network by solving it using the Ford$-$Fulkerson method. At each step, use the left column to indicate the flow$/$capacity graph and use the right column to draw its corresponding residual network.

Instance $1$

flow$/$capacity graph

residual network $[1\mathrm{.}6$ points$]$

What is the max flow for the flow network?

$[0\mathrm{.}4$ points$]$

Instance $2$

flow$/$capacity graph

residual network $[1\mathrm{.}6$ points$]$

What is the max flow for the flow network?

$[0\mathrm{.}4$ points$]$

Explain and solve each questions in detail