dimod.generators.maximal_matching#

maximal_matching(graph: int | tuple[Collection[Hashable], Collection[tuple[Hashable, Hashable]]] | Collection[tuple[Hashable, Hashable]] | Graph, lagrange: float | None = None) → BinaryQuadraticModel[source]#

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 graph 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 ``graph`.

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:

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

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

Returns:

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