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:
- GNetworkX graph
Undirected graph
- Returns:
- matchingset
A maximal matching of the graph.
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.
Examples
>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]) >>> sorted(nx.maximal_matching(G)) [(1, 2), (3, 5)]