Consider the problem of matching n persons with n objects on a one-to-one basis (cf. Exercises 1.21 and 3.9). For each person i there is a given set of objects A(i) that can be matched with i. A...

Consider the problem of matching n persons with n objects on a one-to-one basis (cf. Exercises 1.21 and 3.9). For each person i there is a given set of objects A(i) that can be matched with i. A matching is a subset of pairs (i, j) with j ∈ A(i), such that there is at most one pair for each person and each object. A perfect matching is one that consists of n pairs, i.e., one where every person is matched with a distinct object