John - Hungarian Algorithms

Question 1

A vertex is matched/saturated if

Answer 1

it is an endpoint on one of the edges in the matching. Otherwise, the vertex is unmatched.

Question 2

A maximal matching

Answer 2

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).

Question 3

A maximum matching

Answer 3

is a matching that contains the largest possible number of edges. There may be many maximum matchings.

Question 4

A perfect matching

Answer 4

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