In the context of graph theory, a **minimum cut** refers to a specific type of partitioning of a graph that separates the vertices into two distinct subsets while minimizing the total weight of the edges that cross between these two subsets. ### Key Concepts: - **Graph**: A collection of vertices (nodes) connected by edges (links). - **Cut**: A cut in a graph is a way of dividing the graph's vertices into two disjoint subsets.
Articles by others on the same topic
A minimum cut is a cut of a flow network of least cut capacity for the prescribed source and sink . The max-flow min-cut theorem equates that least cut capacity with the greatest flow value.[ref]
Flows (author-hosted chapter preview). Graph Theory by Reinhard Diestel; Diestel, Flows, §6.2, Theorem 6.2.2, printed p. 159
To certify a particular minimum cut, exhibit a feasible flow whose flow value equals its cut capacity. Every feasible flow is bounded above by every cut capacity, so this single equality proves both optimalities.[ref]
FordFulkerson.java. Algorithms, 4th edition by Robert Sedgewick and others; Sedgewick and Wayne, FordFulkerson.java, check method, lines 180–209: feasibility, source/sink membership and equality of values
In the running example, the four possible source sides , , and have cut capacities , respectively. The feasible flow of flow value therefore certifies three different minimum cuts. A minimum cut need not be unique; the optimum cut capacity is the same for all of them. Merely saturating many edges does not give this certificate: flow conservation and the particular cut of a flow network must also be checked.