dwave.graphs.algorithms.max_cut.maximum_cut#

maximum_cut(G, sampler, **sampler_args)[source]#

Returns an approximate maximum cut.

Defines an Ising problem with ground states corresponding to a maximum cut and uses the sampler to sample from it.

A maximum cut is a subset S of the vertices of G such that the number of edges between S and the complementary subset is as large as possible.

Parameters:

  • G (NetworkX graph) – The graph on which to find a maximum cut.

  • sampler (dimod.Sampler) – A dimod sampler.

  • sampler_args – Additional keyword parameters are passed to the sampler.

Returns:

S – A maximum cut of G.

Return type:

set

Example

This example uses a sampler from dimod to find a maximum cut for a graph of a Chimera unit cell created using the chimera_graph() function.

>>> import dimod
...
>>> sampler = dimod.SimulatedAnnealingSampler()
>>> G = dwave.graphs.chimera_graph(1, 1, 4)
>>> cut = dwave.graphs.maximum_cut(G, sampler)

Notes

Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.