1
$\begingroup$

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? enter image description here

$\endgroup$

1 Answer 1

2
$\begingroup$

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:

enter image description here

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:

enter image description here

This is also the maximal flow, since $\{s, c\} - \{a, b, d, t\}$ forms a saturated s-t-cut.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.