dimod.generators.min_maximal_matching#

min_maximal_matching(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, maximal_lagrange: float = 2, matching_lagrange: float | None = None) → BinaryQuadraticModel[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 graph 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 graph.

Parameters:

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

  • maximal_lagrange – The Lagrange multiplier for the maximal constraint. Should be greater than 1. Defaults to 2.

  • matching_lagrange – 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:

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