Can there be several minimum cuts?

Yes. Different partitions can have the same minimum capacity, as in the worked graph.

Does the minimum cut always contain the smallest-capacity edge?

No. The objective concerns the total capacity of a separating boundary, which can contain several edges.

Can capacities represent costs rather than bandwidth?

Yes, in an appropriate reduction. The interpretation of the resulting cut depends on how those costs were encoded.

AI Glossary / Graphs and symbolic AI / Advanced

Flow-based Minimum Cuts

Definition

Flow-based minimum cuts are graph partitions found using a maximum-flow calculation. For a specified source s and destination t, an s-t cut separates s from t, and its capacity is the sum of capacities crossing from the source side to the destination side. A minimum cut minimizes this capacity.

What it means

The max-flow min-cut theorem links two views of the same capacity-limited network: the greatest feasible flow equals the capacity of a minimum separating cut. One view constructs the largest transfer; the other identifies a boundary that limits it.

The cut is a partition of vertices, with crossing edges determined by that partition. It is not necessarily a single weak link, the cut containing the fewest edges, or the cheapest repair plan. Those interpretations depend on what capacities mean. This entry concerns a cut between chosen terminals, rather than an unrestricted global minimum cut over all possible partitions.

How it works

Construct a graph with nonnegative edge capacities and choose source and sink vertices. A feasible flow respects edge capacities and conserves flow at intermediate vertices. A maximum-flow algorithm improves this flow using residual capacity, which records both unused forward capacity and the ability to revise earlier allocations.

After obtaining a maximum flow, identify the vertices reachable from the source along positive-capacity residual edges. These form one side of a minimum cut; the remaining vertices form the other side. For a directed graph, sum capacities of original edges leaving the source side, not edges pointing back into it.

A feasible flow provides a lower bound on the maximum value, and any separating cut provides an upper bound. When their values match, optimality is established. Several different partitions may attain the same minimum, so one returned cut need not be the only bottleneck boundary consistent with the model.

Three practical examples

1. A network-capacity study identifies a boundary limiting transfer between two sites. Engineers can inspect the crossing links, while separately examining whether upgrading them would encounter another bottleneck.

2. An image-processing model constructs a graph whose cut cost encodes particular labeling penalties. The cut has a segmentation interpretation because of that construction, not because arbitrary minimum cuts automatically identify meaningful objects.

3. A graph-connectivity analysis assigns unit capacities to links. The minimum cut then measures how many modeled edges must be removed to separate the selected endpoints, subject to the graph's direction and other assumptions.

Think of it this way

Think of water moving through a network of pipes. Any boundary separating the inlet from the outlet must accommodate all net transfer, so its total forward capacity limits what can pass. The analogy explains the theorem's capacity constraint. Real fluid systems may involve pressure, losses and coupled physical effects absent from the abstract flow model, so a graph calculation is not automatically a hydraulic design.

Worked example

Consider a directed graph with capacities s-a: 4, s-b: 2, a-t: 2, a-b: 1 and b-t: 3. Send 3 units from s to a and 2 from s to b. At a, send 2 directly to t and 1 to b. At b, the incoming total is 2 + 1 = 3, which flows to t. All capacities are respected, giving a feasible total flow of 5.

Now partition the vertices into source side {s,a} and destination side {b,t}. The crossing edges are s-b with capacity 2, a-b with capacity 1 and a-t with capacity 2. Their sum is 5. No flow can exceed this cut, so the constructed flow and cut together prove the maximum flow and minimum cut value are both 5.

There is another minimum cut: source side {s,a,b} and destination side {t}, with capacities 2 + 3 = 5. By contrast, cutting just after s has capacity 4 + 2 = 6. The example shows that a minimum cut need not occur at the source, and that several optimal partitions can coexist.

Illustrative case study

Fictional case study: Cypress Transfer uses a graph model to investigate a throughput limit. The first report recommends enlarging every link in the returned minimum cut. A reviewer notices that another cut has the same capacity, so addressing only the reported boundary may leave a different limitation unchanged.

The team evaluates proposed upgrades in the modified graph and checks whether the capacities represent actual constraints. It separates mathematical capacity from operational scheduling and shared infrastructure limits. The case illustrates cautious interpretation, not a claim that a particular upgrade achieved higher throughput.

Common misconceptions and mistakes

Minimum capacity is not the same as minimum edge count unless capacities are uniformly one. A cut also differs from a path: it is a separating boundary, not a route from source to sink.

The residual graph is not merely the original graph with saturated edges deleted; reverse residual edges can matter because earlier flow can be redirected. Do not infer that a single saturated edge determines the bottleneck. Finally, an s-t minimum cut answers a terminal-specific question. A global cut, balanced partition or multiway separation problem may need a different formulation.

Business use

Define capacities in units appropriate to the question, and verify that the network model captures the resources being limited. Confirm source and destination choices, graph direction and treatment of missing capacity values before interpreting results.

Present both the cut value and its partition or crossing edges. Where the result informs an investment or redesign, recompute after proposed changes and examine alternative bottlenecks. Distinguish an optimal result for the encoded graph from evidence that the graph captures the real system. The guarantee depends on those modeling assumptions.

Check your understanding

Why does a feasible flow of 5 plus a cut of capacity 5 prove optimality in the example?

Answer: The feasible flow shows that at least 5 can be transferred, while the cut shows that no more than 5 can cross. Matching bounds establish the optimum.

Related terms

Maximum Flow
residual capacity
s-t cut
graph partition
edge connectivity
capacity constraint
flow conservation
bottleneck
global minimum cut

Learn next

Draw the worked flow and verify conservation at each intermediate vertex. Then construct its residual graph and find a reachable-set cut. Change one capacity and check whether another cut becomes the active limitation.

Reachable set

Sources

Primary reference: NetworkX, minimum-cut documentation and its max-flow min-cut basis: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.minimum_cut.html . The capacity calculation and fictional case are original teaching material. No library execution or benchmark is claimed.

Previous: Flow-based generative model Next: Flow-based programming