Cutfunktion

Cutfunktion, in graph theory often called the cut function, assigns to each subset of vertices S of a graph G = (V, E) a nonnegative value that measures the total weight of edges crossing the cut between S and its complement V \ S. Formally, for a weighted graph with edge weights w: E → R≥0, the cut value is f(S) = sum of w(e) over all edges e with exactly one endpoint in S. In an unweighted graph this reduces to counting the crossing edges. The domain of the cutfunktion is the power set of V, and the function is symmetric: f(S) = f(V \ S). It is zero for S = ∅ and for S = V.

Properties and variants: The cutfunktion is a classic example of a symmetric submodular set function, satisfying f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B) for all A, B ⊆ V. It is not generally monotone with respect to inclusion. In directed graphs, the cut value usually sums the weights of arcs from S to V \ S, and directed cuts lead to the s-t cut paradigm when a specific source and sink are fixed.

Computation and applications: The minimum cut problem seeks a subset S that minimizes f(S). In undirected graphs this can be solved efficiently via max-flow/min-cut algorithms; the global minimum cut can be found by algorithms such as Stoer–Wagner. Applications include graph partitioning, clustering, network design and reliability, image segmentation, and VLSI layout. The cutfunktion also underlies constructs like the Gomory–Hu tree, which encodes all-pairs minimum cuts in a graph.

Variants and extensions include weighted and directed cuts, multiway cuts, and interpretations within submodular optimization where cut-based objectives are optimized over subsets of vertices.