Cut (graph theory)

[1] Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition.

In a flow network, an s–t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source's side to the sink's side.

The max-flow min-cut theorem proves that the maximum network flow and the sum of the cut-edge weights of any minimum cut that separates the source and the sink are equal.

[4] The max-cut problem is also APX-hard, meaning that there is no polynomial-time approximation scheme for it unless P = NP.

This objective function favors solutions that are both sparse (few edges crossing the cut) and balanced (close to a bisection).

It forms a vector space over the two-element finite field of arithmetic modulo two, with the symmetric difference of two cut sets as the vector addition operation, and is the orthogonal complement of the cycle space.