Minimum cut

In the special case when the graph is unweighted, Karger's algorithm provides an efficient randomized method for finding the cut.

In this case, the minimum cut equals the edge connectivity of the graph.

For a fixed value of k, this problem can be solved in polynomial time, though the algorithm is not practical for large k. [2] When two terminal nodes are given, they are typically referred to as the source and the sink.

As shown in the max-flow min-cut theorem, 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.

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.

[3] Graph partition problems are a family of combinatorial optimization problems in which a graph is to be partitioned into two or more parts with additional constraints such as balancing the sizes of the two sides of the cut.

Segmentation-based object categorization can be viewed as a specific case of normalized min-cut spectral clustering applied to image segmentation.

It can also be used as a generic clustering method, where the nodes are data samples assumed to be taken from a metric space and edge weights are their distances.

Due to max-flow min-cut theorem, 2 nodes' Minimum cut value is equal to their maxflow value.