networkx.algorithms.matching.maximal_matching¶
-
maximal_matching
(G)[source]¶ Find a maximal matching in the graph.
A matching is a subset of edges in which no node occurs more than once. A maximal matching cannot add more edges and still be a matching.
- Parameters
G (NetworkX graph) – Undirected graph
- Returns
matching – A maximal matching of the graph.
- Return type
Notes
The algorithm greedily selects a maximal matching M of the graph G (i.e. no superset of M exists). It runs in \(O(|E|)\) time.