John - Hungarian Algorithms Flashcards
A vertex is matched/saturated if
it is an endpoint on one of the edges in the matching. Otherwise, the vertex is unmatched.
A maximal matching
a matching of M to G with the property that if any edges not in M are added to M, it is no longer a matching, that is, M is maximal if it is not a subset of any other matching in graph G. I.e it is maximal if every edge in G has a non-empty intersection with at least one edge in M. Figure below shows maximal matchings (in red).
A maximum matching
is a matching that contains the largest possible number of edges. There may be many maximum matchings.
A perfect matching
is a matching which matches all vertices of the graph. That is, every vertex of the graph is incident to exactly one edge of the matching. Every perfect matching is maximum and hence maximal