dimod.generators.matching

matching(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph) → BinaryQuadraticModel

Find a binary quadratic model for the graph’s matchings.

A matching is a subset of edges in which no node occurs more than once. This function returns a binary quadratic model (BQM) with ground states corresponding to the possible matchings of graph.

Finding valid matchings can be done in polynomial time, so finding matching with BQMs is generally inefficient. This BQM may be useful when combined with other constraints and objectives.

Parameters:

graph – The graph on which to find a 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.

Returns:

A binary quadratic model with ground states corresponding to a matching. The variables of the BQM are the edges of graph as frozensets. The BQM’s ground state energy is 0 by construction. The energy of the first excited state is 1.