Flow networks and maximum flow in WACE Mathematics Applications Unit 4

Finding the maximum flow

Traffic flows from $S$ to $T$ with capacities $S\to A = 7$, $S\to B = 5$, $A\to T = 4$, $A\to B = 3$, $B\to T = 8$.

Step 1: Identify a systematic set of cuts to evaluate.

A cut partitions all vertices into a group containing $S$ and a group containing $T$; its capacity is the total of only the forward edges crossing from the source side to the sink side. We try three natural cuts to bracket the maximum flow: one near the source, one near the sink, and one isolating an intermediate vertex.

Step 2: Compute the capacity of each candidate cut.

The cut separating $\{S\}$ from $\{A, B, T\}$ contains the edges $S\to A = 7$ and $S\to B = 5$, giving a capacity of $7 + 5 = 12$. The cut separating $\{S, A, B\}$ from $\{T\}$ contains the edges $A\to T = 4$ and $B\to T = 8$, giving a capacity of $4 + 8 = 12$. The cut placing $A$ on the sink side with $\{S, B\}$ on the source side contains $S\to A = 7$ and $B\to T = 8$, giving a capacity of $7 + 8 = 15$.

Step 3: Identify the minimum cut.

The smallest capacity found across all candidate cuts is $12$, achieved by both the source-side cut and the sink-side cut. No other partition produces a smaller value, so the minimum cut has capacity $12$.

Step 4: Apply the theorem to state the maximum flow and verify it.

By the maximum-flow minimum-cut theorem, the maximum flow from $S$ to $T$ equals the minimum cut capacity, which is $12$ units. We can verify this by constructing a valid flow: route $7$ units through $A$ (with $4$ continuing to $T$ and $3$ crossing to $B$) and $5$ units directly from $S$ to $B$. Then $B\to T$ carries $3 + 5 = 8$ and $A\to T$ carries $4$, totalling $12$ units into $T$, confirming that the capacity bound is achievable.