Maximum Flow
Problem
In the second example the network is a cube. Find the maximum flow from $A$ to $G$.
Getting Started
Student Solutions
Yanqing from Lipson Community College and Andrei from Tudor Vianu National College, Bucharest, Romania both sent correct solutions.
Andrei wrote:
" As I am not familiar with graph theory, I first read the hint and the notes of the problem, then I looked on the web for the Maximum flow, minimum cut theorem. I found different examples, algorithms of solving such problems, as well a possible list of utilisation.
I started with the definition of terms: a cut in a network is a minimal set of edges whose removal separates the network into two components, one containing the source, and the other the sink."
In the first network a cut through $PT$, $RT$, $RU$, $RB$, and $SB$ separates the network showing that the flow cannot be more than $18$ units (the total flow through these edges).
This flow is possible by sending: $3$ units along $ASB$, $5$ units along $ASRB$, $5$ units along $ARB$, $2$ units along $ARUTB$, $1$ unit along $AQRTB$ and $2$ units along $APTB$. Hence the maximum flow is $18$ units.
In the second network a cut through $BC$, $DC$, $FG$ and $HG$ separates the network so the flow cannot be more than $16$ units (the total flow along these edges).
This flow is possible by sending $3$ units along $ABFG$, $4$ units along $ABCG$, $2$ units along $ADCG$, $3$ units along $ADHG$ and $4$ units along $AEHG$. Hence the maximum flow is $16$ units.
Teachers' Resources
There is a 'Maximum flow, minimum cut' theorem for which the proof is sketched in this question. Finding the solutions requires all cases to be checked.