dwave_networkx.algorithms.matching.maximal_matching_bqm

maximal_matching_bqm(G, lagrange=None)

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

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 G can be added without violating the matching rule. This function returns a binary quadratic model (BQM) with ground states corresponding to the possible maximal matchings of G.

Finding maximal matchings can be done in polynomial time, so finding maximal 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 maximal matching.

• lagrange (float (optional)) – The Lagrange multiplier for the matching constraint. Should be positive and greater than max_degree - 2. Defaults to 1.25 * (max_degree - 2).

Returns:

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

Return type:

dimod.BinaryQuadraticModel