finds an edge cover of the graph g with a minimum number of edges.
uses rules vw to specify the graph g.
Background & Context
- FindEdgeCover finds a single minimum edge cover of a graph and returns the result as an edge list. Here, an edge cover is a set of edges for which at least one edge endpoint is incident to every vertex in a graph. A minimum edge cover is an edge cover having the smallest possible number of edges. Minimum edge covers have applications in social networks, biology, and social sciences.
- The size of (i.e. the number of edges in) a minimum edge cover of a graph is known as its edge cover number and is denoted . An edge cover can be found in polynomial time.
- EdgeCoverQ can be used to test if a given edge set is a (not necessarily minimum) edge cover. Application of EdgeCoverQ to all possible edge subsets of a graph can therefore be used to enumerate all edge covers, and application to subsets of size equal to the edge cover number can be used to enumerate all minimum edge covers. FindVertexCover applies the same concept to vertices.
Examplesopen allclose all
Properties & Relations (5)
Test whether a set of edges is an edge cover using EdgeCoverQ:
An edge cover of a StarGraph includes all its edges:
Introduced in 2010
|Updated in 2014