Summary of Chapter 7

1 A bipartite graph has two sets of nodes2 Arcs may connect nodes from different sets but never connect nodes in the same set.3 An alternating path starts at an unmatched node on one side of a bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately 'not in' and 'in' the initial matching.4 When you have drawn a bipartite graph, you can find an improved matching using the maximum matching algorithm.5 The maximum matching algorithm is as follows. Start with any initial matching. Search for an alternating path. If an alternating path can be found, use it to create an improved matching by changing the status of the arcs (in -> out, out -> in). If an alternating path cannot be found, stop. List the new matching, which consists of the result applying the alternating path together with any unchanged elements of the previous matching. If the matching is now complete, stop. Otherwise look for another alternating path. 6 If there is more than one pair of unmatched nodes you will need to find more than one alternating path.7 Each time you apply the maximum matching algorithm you increase the number of matched pairs by one.

New Page