Definition
Formally, an edge cover of a graph G is a set of edges C such that each vertex in G is incident with at least one edge in C. The set C is said to cover the vertices of G. The following figure shows examples of edge coverings in two graphs.
A minimum edge covering is an edge covering of smallest possible size. The edge covering number is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings.
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 M in which each vertex is incident with exactly one edge in M. A perfect matching is always a minimum edge covering.
Read more about this topic: Edge Cover
Famous quotes containing the word definition:
“Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
—Nadine Gordimer (b. 1923)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)