In graph theory, a minimum cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge) that is minimal in some sense. Variations of the minimum cut include:
The cut with the minimum number of edges among all cuts in an undirected graph, determining the edge connectivity of the graph. Karger's algorithm provides an efficient randomized method for finding this cut.
The minimum cut problem in undirected weighted graphs can be solved by the Stoer–Wagner algorithm.
A generalization of the unweighted and undirected minimum cut, the minimum k-cut, in which the goal is to partition the graph into at least k connected components by removing as few edges as possible.
Graph partition, 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.
The cut in a flow network that separates the source and sink vertices and minimizes the total weight on the edges that are directed from the source side of the cut to the sink side of the cut. 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 cut in a weighted undirected network that separates a particular pair of vertices from each other and has minimum possible weight. 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.
