Maximum flow and minimum cut: Definition & Examples

Maximum flow is the largest amount that can be routed from a source to a sink in a directed graph with limited link capacities. A minimum cut is a partition separating source from sink whose forward links have the smallest combined capacity. In a treasury routing model, a flow shows how much can be delivered, and a cut shows how much could possibly be delivered. When the two figures agree, the plan is optimal for the model.

Certify five without searching every route

Suppose a treasury desk can route divisible USD transfers from $s$ to $t$ via intermediaries $a$ and $b$ in one window. The link capacities are 3 on $s\to a$ , 2 on $s\to b$ , 1 on $a\to b$ , 2 on $a\to t$ and 3 on $b\to t$ , all in USD millions per window.

A feasible flow assigns each link an amount between zero and its capacity. Each intermediary must send out exactly what it receives. The value

F

is the net amount leaving

s

, which equals the net amount reaching

t

. MIT 6.854 flow notes

A feasible plan reaches five. Fill every link to capacity. At

a

, the incoming 3 splits into 1 to

b

and 2 to

t

. At

b

, 2 from

s

and 1 from

a

go to

t

. The sink receives

2+3=5

A cut caps every plan at five. Put

s

on one side and

a,b,t

on the other. The only links leaving the source side are

s\to a

and

s\to b

, so at most

3+2=5

can cross. The feasible plan meets that bound. Five is therefore the maximum flow value and this cut is a minimum cut.

In a fictional network, s→a carries 3 of 3, s→b 2 of 2, a→b 1 of 1, a→t 2 of 2 and b→t 3 of 3. The source cut has capacity 5. The residual graph has only reverse arrows and no path out of s.

The solid arrows carry the plan’s flow. The dashed arrows on the right show how much of that plan could be undone on each link.

Why a cut bounds the flow

For any partition $(S,T)$ with $s\in S$ and $t\in T$ , write $f(S,T)$ for the flow on links directed from $S$ to $T$ and $c(S,T)$ for their total capacity. Add up net outflow over all the nodes in $S$ . Flows between nodes inside $S$ cancel, and only the source contributes to the sum. This gives

F=f(S,T)-f(T,S)\leq c(S,T).

Flow on a link pointing back into

S

subtracts from the net transfer. Its capacity contributes zero to the cut capacity

c(S,T)

. The max-flow min-cut theorem says this bound is tight for a finite directed network with finite nonnegative capacities. The maximum feasible flow value equals the minimum cut capacity. This is a network example of duality in linear programming. MIT 6.854 flow notes · Ford and Fulkerson, §1

Reverse arrows revise the plan

The residual graph records changes available to the current plan. An original link

u\to v

carrying

f

out of capacity

c

contributes forward capacity

c-f

for adding flow and reverse capacity

f

for cancelling flow on that same link. An augmenting path runs from

s

t

on positive residual capacity. It increases the flow value by up to the smallest residual capacity along the path. MIT 6.854 flow notes

For example, start by assigning 1 to $s\to a\to b\to t$ . The residual path $s\to b\to a\to t$ has capacities 2, 1 and 2. Augment by 1. Keep the existing assignments on $s\to a$ and $b\to t$ , add 1 on $s\to b$ and $a\to t$ , and reduce $a\to b$ from 1 to 0. The two direct routes now carry 1 each. The residual step $b\to a$ cancels a draft assignment on $a\to b$ . A real transfer in that direction would require an original link of its own.

Ford–Fulkerson starts with zero flow and repeatedly augments along a path by its full bottleneck capacity. With integer capacities each step adds at least one unit, so a finite throughput bound guarantees termination. When there is no augmenting path, take

S

to be the vertices still reachable from

s

using positive residual capacity. Any original link leaving

S

must be full, since spare capacity would let the search reach its endpoint. Any original link entering

S

must carry zero, since otherwise its reverse residual arrow would let the search leave

S

. Hence

F=c(S,T)

. In the five-unit plan, the residual graph has only reverse arrows and none leaves

s

, so the search gives

S=\{s\}

. MIT 6.854 flow notes

The SelfMadeQuant lesson on Ford–Fulkerson traces a larger residual network and its next augmenting path. The full lesson requires membership.

What the bottleneck tells treasury

Increasing $s\to a$ from 3 to 4 leaves throughput at 5. The cut just before $t$ still has capacity $2+3=5$ , and the original plan still works. A link can sit on one minimum cut while another minimum cut continues to bind after an upgrade.

The estimate assumes one currency, a common time window, fixed transfer limits, and intermediaries that can pass on the funds they receive within the window. If payments must arrive in a specific order or depend on available intraday credit and collateral, those constraints need to be modelled before the routing can serve as a settlement schedule. Nellen’s study of intraday liquidity and settlement coordination

Certify five without searching every route

Why a cut bounds the flow

Reverse arrows revise the plan

What the bottleneck tells treasury

Sources

Related terms

Linear programming