Network Flows

Introduction

Network flow theory studies how commodities, information, or other quantities move through networks. Consider water flowing through pipes, traffic through road networks, or data through communication channels. Each edge has a capacity limiting how much can flow through it, and the fundamental question is: what is the maximum amount that can be transported from a source to a destination?

Network flow problems have diverse applications including transportation logistics, telecommunications, bipartite matching, project selection, and image segmentation. The mathematical theory reveals deep connections between maximum flows and minimum cuts.

Flow Networks

A flow network is a directed graph G=(V,E) with:

A source vertex s∈V with no incoming edges.

A sink (target) vertex t∈V with no outgoing edges.

A capacity function c:E→(ℝ_≥0) assigning a non-negative capacity c(u,v) to each edge (u,v)

Definition of Flow

A flow is a function ƒ:E→(ℝ_≥0) satisfying two constraints:

Capacity Constraint

For every edge (u,v)∈E

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

The flow through an edge cannot exceed its capacity.

Flow Conservation

For every vertex v∈V∖{s,t}

(∑_u:(u,v)∈E^)(ƒ(u,v))=(∑_w:(v,w)∈E^)(ƒ(v,w))

Total flow into a vertex equals total flow out (except at the source and sink).

Value of a Flow

The value of a flow ƒ is the net flow leaving the source:

|ƒ|=(∑_v:(s,v)∈E^)(ƒ(s,v))−(∑_u:(u,s)∈E^)(ƒ(u,s))

By flow conservation, this equals the net flow entering the sink. The maximum flow problem asks: find a flow ƒ maximizing |ƒ|

Cuts

An s-t cut is a partition of vertices into sets (S,T) where s∈S and t∈T The capacity of a cut is the sum of capacities of edges from S to T

c(S,T)=(∑_u∈S,v∈T:(u,v)∈E^)(c(u,v))

A minimum cut is a cut with the smallest capacity among all s-t cuts.

Max-Flow Min-Cut Theorem

One of the fundamental results in combinatorial optimization is the max-flow min-cut theorem:

The value of a maximum flow equals the capacity of a minimum cut.

(max_ƒ)(ƒ)=(min_(S,T))(c(S,T))

This theorem has a natural interpretation: the maximum amount that can flow from source to sink is limited by the bottleneck cut, and this limit is always achievable.

Residual Networks

Given a flow ƒ the residual network (G_ƒ) represents remaining capacity. For each edge (u,v) in the original network:

The residual capacity is (c_ƒ)(u,v)=c(u,v)−ƒ(u,v) (remaining forward capacity).

A backward edge (v,u) with residual capacity (c_ƒ)(v,u)=ƒ(u,v) represents the ability to reduce flow.

Ford-Fulkerson Method

The Ford-Fulkerson method is an iterative approach to finding maximum flow:

Initialize ƒ(u,v)=0 for all edges.

While there exists an augmenting path p from s to t in the residual network:

Find the bottleneck capacity (c_ƒ)(p)=(min_(u,v)∈p)((c_ƒ)(u,v))

Augment flow along path p by (c_ƒ)(p)

When no augmenting path exists, the current flow is maximum.

Edmonds-Karp Algorithm

The Edmonds-Karp algorithm implements Ford-Fulkerson using BFS to find shortest augmenting paths. This guarantees termination and runs in O*(V*E2) time.

Applications

Bipartite Matching

Maximum bipartite matching can be solved as a max flow problem. Given a bipartite graph with vertex sets L and R add a source connected to all vertices in L and a sink connected from all vertices in R with all capacities equal to 1. The maximum flow equals the maximum matching size.

Edge-Disjoint Paths

The maximum number of edge-disjoint paths from s to t equals the maximum flow when all edge capacities are 1. By the max-flow min-cut theorem, this also equals the minimum number of edges whose removal disconnects s from t (Menger's theorem).

Image Segmentation

In computer vision, minimum cuts can separate foreground from background in images. Pixels are vertices with edges to neighbors; edge weights reflect similarity. A minimum cut finds the optimal boundary.

Proof of Max-Flow Min-Cut Theorem

The proof establishes three equivalent conditions: (1) ƒ is a maximum flow, (2) there is no augmenting path in (G_ƒ) and (3) |ƒ|=c(S,T) for some cut (S,T)

Key insight: for any flow ƒ and any cut (S,T) the flow value |ƒ| equals the net flow across the cut:

|ƒ|=(∑_u∈S,v∈T^)(ƒ(u,v))−(∑_u∈T,v∈S^)(ƒ(u,v))≤c(S,T)

Thus every flow is bounded by every cut. When equality holds, both are optimal.

Minimum Cost Flows

In minimum cost flow problems, each edge also has a cost w(u,v) per unit of flow. The goal is to find a flow of a specified value d that minimizes total cost:

min((∑_(u,v)∈E^)(w(u,v)))⋅ƒ(u,v)*subject to *|ƒ|=d

This generalizes shortest path, maximum flow, and assignment problems. Algorithms include successive shortest path and cycle-canceling methods.

Multiple Sources and Sinks

Problems with multiple sources {(s_1),…,(s_k)} or sinks {(t_1),…,(t_m)} reduce to single source-sink problems by adding a super-source connected to all sources and a super-sink connected from all sinks.

Summary

A flow network is a directed graph with edge capacities, a source, and a sink. A flow assigns non-negative values to edges respecting capacity constraints and conservation (flow in equals flow out at internal vertices).

The max-flow min-cut theorem establishes that the maximum flow value equals the minimum cut capacity. This fundamental duality has algorithmic implications: finding a maximum flow also finds a minimum cut.

The Ford-Fulkerson method iteratively augments flow along paths in the residual network. The Edmonds-Karp variant using BFS runs in polynomial time.

Applications span bipartite matching, edge connectivity, transportation, and computer vision. Network flow theory exemplifies the power of combinatorial optimization, connecting graph structure to algorithmic solutions.