**__Chapter 7.5: A First Application: The Bipartite Matching Problem__**

A //bipartite// graph is an undirected graph whose node set can be partitioned as V = X U Y, with the property that every edge e in E has one end in X and the other end in Y.  A //matching// M in G is a subset of the edges M including E such that each node appears in at most one edge in M.  The Bipartite Matching Problem is that of finding a matching in G of largest possible size.

**Designing the Algorithm**

Beginning with the graph G, we construct a flow network G'.  First we direct all edges in G from X to Y, then we add nodes s and t and give each edge in G' a capacity of 1.  We now compute a maximum s-t flow in this network G'.  The value of this maximum is equal to the size of the maximum matching in G.  Bam.

Runtime:  O(mn) ---> same as Ford-Fulkerson Algorithm.
This section was pretty self explanatory.  9/10.