Is the maximum flow always unique?

Its optimal value is fixed, but several different edge-flow assignments can attain it.

Must every edge be full?

No. The worked example reaches its maximum with the cross-edge unused in one valid solution.

Can capacities be fractional?

The mathematical model allows nonnegative real capacities. Numerical implementations need suitable precision; integer-capacity formulations also have an integral optimal flow in the standard setting.

AI Glossary / Graphs and symbolic AI / Intermediate

Maximum Flow

Definition

Maximum flow is the largest feasible amount of a single commodity that can move from a designated source to a designated sink through a capacitated network. Each connection limits how much flow it can carry, and intermediate nodes conserve flow. The objective is total throughput, not the shortest route or the least expensive routing.

What it means

A network can have several routes operating at once. Finding one good path may leave useful capacity elsewhere unused, while summing all edge capacities counts capacity that cannot necessarily be used together. Maximum flow accounts for the interaction of routes and bottlenecks.

The commodity can represent material, data, or an abstract allocation quantity. In a time-based interpretation, all capacities must use a consistent rate or planning horizon. A static model with units per hour does not automatically describe travel times, temporary storage, changing demand, or queues. Those features need additional modeling when they affect the decision.

How it works

Build a directed graph with source s, sink t, and nonnegative edge capacities. Assign flow to each edge without exceeding its capacity. At every intermediate node, total inflow must equal total outflow. Maximize net flow leaving s, equivalently net flow entering t under these conditions.

Algorithms may use a residual network, which records remaining capacity and opportunities to reverse earlier routing choices. A reverse residual edge represents undoing part of a prior assignment; it need not correspond to a physical reverse pipe.

The max-flow/min-cut theorem supplies an optimality certificate: maximum flow equals the smallest capacity of a cut separating source from sink. A feasible flow and a cut with the same value prove the result, rather than merely showing that a particular routing appears full.

Three practical examples

Distribution planning: estimate throughput from an origin to a destination across intermediate facilities with stated transfer capacities.
Data-network design: identify a capacity bottleneck between two endpoints under a simplified single-commodity model.
Assignment modeling: transform a bipartite matching problem into a flow network with suitable unit capacities to represent compatible pairings.

Think of it this way

Think of a network of pipes carrying water from one tank to another. Narrow pipes can limit the whole system even when other pipes are wide. Several routes may carry water simultaneously.

The analogy is bounded: standard maximum flow does not model pressure, fluid physics, leakage, or nonlinear pipe behavior. It treats capacities as given numerical limits and assumes flow conservation at intermediate junctions.

Worked example

Use nodes s, A, B, and t. The directed capacities are s→A:5, s→B:4, A→t:3, B→t:4, and A→B:2. One feasible assignment sends 3 units along s→A→t and 4 along s→B→t, totaling 7.

Another maximum assignment sends 5 from s to A, sends 3 of those directly to t and 2 to B, and sends 2 from s to B. B then sends its combined 4 to t. Every intermediate inflow matches its outflow, and every edge respects its capacity.

Why is 7 optimal? The cut with source side {s,A,B} and sink side {t} has capacity 3+4=7. Every unit reaching t must cross that cut, so no feasible flow can exceed 7. Our assignment reaches the bound.

Increasing s→A alone from 5 to 8 does not raise throughput: the same cut still limits it to 7. Increasing A→t from 3 to 5 instead permits 5 along the A route and 4 along the B route, reaching 9. The source's total outgoing capacity is then a matching upper bound of 9.

Illustrative case study

Fictional case: a fulfillment team considers expanding a conveyor that feeds a sorting area. Its flow model shows unused upstream capacity but saturated final dispatch connections. Enlarging the proposed conveyor leaves maximum modeled throughput unchanged.

The team examines the limiting cut and evaluates a different capacity change. Before proceeding, it checks whether staffing schedules, item compatibility, and burst arrivals invalidate the static single-commodity assumptions. The fictional case illustrates how a bottleneck certificate can guide investigation; it does not claim a real facility improvement or guarantee that the mathematical capacity is achievable operationally.

Common misconceptions and mistakes

Maximum flow does not minimize cost, distance, or delay. Two optimal flows can route material differently and incur different costs. A minimum-cost flow model addresses the cost objective explicitly.

Do not assume each saturated edge is independently responsible for the bottleneck or that expanding one will improve the optimum. Several minimum cuts can exist. Likewise, multiple commodities competing for shared capacity generally require a richer formulation. A maximum-flow answer is exact for the stated model, not for every physical or operational feature omitted from it.

Business use

The method supports capacity analysis and certain allocation tasks because it returns both a throughput value and a feasible routing. A minimum cut can explain why more throughput is impossible under the current assumptions.

When implementing the model, validate directions, units, capacity completeness, and source/sink selection. NetworkX's maximum_flow routine returns the value and edge flows; its documented convention treats a missing capacity attribute as infinite capacity. That makes omitted data potentially consequential. Preserve explicit capacities and check the resulting flows against the intended network before interpreting them as an operational plan.

Check your understanding

the source in the worked network can send 9 units, so why is the original maximum only 7?

Answer: the two edges entering t have total capacity 7. They form a source - sink cut that every delivered unit must cross, limiting throughput despite spare source capacity.

Related terms

Flow network
edge capacity
flow conservation
residual graph
augmenting path
minimum cut
max-flow/min-cut theorem
bipartite matching
minimum-cost flow

Learn next

verify conservation and capacity limits for both worked assignments. Then find the limiting cut before and after the capacity change. Study residual networks to see how an algorithm can revise earlier choices, and minimum-cost flow when alternative routings have different costs.

Sources

NetworkX, maximum_flow documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.maximum_flow.html. Google OR-Tools, “Maximum Flows”: https://developers.google.com/optimization/flow/maxflow. Primary implementation documentation was read. The four-node calculations and cut certificates are original direct checks; no solver execution is claimed.

Previous: Maximum expected utility Next: Maximum inner-product search