Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 49 Β· Network Optimization

Maximum Flow and Minimum Cut

Find the largest amount that can flow through a capacitated network with augmenting paths, residual graphs and reverse edges, and prove it with a minimum cut.

Water pipes, roads, data links and supply chains all share one feature: each connection can carry only so much. How much can you send from a source to a destination before the network is full? That is the maximum flow problem. It sounds like a question about capacity, but it turns out to be one of the most versatile models in operations research, because matching, scheduling and even image-processing problems can be rewritten as flows.

In this lesson you learn the augmenting-path method, meet the idea of reverse edges (undoing earlier decisions), and discover a beautiful theorem: the maximum flow always equals the capacity of the narrowest bottleneck, the minimum cut.

A capacitated network with flows shown as flow over capacity on each arc, saturated arcs in pink, and the minimum cut drawn as a dashed line
Maximum flow is 11. The two saturated arcs a to c (6 of 6) and d to t (5 of 5) form the minimum cut: 6 + 5 = 11.

What you will learn

  • The maximum flow problem and the rules a flow must obey.
  • How augmenting paths and residual capacities work, including reverse edges.
  • The max-flow min-cut theorem.
  • How to find the flow and the cut in Python, and by linear programming.

Key terms

Capacity: the largest flow an arc can carry.

Flow conservation: at every node except source and sink, flow in equals flow out.

Residual capacity: how much more could still be pushed along an arc, plus the amount that could be undone along its reverse.

Augmenting path: a path from source to sink in the residual network with positive residual capacity everywhere.

Cut: a split of the nodes into a source side and a sink side; its capacity is the total capacity of arcs going from the source side to the sink side.

The problem

A flow network has a source s, a sink t, and arcs with capacities. A flow assigns each arc an amount that satisfies two rules:

  1. Capacity: 0 ≀ flow ≀ capacity on every arc.
  2. Conservation: at every node other than s and t, the total flow arriving equals the total flow leaving.

The value of a flow is the amount leaving s (which equals the amount arriving at t). We want a flow of maximum value.

Our example (example numbers) has these arc capacities: s→a 10, s→b 6, a→b 3, a→c 6, b→d 7, c→t 8, c→d 4, d→t 5. Notice that more can leave s (16) than can arrive at t (13); something in the middle must limit the flow.

Augmenting paths

The method of L. R. Ford Jr. and D. R. Fulkerson (1956) is delightfully simple:

  1. Start with zero flow.
  2. Find a path from s to t along which every arc still has spare capacity. Push as much as the bottleneck (the smallest spare capacity on the path) allows. This is an augmenting path.
  3. Repeat until no augmenting path exists.

On the example network: the path s β†’ a β†’ c β†’ t has spare capacities 10, 6 and 8, so we push 6 (the arc a β†’ c is now full). The path s β†’ b β†’ d β†’ t has capacities 6, 7 and 5, so we push 5 (the arc d β†’ t is full). The total flow is 11. Now every path from s to t must either cross a β†’ c or d β†’ t, both full, so we stop. Flow 11 is the maximum.

Reverse edges: the ability to undo

Greedy path choices can block better solutions. The method fixes this with the residual network. When you push flow along u β†’ v, you also create a reverse arc v β†’ u with capacity equal to the flow pushed. Pushing along the reverse arc cancels some of the earlier flow. A later augmenting path may use it to reroute flow.

Consider the small network with arcs s→a, s→b, a→b, a→t, b→t, all of capacity 1. If the first path chosen is s → a → b → t, it fills s→a, a→b and b→t. Now the only remaining route is s → b → a → t, which uses the reverse arc b → a (undoing the flow on a → b). The final flow is 2, with a → t and b → t both used. Without reverse arcs the method would stop at 1, which is wrong.

Edmonds and Karp showed in 1972 that choosing the augmenting path with the fewest arcs (found by breadth-first search) guarantees a polynomial number of augmentations: at most about nΒ·m/2 for n nodes and m arcs.

Python Augmenting paths with residual arcs

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the second run, the second augmentation is s β†’ b β†’ a β†’ t: it travels backwards along the arc a β†’ b.

The max-flow min-cut theorem

A cut separates the nodes into a set S containing the source and a set T containing the sink. Its capacity is the sum of the capacities of arcs going from S to T (arcs going back do not count). Any flow must cross the cut, so the flow value can never exceed the capacity of any cut. In our network, take S = {s, a, b, d} and T = {c, t}. The arcs from S to T are a β†’ c (6) and d β†’ t (5), so this cut has capacity 11. The arc c β†’ d goes from T to S and is not counted.

The theorem (Ford and Fulkerson, 1956) says more:

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

When the augmenting-path method stops, the set of nodes reachable from s in the residual network is exactly the source side of a minimum cut. Here it is {s, a, b, d}. This gives a certificate: a flow of 11 and a cut of 11 prove each other optimal. The cut also names the bottleneck: to increase the maximum flow, you must widen a β†’ c or d β†’ t.

Flow by library and by linear programming

scipy has maximum_flow (integer capacities required). The flow matrix shows the flow on each arc, with antisymmetric entries for reverse arcs. The LP formulation maximizes the flow leaving s subject to capacity limits and conservation; because of total unimodularity the LP optimum is integer.

Python scipy maximum_flow and the LP formulation

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Try it yourself: change the capacities

Change a capacity and watch the maximum flow and the minimum cut respond. When you widen an arc that is not in the cut, nothing happens. When you widen a cut arc, the flow rises until another bottleneck appears.

Capacity sliders: max flow and min cut

Applications

  • Bipartite matching. Add a source connected to every worker and a sink connected to every job, with capacity 1 on all arcs: the maximum flow is the largest number of workers who can be given different jobs they are qualified for.
  • Transport and communication. Maximum data per second between two servers or maximum vehicles per hour through a road network.
  • Project and scheduling problems. Selection problems with dependencies reduce to a minimum cut.
  • Image segmentation. Pixels are nodes; a minimum cut separates foreground from background.

Common misconceptions

"The maximum flow is the sum of the capacities leaving the source." Here 16 could leave s, but only 11 can reach t. Downstream bottlenecks limit the flow.

"Once flow is placed on an arc, it stays there." Augmenting paths may push flow along reverse arcs, which cancels and reroutes earlier flow.

"The minimum cut is the arc with the smallest capacity." It is the set of arcs separating source from sink with the smallest total capacity.

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. What is a bottleneck of an augmenting path?

    You can push only as much as the tightest arc of the path allows.
  2. 2. What is the purpose of reverse arcs in the residual network?

    Pushing flow along a reverse arc undoes part of an earlier flow decision.
  3. 3. In the example network, what is the maximum flow from s to t?

    The arcs a β†’ c (6) and d β†’ t (5) form a cut of capacity 11, and a flow of 11 exists.
  4. 4. The max-flow min-cut theorem states that...

    The two optimal values are equal: each proves the other optimal.
  5. 5. How can a bipartite matching problem be solved with a max flow?

    With unit capacities, the maximum flow equals the largest matching.

Summary

  • A flow obeys capacities and conservation; the maximum flow problem maximizes the value leaving the source.
  • Augmenting paths push flow along paths with spare capacity; reverse arcs allow undoing earlier choices; Edmonds–Karp uses shortest augmenting paths.
  • The max-flow min-cut theorem: the maximum flow value equals the capacity of a minimum cut, giving both an answer and a certificate (here 11).
  • LP and scipy.sparse.csgraph.maximum_flow give the same result.
  • Matching and many other problems reduce to flows.

Next: Transportation and Assignment Problems