Maxcut
Let G=(V,E) be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut C of G is any nontrivial subset of V, 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 G of maximum weight. Determining the maxcut of a graph is an NP-hard problem.
See also
Cut, Mincut, Weighted GraphExplore with Wolfram|Alpha
WolframAlpha
More things to try:
Cite this as:
Weisstein, Eric W. "Maxcut." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Maxcut.html