Let be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut of is any nontrivial subset of , and the weight of the cut is the sum of weights of edges crossing the cut. A maxcut is then defined as a cut of of maximum weight. Determining the maxcut of a graph is an NP-hard problem.

# Maxcut

## See also

Cut, Mincut, Weighted Graph## Explore with Wolfram|Alpha

## Cite this as:

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