# max_weight_matching#

max_weight_matching(G, maxcardinality=False, weight='weight')[source]#

Compute a maximum-weighted matching of G.

A matching is a subset of edges in which no node occurs more than once. The weight of a matching is the sum of the weights of its edges. A maximal matching cannot add more edges and still be a matching. The cardinality of a matching is the number of matched edges.

Parameters:
GNetworkX graph

Undirected graph

maxcardinality: bool, optional (default=False)

If maxcardinality is True, compute the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings.

weight: string, optional (default=â€™weightâ€™)

Edge data key corresponding to the edge weight. If key not found, uses 1 as weight.

Returns:
matchingset

A maximal matching of the graph.

Notes

If G has edges with weight attributes the edge data are used as weight values else the weights are assumed to be 1.

This function takes time O(number_of_nodes ** 3).

If all edge weights are integers, the algorithm uses only integer computations. If floating point weights are used, the algorithm could return a slightly suboptimal matching due to numeric precision errors.

This method is based on the â€śblossomâ€ť method for finding augmenting paths and the â€śprimal-dualâ€ť method for finding a matching of maximum weight, both methods invented by Jack Edmonds [1].

Bipartite graphs can also be matched using the functions present in `networkx.algorithms.bipartite.matching`.

References

[1]

â€śEfficient Algorithms for Finding Maximum Matching in Graphsâ€ť, Zvi Galil, ACM Computing Surveys, 1986.

Examples

```>>> G = nx.Graph()
>>> edges = [(1, 2, 6), (1, 3, 2), (2, 3, 1), (2, 4, 7), (3, 5, 9), (4, 5, 3)]