D2 3.4, 3.5 - Multiple sources, sinks and restricted capacities

You already know

The labelling procedure starts from a feasible directed flow and uses forward and reverse residual arrows. Conservation holds at intermediate nodes. A feasible pattern and a matching valid cut bound prove that an optimum is attained.

Supersource and supersink

Join a supersource S to every original source $S_i$. Give $S\to S_i$ capacity equal to the sum of capacities leaving $S_i$.

Join every original sink $T_j$ to a supersink T. Give $T_j\to T$ capacity equal to the sum of capacities entering $T_j$.

The added arrows point into the original sources and out of the original sinks. They aggregate the total flow without imposing an extra bottleneck.

Worked example 1: two supplies and two destinations

Question. A network has arcs $S_1\to A$ of capacity $6$, $S_2\to A$ of capacity $5$, $A\to T_1$ of capacity $4$, and $A\to T_2$ of capacity $8$. Add a supersource and supersink, then determine the maximum total flow.

Plan. Give the artificial connectors their aggregate capacities, exhibit a feasible pattern and match it to a cut.

Add

The source-side cut has capacity $6+5=11$; the sink-side cut has capacity $4+8=12$.

Use real-arc flows

Give the corresponding artificial connectors the same flows.

Why is $7$, rather than $8$, sent to $T_2$? A receives only $11$, and $4$ of it goes to $T_1$. Capacities are available room, not compulsory amounts.

Answer. Maximum flow is $11$, attained by the displayed pattern and bounded by the cut through the two source connectors.

Check. A has inflow $6+5=11$ and outflow $4+7=11$; every real and artificial arc respects its capacity.

Worked example 2: recalculate the affected connector

Question. Find the new supersource connector capacity and maximum total flow.

Plan. Update the aggregate capacity leaving $S_1$, then produce a matching feasible pattern.

The connector $S\to S_1$ now has capacity $4$. The others remain $5,4,8$. Thus the source cut has capacity $4+5=9$.

Use

with the same corresponding connector flows.

Why change the artificial connector too? It is defined by the original source's outgoing capacity, not an independent extra supply.

Answer. The new maximum is $9$.

Check. A receives and sends $9$, the sink capacities allow this split, and the source cut prevents any larger total.

Watch out

Wrong: point a connector towards the supersource, add capacities of unrelated arcs, or assume every connector must be full. Right: use the prescribed directions and sums, then find a feasible overall pattern.

Splitting a restricted vertex

Replace a vertex A by two vertices $A_{\mathrm{in}}$ and $A_{\mathrm{out}}$.

• Direct every original incoming arc into $A_{\mathrm{in}}$.
• Direct every original outgoing arc out of $A_{\mathrm{out}}$.
• Join $A_{\mathrm{in}}\to A_{\mathrm{out}}$ with capacity equal to A's permitted throughput.

Keep every original arc's capacity and direction. Every unit passing through A must now use the new internal arc.

Worked example 3: a junction becomes the bottleneck

Question. Return to the original network with incoming capacities $6,5$ and outgoing capacities $4,8$. A can now pass at most $7$ units per second. Represent the restriction and find the maximum total flow.

Plan. Split A, insert a $7$-capacity internal arc, and attain its cut bound.

The internal arc is $A_{\mathrm{in}}\to A_{\mathrm{out}}$, capacity $7$. Use real-arc flows $6,1$ into $A_{\mathrm{in}}$, then $4,3$ out of $A_{\mathrm{out}}$. The internal flow is $7$.

The cut with

and all remaining nodes in Y crosses only the internal arc, so its capacity is $7$.

Why must every incoming arc end at $A_{\mathrm{in}}$? An incoming connection to $A_{\mathrm{out}}$ would bypass the restriction.

Answer. The split representation gives maximum flow $7$.

Check. The source supplies $6+1=7$, the internal arc carries $7$, and the destinations receive $4+3=7$.

Worked example 4: relax the vertex restriction

Question. Find the maximum total flow with the new vertex limit $9$.

Plan. Change only the capacity of the internal split arc and construct a new feasible split.

Set $c_{A_{\mathrm{in}}A_{\mathrm{out}}}=9$. Send $6,3$ from the original sources, pass $9$ along the internal arc, and send $4,5$ to the original sinks.

Why keep the other capacities fixed? The restriction belongs to the vertex. It does not alter any individual real pipe.

Answer. Maximum flow is $9$, matching the internal cut capacity $9$.

Check. Both source flows fit within $6,5$, both destination flows within $4,8$, and conservation holds at the two split nodes.

Watch out

Wrong: reduce every incoming capacity to the vertex limit, or leave an arc that bypasses the internal link. Right: preserve the original arcs and put the total-throughput limit on the single directed split arc.