Maximum Flow in Networks

A flow network is a directed graph where each edge has a capacity (the maximum amount of flow it can carry). The goal is to find the maximum amount of flow that can be sent from a source vertex (s) to a sink vertex (t) while respecting all capacity constraints.

Flow Network Terminology

• Source (s) — the vertex where flow originates; has no incoming edges carrying flow.
• Sink (t) — the vertex where flow terminates; has no outgoing edges carrying flow.
• Capacity — a non-negative integer or real on each edge, denoting the maximum flow through that edge.
• Flow — a non-negative value on each edge satisfying 0 ≤ flow ≤ capacity.
• Conservation — for every vertex except s and t, flow in = flow out.
• Value of flow — the total flow leaving the source (which equals total flow arriving at the sink).

Ford-Fulkerson Method

The Ford-Fulkerson method is a greedy iterative algorithm. It repeatedly finds an augmenting path from s to t in the residual graph and pushes flow along that path. The process repeats until no more augmenting paths exist.

Residual Graph

The residual graph G_f shows the remaining capacity on each edge after some flow has been sent. For each original edge (u, v) with capacity c and flow f, the residual graph contains:

• A forward edge (u, v) with residual capacity c - f.
• A backward edge (v, u) with residual capacity f (allowing flow to be undone).

def ford_fulkerson(graph, source, sink):
    n = len(graph)
    # Residual graph: res[u][v] = remaining capacity
    res = [row[:] for row in graph]
    max_flow = 0

    def bfs(s, t, parent):
        visited = [False] * n
        queue = [s]
        visited[s] = True
        while queue:
            u = queue.pop(0)
            for v in range(n):
                if not visited[v] and res[u][v] > 0:
                    parent[v] = u
                    visited[v] = True
                    queue.append(v)
                    if v == t:
                        return True
        return False

    parent = [-1] * n
    while bfs(source, sink, parent):
        # Find the bottleneck capacity along the augmenting path
        bottleneck = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            bottleneck = min(bottleneck, res[u][v])
            v = u
        # Update residual capacities
        v = sink
        while v != source:
            u = parent[v]
            res[u][v] -= bottleneck
            res[v][u] += bottleneck
            v = u
        max_flow += bottleneck
    return max_flow

Edmonds-Karp Algorithm

Edmonds-Karp is a specific implementation of Ford-Fulkerson that uses BFS to find the shortest augmenting path (in terms of number of edges). This guarantees O(V * E²) time complexity, whereas a naive DFS-based Ford-Fulkerson can be exponential.

Max-Flow Min-Cut Theorem

One of the most important results in network flow theory:

The value of the maximum flow from s to t equals the capacity of the minimum s-t cut.

An s-t cut is a partition of vertices into two sets S and T (with s in S and t in T such that the sum of capacities of edges from S to T is minimized). The minimum cut is the bottleneck of the network.

Applications of Maximum Flow

• Bipartite Matching — add a source connected to left vertices, connect right vertices to a sink, set all capacities to 1. The max flow equals the size of the maximum matching.
• Transportation — shipping goods from factories (sources) to warehouses (sinks) with road capacity limits.
• Image Segmentation — treat pixels as vertices; the min cut separates foreground from background.
• Circulation with Demands — supply and demand nodes connected by capacity-limited edges.

# Bipartite matching via max flow
def max_bipartite_matching(left, right, edges):
    # Build flow network:
    # source = 0, left = 1..|left|, right = |left|+1..|left|+|right|, sink = last
    n = 2 + len(left) + len(right)
    graph = [[0]*n for _ in range(n)]
    source, sink = 0, n - 1
    for i in range(len(left)):
        graph[source][1 + i] = 1
    for i in range(len(right)):
        graph[1 + len(left) + i][sink] = 1
    for u, v in edges:
        graph[1 + u][1 + len(left) + v] = 1
    return ford_fulkerson(graph, source, sink)

Complexity Summary

graph = [
    [0, 16, 13, 0, 0],
    [0, 0, 10, 12, 0],
    [0, 4, 0, 0, 14],
    [0, 0, 9, 0, 20],
    [0, 0, 0, 0, 0]
]