In this exercise we consider matching problems where some man-woman pairs are not allowed.a) Extend the definition of a stable matching to cover the situation where there are the same number of men and women, but certain pairs of men and women are forbidden. Avoid all cases where a man and a woman would prefer each other to their current situation, including those involving unmatched people.________________b) Adapt the deferred acceptance algorithm to find stable matchings when there are the same number of men and women, but certain man-woman pairs are forbidden. Be sure to consider people who are unmatched at the end of the algorithm. (Assume that an unmatched person prefers a match with a member of the opposite gender who is not a forbidden partner to remaining unmatched.)________________c Prove that all matchings produced by the algorithm from (b) arc stable, according to the definition in part (a).

SOLUTIONStep 1In this problem, we are asked to consider the matching problems where some man woman pair is forbidden and then do the following .