Skip to main content
`Ctrl`+`K`

# min_edge_cover

min_edge_cover(G, matching_algorithm=None)

  Returns a set of edges which constitutes the minimum edge cover of the graph.

  The smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all nodes are covered.

  Parameters:
    G NetworkX graph

      An undirected bipartite graph.

    matching_algorithm function

      A function that returns a maximum cardinality matching in a given bipartite graph. The function must take one input, the graph `G`, and return a dictionary mapping each node to its mate. If not specified, `hopcroft_karp_matching()` will be used. Other possibilities include `eppstein_matching()`,

  Returns:
    set

      A set of the edges in a minimum edge cover of the graph, given as pairs of nodes. It contains both the edges `(u, v)` and `(v, u)` for given nodes `u` and `v` among the edges of minimum edge cover.

  Notes

  An edge cover of a graph is a set of edges such that every node of the graph is incident to at least one edge of the set. A minimum edge cover is an edge covering of smallest cardinality.

  Due to its implementation, the worst-case running time of this algorithm is bounded by the worst-case running time of the function `matching_algorithm`.