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