Matchings

Question 1

Alternating path

Answer 1

Starts at an unmatched node on one side of a bipartite graph and finished at an unmatched node. It uses arcs that are alternately ‘not in’ and ‘in’ in the initial matching.

Question 2

explain why a complete matching may not be possible

Answer 2

Both X and Y can only be matched to n

e.g.Both C and J can only be matched to 5