Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.bipartite.covering.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

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.

Return type

set

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.