Английская Википедия:Edge cover
Шаблон:Short description In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time.
Шаблон:Covering-Packing Problem Pairs
Definition
Formally, an edge cover of a graph Шаблон:Mvar is a set of edges Шаблон:Mvar such that each vertex in Шаблон:Mvar is incident with at least one edge in Шаблон:Mvar. The set Шаблон:Mvar is said to cover the vertices of Шаблон:Mvar. The following figure shows examples of edge coverings in two graphs (the set Шаблон:Mvar is marked with red).
A minimum edge covering is an edge covering of smallest possible size. The edge covering number Шаблон:Math is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set Шаблон:Mvar is marked with red).
Note that the figure on the right is not only an edge cover but also a matching. In particular, it is a perfect matching: a matching Шаблон:Mvar in which every vertex is incident with exactly one edge in Шаблон:Mvar. A perfect matching (if it exists) is always a minimum edge covering.
Examples
- The set of all edges is an edge cover, assuming that there are no degree-0 vertices.
- The complete bipartite graph Шаблон:Mvar has edge covering number Шаблон:Math.
Algorithms
A smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all vertices are covered.[1][2] In the following figure, a maximum matching is marked with red; the extra edges that were added to cover unmatched nodes are marked with blue. (The figure on the right shows a graph in which a maximum matching is a perfect matching; hence it already covers all vertices and no extra edges were needed.)
On the other hand, the related problem of finding a smallest vertex cover is an NP-hard problem.[1]
Looking at the image it already becomes obvious why, for a given minimum edge cover <math>C</math> and maximum matching <math>M</math>, letting <math>c</math> and <math>m</math> be the number of edges in <math>C</math> and <math>M</math> respectively, we have:[3] <math>|V| = c + m</math>. Indeed, <math>C</math> contains a maximum matching, so the edges of <math>C</math> can be decomposed between the <math>m</math> edges of a maximum matching, covering <math>2m</math> vertices, and the <math>c-m</math> other edges that each cover one other vertex. Thus, as <math>C</math> covers all of the <math>|V|</math> vertices, we have <math>|V| = 2m + (c-m)</math> giving the desired equality.
See also
- Vertex cover
- Set cover – the edge cover problem is a special case of the set cover problem: the elements of the universe are vertices, and each subset covers exactly two elements.
Notes
References
- ↑ 1,0 1,1 Шаблон:Harvtxt, p. 79, uses edge cover and vertex cover as one example of a pair of similar problems, one of which can be solved in polynomial time while the other one is NP-hard. See also p. 190.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Cite web
