Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 36 Β· Planarity and Flows

Minimum Cuts and Flow Applications

Learn s-t cuts, the max-flow min-cut theorem, how to extract a minimum cut from the residual graph, and apply flows to matching and edge-disjoint paths with Python.

A flow network asks how much you can push through. Its mirror-image question is: what is the cheapest set of connections you could cut to separate the source from the sink completely? Remarkably, these two questions have the same answer. This duality, the max-flow min-cut theorem, is one of the great theorems of combinatorial optimization, and it explains why flow algorithms can solve so many problems that do not look like flows at all.

Cuts

An s-t cut splits the vertices into two sets S and T with s ∈ S and t ∈ T. Its capacity is the total capacity of the edges that go from S to T. (Edges going back from T to S do not count.) Any flow from s to t must cross the cut, so every flow value is at most every cut capacity:

flow value ≀ capacity of any cut.

Max-flow min-cut theorem. The maximum value of an s-t flow equals the minimum capacity of an s-t cut.

The proof comes straight from the algorithm of the previous lesson. When Ford-Fulkerson stops, no augmenting path exists in the residual graph. Let S be the set of vertices reachable from s in the residual graph and T the rest. Every edge from S to T must be saturated (otherwise its head would be reachable), and every edge from T to S carries zero flow. So the flow equals the capacity of this cut, and since no flow can exceed any cut, both are optimal.

flowchart LR
    s((s)) -->|"10"| a((a))
    s -->|"10"| b((b))
    a -->|"4"| c((c))
    a -->|"8"| d((d))
    b -->|"9"| d
    c -->|"10"| t((t))
    d -->|"10"| t

The example network used below. Edge labels are capacities; the next example finds its minimum cut.

Extracting a minimum cut

To find a minimum cut, run any max-flow algorithm, then do a search from s in the residual graph. The reachable set is S; the saturated edges leaving it are the "bottleneck" edges to upgrade if you want more throughput.

Python Find a minimum s-t cut from the residual graph

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.

The capacity of the cut printed at the end equals the flow value, which is the theorem in action.

Application 1: bipartite matching as a flow

Add a source s connected to every left vertex and a sink t connected from every right vertex, all with capacity 1, and give every original edge capacity 1 (directed left to right). An integer flow of value k corresponds to a matching of size k: each left vertex receives at most one unit, so it is used at most once, and the same holds for right vertices. This is precisely why Kuhn's augmenting paths from the matching lesson are flow augmentations, and why KΓΆnig's theorem is the min-cut statement for this network.

Python Maximum bipartite matching through a flow network

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.

Application 2: edge-disjoint paths and Menger's theorem

How many routes from s to t share no edge? Give every edge capacity 1 and compute the maximum flow: a flow of value k decomposes into k edge-disjoint paths. Menger's theorem states that the maximum number of edge-disjoint s-t paths equals the minimum number of edges whose removal disconnects t from s, a min-cut statement with unit capacities. The vertex version (internally vertex-disjoint paths) uses the vertex-splitting trick. Menger's theorem underlies the notion of k-connectivity: a graph is k-edge-connected exactly when every pair of vertices has k edge-disjoint paths between them, and so network reliability is a max-flow question.

Python Edge-disjoint paths and network reliability

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.

Other problems that reduce to min cut

  • Image segmentation: pixels are vertices; edges between neighbors are weighted by similarity; terminals s ("foreground") and t ("background") connect to pixels by how strongly each pixel prefers a label. A minimum cut is the best labeling.
  • Project selection (closure): choose projects with profits and prerequisite costs to maximize net profit; the optimum is the total profit minus a min cut.
  • Baseball elimination, airline crew scheduling, data-center load balancing.
  • Global minimum cut (no fixed s and t): solved by the Stoer-Wagner algorithm or by Karger's random contraction, which succeeds with probability at least 2/(n(nβˆ’1)) per run, so repeated runs find it with high probability.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What does the max-flow min-cut theorem state?

    Flow value is bounded by every cut and equality is reached at the optimum, so the two optimization problems have the same value.
  2. 2. After the last augmentation, how do you find the source side S of a minimum cut?

    Vertices reachable from s through positive residual capacity form S. All edges leaving S are saturated, so their total capacity equals the flow value.
  3. 3. How do you model bipartite matching as a flow problem?

    Unit capacities ensure each vertex is used at most once, and an integral flow of value k gives a matching of size k.
  4. 4. Menger's theorem relates the maximum number of edge-disjoint s-t paths to

    With unit capacities the maximum flow counts edge-disjoint paths and the minimum cut counts the fewest edges that must be removed.

Summary

  • An s-t cut splits the vertices; its capacity counts edges from the source side to the sink side.
  • Max-flow min-cut: the largest flow equals the smallest cut capacity; the residual-reachable set gives a minimum cut.
  • Matching is flow on a unit-capacity network; KΓΆnig's theorem is its min-cut statement.
  • Menger's theorem: edge-disjoint paths equal the minimum edge cut, which measures connectivity and reliability.
  • Many labeling and selection problems (segmentation, project selection) reduce to minimum cuts.

Next: Graph Matrices and the Spectrum