dwave_networkx.algorithms.matching.matching_bqm

matching_bqm(G)

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 G.

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:

G (NetworkX graph) – The graph on which to find a matching.

Returns:

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

Return type:

dimod.BinaryQuadraticModel