min_edge_cover#
- min_edge_cover(G, matching_algorithm=None)[source]#
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:
- GNetworkX graph
An undirected bipartite graph.
- matching_algorithmfunction
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 includeeppstein_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 nodesu
andv
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
.