pub fn minimum_edge_cover(graph: &Graph) -> IgraphResult<Vec<u32>>Expand description
Compute a minimum edge cover.
Returns a set of edge IDs such that every vertex is incident to at least one edge in the set, and the number of edges is minimized.
The algorithm first computes a greedy maximal matching, then covers each unmatched vertex by adding any one of its incident edges. By König’s theorem, the result has size n - |matching|, which is optimal.
§Errors
Returns an error if the graph has isolated vertices (vertices with degree 0), since no edge cover exists in that case.
§Examples
use rust_igraph::{Graph, minimum_edge_cover, is_edge_cover};
// Path 0-1-2: minimum edge cover is {0-1, 1-2} (2 edges)
let mut g = Graph::with_vertices(3);
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
let cover = minimum_edge_cover(&g).unwrap();
assert!(is_edge_cover(&g, &cover));
assert_eq!(cover.len(), 2);
// K3: minimum edge cover is 2 edges
let mut g = Graph::with_vertices(3);
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
g.add_edge(2, 0).unwrap();
let cover = minimum_edge_cover(&g).unwrap();
assert!(is_edge_cover(&g, &cover));
assert_eq!(cover.len(), 2);