the weight of this cut equals the maximum amount of flow that can be sent from the source to the sink in the given network.

In a weighted, undirected network, it is possible to calculate the cut that separates a particular pair of vertices from each other and has minimum possible total cost. A system of cuts that solves this problem for every possible vertex pair can be collected into a structure known as the Gomory-Hu tree of the graph.

k-cut

A generalization of the minimum cut

1.Previous
3.Next