min_weight_matching

min_weight_matching(G, maxcardinality=False, weight='weight')

Computing a minimum-weight maximal matching of G.

Use reciprocal edge weights with the maximum-weight algorithm.

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.

This method replaces the weights with their reciprocal and then runs max_weight_matching(). Read the documentation of max_weight_matching for more information.

Parameters

GNetworkX graph

Undirected graph

maxcardinality: bool, optional (default=False)

If maxcardinality is True, compute the maximum-cardinality matching with minimum 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 minimal weight matching of the graph.