Skip to main content
`Ctrl`+`K`

# min_weight_matching

min_weight_matching(G, weight='weight')

  Computing a minimum-weight maximal matching of G.

  Use the maximum-weight algorithm with edge weights subtracted from the maximum weight of all edges.

  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 edge weights with 1 plus the maximum edge weight minus the original edge weight.

  new_weight = (max_weight + 1) - edge_weight

  then runs `max_weight_matching()` with the new weights. The max weight matching with these new weights corresponds to the min weight matching using the original weights. Adding 1 to the max edge weight keeps all edge weights positive and as integers if they started as integers.

  You might worry that adding 1 to each weight would make the algorithm favor matchings with more edges. But we use the parameter `maxcardinality=True` in `max_weight_matching` to ensure that the number of edges in the competing matchings are the same and thus the optimum does not change due to changes in the number of edges.

  Read the documentation of `max_weight_matching` for more information.

  Parameters:
    G NetworkX graph

      Undirected graph

    weight: string, optional (default=’weight’)

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

  Returns:
    matching set

      A minimal weight matching of the graph.

  See also

  `max_weight_matching`