Maximum Flow Problem¶

Definition¶

The maximum flow problem assigns nonnegative flow $x_{ij}$ to the edges of a directed network, subject to capacities $x_{ij}\le c_{ij}$ and flow conservation (inflow equals outflow) at every intermediate vertex, that is, every vertex other than the source and the sink. The course assumes the source has only outgoing edges and the sink only incoming edges. The objective is to maximize total source outflow, equivalently total sink inflow.

Interpretation¶

The maximum flow problem asks how much can be sent from a source to a sink through a network of directed connections with limited capacity. Intermediate vertices pass flow on rather than create or consume it.

A network from A to F with flow and capacity on each edge, a total flow of 8 leaving A, and a vertical cut through two saturated edges of total capacity 8.

Each edge is labelled flow/capacity. The source $A$ sends $3+5=8$ $8$ , and every intermediate vertex passes on what it receives; for example, $D$ receives $3+2=5$ and sends $5$ to $F$ . The dashed line separates $F$ from the other vertices; the only edges crossing it, $D\to F$ and $E\to F$ $F$ , are full and have total capacity $5+3=8$ $8$ , so no flow can exceed 8 and the flow shown is maximum.

The capacity constraints $x_{ij}\le c_{ij}$ bound the flow on each edge, nonnegativity keeps flow in the direction of the edge, and the conservation constraints balance incoming and outgoing flow at intermediate vertices. Without conservation, an intermediate vertex could simply absorb what the source sends, and the source outflow would no longer measure what reaches the sink.

The value of a flow is the source outflow, not the sum of all edge flows: in the figure the edge flows add up to $24$ , while the value is $8$ , since a unit that travels over three edges is counted once.

The augmenting path algorithm finds a maximum flow using the residual network. Later in the course, the same model is written as a linear program.

Key Results¶

Flow into each intermediate vertex equals flow out.
The same maximum value can have several feasible edge-flow assignments.
Residual reverse capacity permits earlier routing choices to be revised.

Examples¶

The illustrated flow has source outflow $3+5=8$ $8$ , and each intermediate vertex passes on what it receives (for example, $C$ receives 5 and sends $2+3$ $3$ ). A cut splits the vertices into a source side and a sink side; its capacity is the total capacity of the edges directed from the source side to the sink side, and no feasible flow value exceeds the capacity of any cut. The red dashed cut in the figure separates $\{A,B,C,D,E\}$ from $\{F\}$ : only $D\to F$ and $E\to F$ cross it, with capacity $5+3=8$ $8$ , so no feasible flow can exceed 8. Attaining that cut bound certifies maximality.

A minimum cut need not be unique: the cut separating $\{A,B,C,E\}$ from $\{D,F\}$ is crossed by $B\to D$ $D$ , $C\to D$ and $E\to F$ and also has capacity $3+2+3=8$ $8$ .
Week 4 course examples (networks not shown on this page) use source $S$ and sink $T$ : the main example has maximum flow 15, and Week 4 practice 7 reaches 16, with 9 entering $T$ from $D$ and 7 from $E$ .

Prerequisites¶

Sources¶

OR Modelling · Week 4

Aliases: max-flow problem, maximal flow problem

Last updated: 20 October 2026 03:02