It is often required to match collections of things with other collections to ensure as far as possible that everything is matched to everything else. It may not be possible for everything to be matched, because some objects in one set may only be matched to certain objects in the other set.
There exists an algorithm, called the matching algorithm, to achieve the maximum possible number of matchings. To demonstrate the algorithm, we start with a bipartitie graph displaying things on the left hand side to be matched with things on the right hand side.
A, B, C, D and E are people, to be matched with tasks 1, 2, 3, 4 and 5. Not all the people can do all the tasks.
Person A can only do tasks 1, 2 and 3.
Person B can only do tasks 1.
Person C can only do tasks 2 and 3.
Person D can only do tasks 1, 2 and 3 and 4
Person E can do tasks 1, 2, 3, 4 and 5.
The possible tasks each person can do are illustrated below.
To apply the algorithm we need an 'initial matching', which could be any combination of the pairings on the diagram above, as long as each thing on the left is matched to at most one thing on the right and vices versa. Notice that an initial matching does not mean that everything needs to be matched. I will choose the initial matching that matches A to 1.
Now I must find an alternating path which improves on this initial matching. Each alternating path starts at an object on the left which is not matched to anything, and goes to an object on the right which is either not matched, or is matched, and is removed from the matching by the alternating path. Alternately, we make a matching, remove a matching, make a matching... until we arrive on the right at something which is unmatched to anything. Each alternating path makes one more matching than it removes, resulting in an overall increase in matchings.
For the first alternating path, I will start at B on the left, go to 1 on the right, back to A on the left and back to 2 on the right.
This alternating path is written B-1=A-2. The matching A-1 is removed at the matchings B-1 and A-2 are inserted, as shown below.
We can match C in an alternating path of length 1 to 3 without affecting anything else, matched or unmatched, obtaining the set of matchings shown below.
We can obtain a maximal matching now by matching D to 4 and E to 5, both alternating paths of length 1, to obtain the 'maximal matching' below.
