12.1 Flow Networks

Problem

You need to model the movement of resources through a constrained system. The resources may represent data packets, water, vehicles, products, workers, money, electricity, or any quantity that moves between locations. Each connection has a limited capacity, and the objective is to determine how much can be transported from a source to a destination while respecting all constraints.

Examples include:

• Delivering products from warehouses to stores
• Routing network traffic through routers
• Assigning workers to tasks
• Sending water through a pipe system
• Scheduling resources across projects

These seemingly different problems share a common mathematical structure known as a flow network.

Solution

Represent the system as a directed graph.

A flow network consists of:

• A set of vertices (V)
• A set of directed edges (E)
• A capacity function (c(u,v))
• A source vertex (s)
• A sink vertex (t)

Every edge has a maximum amount of flow that can travel across it.

Consider the following network:

Edge	Capacity
S → A	10
S → B	5
A → B	15
A → T	10
B → T	10

Graphically:

      10
   S ----> A
   |       |
 5 |       |10
   v       v
   B ----> T
      10

The source (S) produces flow.

The sink (T) consumes flow.

Intermediate vertices simply pass flow through the network.

Understanding Flow

A flow assignment specifies how much flow travels along each edge.

For example:

Edge	Capacity	Flow
S → A	10	10
S → B	5	5
A → B	15	0
A → T	10	10
B → T	10	5

The value of the flow equals:

10 + 5 = 15

units leaving the source.

Every flow must satisfy three fundamental rules.

Rule 1: Capacity Constraints

Flow can never exceed capacity.

For every edge:

flow ≤ capacity

A pipe with capacity 10 cannot carry 12 units.

Rule 2: Non-Negativity

Flow cannot be negative.

flow ≥ 0

Negative flow has no physical meaning in the basic model.

Rule 3: Flow Conservation

Every intermediate vertex must preserve flow.

Incoming flow equals outgoing flow.

For vertex (v):

incoming(v) = outgoing(v)

The vertex cannot create or destroy flow.

Formal Definition

A flow function:

f : E → ℝ

assigns a value to every edge.

It must satisfy:

Capacity

For every edge:

0 ≤ f(u,v) ≤ c(u,v)

Conservation

For every vertex except source and sink:

Σ f(incoming)
=
Σ f(outgoing)

Flow Value

The value of the flow equals total flow leaving the source.

|f|
=
Σ f(s,v)

or equivalently,

|f|
=
Σ f(v,t)

because conservation guarantees equality.

Example: Water Distribution

Suppose a reservoir supplies water to a city.

Edge	Capacity
Reservoir → Pump1	40
Reservoir → Pump2	30
Pump1 → City	20
Pump2 → City	25

The maximum delivery cannot exceed:

20 + 25 = 45

because the pipes entering the city form the bottleneck.

Although the reservoir can supply:

40 + 30 = 70

units, only 45 units can reach the destination.

This observation motivates one of the central ideas in flow theory: bottlenecks determine throughput.

Example: Data Network

Consider a packet-routing system.

RouterA ----> RouterB
     \          |
      \         |
       \        v
        ---> RouterC

Capacities represent bandwidth.

A 1 Gbps link can carry at most 1 Gbps of traffic.

The maximum traffic from source to destination becomes a flow problem.

Modern routing systems, content delivery networks, and cloud infrastructure frequently use concepts directly related to flow networks.

Modeling Tips

Sources and Sinks

Identify where resources originate.

These become source vertices.

Identify where resources are consumed.

These become sink vertices.

Capacities

Ask what limits movement.

Examples:

Domain	Capacity Meaning
Transportation	Vehicles per hour
Networks	Bandwidth
Manufacturing	Production rate
Scheduling	Available workers
Logistics	Shipment volume

Intermediate Vertices

Intermediate vertices usually represent:

• Warehouses
• Routers
• Factories
• Processing stages
• Distribution centers

Their role is to transfer flow.

Common Mistakes

Treating Undirected Edges as Directed

Flow networks are directed.

If movement is possible in both directions, create two directed edges.

Ignoring Bottlenecks

Large capacities near the source do not guarantee large overall flow.

The smallest cut in the network often determines throughput.

Violating Conservation

A common implementation error is allowing vertices to generate or lose flow.

Always verify:

incoming = outgoing

for every internal vertex.

Forgetting Units

All capacities should represent the same unit.

Examples:

• MB/s
• Vehicles/hour
• Tons/day

Mixing units produces invalid models.

Complexity Considerations

The flow network itself is simply a graph representation.

Storage requirements:

Representation	Space
Edge list	O(E)
Adjacency list	O(V + E)
Matrix	O(V²)

Most practical flow algorithms use adjacency lists because flow networks are often sparse.

When to Use Flow Networks

Flow networks are appropriate whenever a problem involves:

• Resource movement
• Capacity constraints
• Conservation laws
• Allocation decisions
• Routing decisions

Typical applications include:

• Maximum matching
• Supply-chain optimization
• Network routing
• Transportation planning
• Task assignment
• Image segmentation
• Project selection
• Scheduling

Many advanced algorithms in this chapter begin with a simple observation:

If a problem can be expressed as resources moving through constrained connections, it can often be transformed into a flow network.

This modeling step is the foundation upon which maximum flow, minimum cut, matching, circulation, and min-cost flow algorithms are built. In the next recipe, we will introduce residual graphs, the structure that makes efficient flow algorithms possible.