dwave.graphs.algorithms.matching.min_maximal_matching#

min_maximal_matching(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, sampler: Sampler, **sampler_args) → set[Hashable][source]#

Returns an approximate minimum maximal matching.

Defines a BQM with ground states corresponding to a minimum maximal matching and uses the sampler to sample from it.

A matching is a subset of edges in which no node occurs more than once. A maximal matching is one in which no edges from graph can be added without violating the matching rule. A minimum maximal matching is the smallest maximal matching for graph.

Parameters:

  • graph – The graph on which to find a minimum maximal matching. Either an integer n, interpreted as a complete graph of size n, a nodes/edges pair, a list of edges or a NetworkX graph.

  • sampler – A dimod sampler.

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

Returns:

A minimum maximal matching of the graph.

Example

This example uses a sampler from dimod to find a minimum maximal matching for a Chimera unit cell.

>>> import dimod
>>> sampler = dimod.ExactSolver()
>>> G = dwave.graphs.chimera_graph(1, 1, 4)
>>> matching = dwave.graphs.min_maximal_matching(G, sampler)