Matching and Covering скачать в хорошем качестве

Matching and Covering

A vertex is matched (or saturated) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched (or unsaturated). A maximal matching is a matching M of a graph G that is not a subset of any other matching. A matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M. The following figure shows examples of maximal matchings (red) in three graphs. A maximum matching (also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number 𝜈(𝐺) of a graph G is the size of a maximum matching. Every maximum matching is maximal, but not every maximal matching is a maximum matching. A covering graph is a subgraph which contains either all the vertices or all the edges corresponding to some other graph. A subgraph which contains all the vertices is called a line/edge covering. A subgraph which contains all the edges is called a vertex covering.