TOPICS
Search

Cut


Given a weighted, undirected graph G=(V,E) and a graphical partition of V into two sets A and B, the cut of G with respect to A and B is defined as

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

where W(i,j) denotes the weight for the edge connecting vertices i and j. The weight of the cut is the sum of weights of edges crossing the cut.


See also

Articulation Vertex, Branch Cut, Edge Cut, Maxcut, Mincut, 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." http://www.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html.

Referenced on Wolfram|Alpha

Cut

Cite this as:

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

Subject classifications