Graph Theory37 sections · 1633 units
Open in Course

Vocabulary - Cut

Partition separating source...

A cut is a partition of nodes into two sets SS and TT, where the source is in SS and the sink is in TT. The capacity of the cut is the sum of capacities of edges from SS to TT. The minimum cut has the smallest capacity.

By the max-flow min-cut theorem, its capacity equals the maximum flow. Finding the min-cut reveals the bottleneck edges in the network. These edges limit the maximum throughput.