Consider the network below

In the above network, node $1$ is the source and node $5$ is the sink.

$($a$)$ Find a maximal flow by flow augmentation algorithm, and use first$-$label$-$first$-$scan

method to find an augmenting path at each stage.

$($b$)$ Construct an s$-$t cut $(x,\stackrel{}{x}),$ such that $C(x,\stackrel{}{x})$ equals the value of the flow you obtained

in $($a$).$

$($c$)$ Write down the incidence matrix of the above diagram.

$($d$)$ Assume an arc directed from node $5$ to node $1$ is added with the capacity $c_{51}=+.$

Write down the LP formulation of the above maximal flow problem.

$($e$)$ Construct the dual problem of the LP you obtained in $($D$).$