MathsGee is Zero-Rated (You do not need data to access) on: Telkom |Dimension Data | Rain | MWEB

0 like 0 dislike
28 views
What is a cover in graph theory?
| 28 views

0 like 0 dislike
A cover of a graph G is a set C of vertices such taht every edge of G has at least one end in C.

Lemma:
If M is a matching of G and C is a cover of G, then $|M| \leq |C|$.

Lemma:
If M is a matching and C is a cover and $|M| = |C|$, then M is a maximum matching and C is a minimum cover.
by Diamond (75,918 points)

0 like 0 dislike