I thought I understood max flow perfectly until I got to the exam and we got this. I know how to compute a maximum flow by means of the Ford-Fulkerson algorithm, specify the residual network and augmenting path. But here they gave us a graph where some of the capacities were already full (if you can tell from the picture) and I couldn't find a new augmenting path. Is there another way to solve this?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A full edge, e.g. $a \rightarrow c$, has a residual capacity of $0$ in the residual network. So you can't make an augmenting path over that directed edge. However the reversed edge, $c \rightarrow a$ has a residual capacity of $5$ (since $c_{c \rightarrow a} = 0$ and $f_{c \rightarrow a} = -5$). Therefore you can create an augmenting path using the reversed edge. The residual network would be:
E.g. a possible augmenting path would be $s \rightarrow c \rightarrow a \rightarrow d \rightarrow t$. You can increase the flow along that path by 5 and get the following flow network:
This is also the maximal flow, since $\{s, c\} - \{a, b, d, t\}$ forms a saturated s-t-cut.
