Section 7.5 a First Application: the Bipartite Matching Problem

We can compute a maximum matching in a set of nodes G by adding an s and a t node, then computing the maximum s-t flow in our new graph G'. This means that not only can we find the size of this matching but actually use the flow to find the matching itself.

I don't understand how we are determining a “maximum matching”? What does a maximum matching mean? what is the metric that we are trying to maximize? Statements 7.34, 7.35, and 7.36 seem important enough to warrant being included in my notes, so here they are:

M' contains k edges

Each node in X is the tail of at most one edge in M'

Each node in Y is the head of at most one edge in M'

However, I do not understand what the application of these statements means.

We can compute this mystical “maximum matching” using the FF algorithm in O(mn) time. I don't quite understand how, other than we appear to be using the FF algorithm which has that running time.

The chapter goes on the discuss some other nonsensical thing about what augenting paths mean in the network G'. Again, I am lost quickly. The authors appear to be drawing dashed lines and bold lines at will with no real meaning behind them. This is all I am able to discern. These distinctions have something to do with a type of path called an alternating path.

The section goes on to discuss what should happen in the case that there is not perfect matching in the bipartite graph. It would be good to produce an output that convinces the user that there is no perfect matching. The maximum flow of G' must be at least n to allow for a perfect matching.