1 A bipartite graph has two sets of nodes

2 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.

	Created by jakubburger about 11 years ago

Decision (Chapter 7: Matchings) Note on Summary of Chapter 7, created by jakubburger on 12/04/2013.

Summary of Chapter 7