Edge cover
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is an endpoint of 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.
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is an endpoint of 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. Looking at the image it already becomes obvious why, for a given minimum edge cover C and maximum matching M , letting c and m be the number of edges in C and M respectively, we have: |V| = c + m . Indeed, C contains a maximum matching, so the edges of C can be decomposed between the m edges of a maximum matching, covering 2m vertices, and the c-m other edges that each cover one other vertex. Thus, as C covers all of the |V| vertices, we have |V| = 2m + (c-m) giving the desired equality.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1295741878 under CC BY-SA 4.0; modifications have been made.