Flows in networks

Explanation

• In a directed network with source $S$ and sink $T$, a cut is a set of arcs whose removal separates the network into two parts $X$ and $Y$, where $X$ contains at least $S$ and $Y$ contains at least $T$. Equivalently, choose which side of the cut each vertex lies on, with $S$ in $X$ and $T$ in $Y$;
• the cut is then the set of arcs crossing between the two sides. The capacity of the cut is the sum of the capacities of those arcs that are directed from $X$ to $Y$ only.
• An arc directed from $Y$ back to $X$ contributes nothing, because flow along it does not help material reach $T$; this is the single most common error.
• If a network has $n$ vertices besides $S$ and $T$, there are $2^n$ cuts, since each of those vertices may be placed on either side.
• Every cut is an upper bound for the flow, because everything reaching $T$ must cross from $X$ to $Y$ at some point, so the maximum flow is at most the smallest cut capacity.

Explanation

• The labelling procedure records, on every arc, both how much more flow it could take and how much of its current flow could be removed. The arrow drawn in the same direction as the arc gives the excess capacity, and the arrow drawn in the opposite direction gives the amount by which the flow could be reduced;
• the two always add to the capacity of the arc.
• Starting from any feasible flow, look for a flow-augmenting route from $S$ to $T$ along which every forward arc has a positive excess capacity and every backward arc has a positive current flow. The amount of the augmentation is the smallest of those numbers along the route.
• Update the labels on every arc of the route, adding the augmentation to the flow on forward arcs and subtracting it on backward arcs, and repeat.
• When no flow-augmenting route can be found, the flow is maximal. The value of the flow is the total leaving $S$, which must equal the total entering $T$.

Explanation

• The max-flow min-cut theorem states that in any network the value of the maximum flow equals the capacity of the minimum cut. One half is easy: every flow is at most every cut, because everything reaching the sink crosses the cut somewhere.
• The theorem asserts that the bound is attained, so exhibiting a flow and a cut of the same value proves both are optimal at once, with no further searching.
• In an examination this is the standard way to justify an answer: state the value of the flow you have found, name a cut, compute its capacity and observe that the two numbers agree.
• The minimum cut can always be found from a maximum flow: put in $X$ the source together with every vertex reachable from $S$ along arcs that still have spare capacity or, backwards, carry flow, and put everything else in $Y$.
• Every arc from $X$ to $Y$ is then saturated and every arc from $Y$ to $X$ is empty, which is exactly the equality case of the bound.

Explanation

• Two standard devices reduce awkward networks to the ordinary case.
• If a network has several sources $S_1,S_2,\dots$, connect them all to a single supersource $S$; the capacity of the arc from $S$ to $S_i$ is the sum of the capacities of the arcs leaving $S_i$, so the new arc never restricts anything the original network allowed.
• Several sinks $T_1,T_2,\dots$ are handled symmetrically with a supersink $T$, the arc from $T_j$ to $T$ having capacity equal to the sum of the capacities of the arcs entering $T_j$.
• If instead a vertex $V$ has a restricted capacity, meaning that only a limited amount may pass through it, replace $V$ by two vertices $V_1$ and $V_2$, direct every arc that entered $V$ into $V_1$, direct every arc that left $V$ out of $V_2$, and join them by a single arc $V_1V_2$ whose capacity is the restriction.
• Any flow through $V$ must now use that arc, so the restriction is enforced automatically, and the labelling procedure and the max-flow min-cut theorem apply to the modified network unchanged.

Explanation

• Some networks impose a lower capacity as well as an upper capacity on each arc,
• so the flow along that arc must lie between the two. A flow is feasible only if it respects every lower and upper capacity and conserves flow at every internal vertex, and a first feasible flow now has to be constructed rather than started from zero.
• The definition of the capacity of a cut changes accordingly: it is the sum of the upper capacities of the arcs crossing from $X$ to $Y$ minus the sum of the lower capacities of the arcs crossing from $Y$ to $X$. The maximum flow is still the minimum of these cut capacities.
• For the minimum flow the roles are reversed: a cut gives the lower bound obtained by adding the lower capacities of the arcs from $X$ to $Y$ and subtracting the upper capacities of the arcs from $Y$ to $X$, and the minimum flow is the largest of those numbers.
• In practice, questions ask for the range of possible flow rates, so both calculations are needed, together with a feasible flow attaining each end.