Definition
Maximum Cut Optimisation Problem
Instance: A finite simple undirected graph
. Feasible solutions: Bipartitions
with and ; either part may be empty. Objective: Maximise the number of crossing edges:
Maximum Cut Optimisation Problem
Instance: A finite simple undirected graph
. Feasible solutions: Bipartitions
with and ; either part may be empty. Objective: Maximise the number of crossing edges: