dwave_networkx.algorithms.matching.is_maximal_matching

is_maximal_matching(G, matching)[source]

Determines whether the given set of edges is a maximal matching.

A matching is a subset of edges in which no node occurs more than once. The cardinality of a matching is the number of matched edges. A maximal matching is one where one cannot add any more edges without violating the matching rule.

Parameters:
  • G (NetworkX graph) – The graph on which to check the maximal matching.
  • edges (iterable) – A iterable of edges.
Returns:

is_matching – True if the given edges are a maximal matching.
Return type:

bool

Example

This example checks two sets of edges, both derived from a single Chimera unit cell, for a matching. The first set (a matching) is a subset of the second, which was found using the min_maximal_matching() function.

>>> import dwave_networkx as dnx
>>> G = dnx.chimera_graph(1, 1, 4)
>>> dnx.is_matching({(0, 4), (2, 7)})
True
>>> dnx.is_maximal_matching(G,{(0, 4), (2, 7)})
False
>>> dnx.is_maximal_matching(G,{(0, 4), (1, 5), (2, 7), (3, 6)})
True