dwave_networkx.algorithms.matching.min_maximal_matching_bqm#

min_maximal_matching_bqm(G, maximal_lagrange=2, matching_lagrange=None)[source]#

Find a binary quadratic model for the graph’s minimum 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. A minimum maximal matching is a maximal matching that contains the smallest possible number of edges. This function returns a binary quadratic model (BQM) with ground states corresponding to the possible maximal matchings of G.

Parameters:
  • G (NetworkX graph) – The graph on which to find a minimum maximal matching.

  • maximal_lagrange (float (optional, default=2)) – The Lagrange multiplier for the maximal constraint. Should be greater than 1.

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

Returns:

bqm – A binary quadratic model with ground states corresponding to a minimum maximal matching. The variables of the BQM are the edges of G as frozensets.

Return type:

dimod.BinaryQuadraticModel