TOPICS
Search

Cut

A cut of a weighted undirected graph G=(V,E) is specified by a set partition of V into two sets A and B. Its weight is

cut(A,B)=sum_(i in A,j in B)W(i,j),

where W(i,j) is the weight of the edge joining vertices i and j.

See also

Articulation Vertex, Branch Cut, Directed Cut, Edge Cut, Maxcut, Min-UnCut, Mincut, Sparsest Cut, Uniform Sparsest Cut, Vertex Cut

Explore with Wolfram|Alpha

References

Demmel, J. "CS 267: Lectures 20 and 21, Mar 21, 1996 and Apr 2, 1999. Graph Partitioning, Part 1." https://people.eecs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html.

Referenced on Wolfram|Alpha

Cut

Cite this as:

Weisstein, Eric W. "Cut." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Cut.html

Subject classifications