min_edge_cover(G, matching_algorithm=None)
A smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all nodes are covered. This function follows that process. A maximum matching algorithm can be specified for the first step of the algorithm. The resulting set may return a set with one 2-tuple for each edge, (the usual case) or with both 2-tuples :None:None:`(u, v)` and :None:None:`(v, u)` for each edge. The latter is only done when a bipartite matching algorithm is specified as :None:None:`matching_algorithm`.
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. The 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
.
Minimum edge cover for G can also be found using the :None:None:`min_edge_covering` function in networkx.algorithms.bipartite.covering
which is simply this function with a default matching algorithm of ~networkx.algorithms.bipartite.matching.hopcraft_karp_matching
An undirected graph.
A function that returns a maximum cardinality matching for G. The function must take one input, the graph G, and return either a set of edges (with only one direction for the pair of nodes) or a dictionary mapping each node to its mate. If not specified, ~networkx.algorithms.matching.max_weight_matching
is used. Common bipartite matching functions include ~networkx.algorithms.bipartite.matching.hopcroft_karp_matching
or ~networkx.algorithms.bipartite.matching.eppstein_matching
.
A set of the edges in a minimum edge cover in the form of tuples. It contains only one of the equivalent 2-tuples :None:None:`(u, v)` and :None:None:`(v, u)` for each edge. If a bipartite method is used to compute the matching, the returned set contains both the 2-tuples :None:None:`(u, v)` and :None:None:`(v, u)` for each edge of a minimum edge cover.
Returns the min cardinality edge cover of the graph as a set of edges.
>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])See :
... sorted(nx.min_edge_cover(G)) [(2, 1), (3, 0)]
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.covering.min_edge_cover
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them