For a weighted graph G, the maximum cut problem seeks to partition the
vertices into sets 
and 
so as to maximize the weight (or number) of edges with one vertex in each
set.
When the graph specifies an electronic circuit, the maximum cut
in the graph defines the largest amount of data communication
that can take place
in the circuit simultaneously.
As discussed in catalog Section 
,
maximum cut is an NP-complete version of graph partitioning.
How can we formulate maximum cut for simulated annealing?
The solution space consists of all 
possible vertex partitions;
we save a factor of two over all vertex subsets because
we can assume that vertex 
is fixed to be on the left side
of the partition.
The subset of vertices accompanying it can be represented using a bit vector.
The cost of a solution will be the sum of the weights cut in the current
configuration.
A natural transition mechanism is to select one vertex at random and move
it across the partition by simply flipping the corresponding
bit in the bit vector.
The change in the cost function will be the weight of its old neighbors minus
the weight of its new neighbors, so it can be computed in time proportional
to the degree of the vertex.
This kind of simple, natural modeling is the right type of heuristic to seek in practice.