A little overview of bipartite matching and some of the previous applications that were provided in the textbook, and some definitions. A matching is “a set of edges with the property that each node appears in at most one edge.” Matchings are good for representing assignment. They set up a goal for finding the largest matching in a bipartite graph.

This section is a pretty comprehensive overview of the maximum flow problem and its solution, the Ford-Fulkerson algorithm. First are the features of a “flow network”: each edge has a capacity, there's a source, and there's a sink. And then there's the properties of the “flow” proper, a “flow” maps the edges of a flow network to a non-negative number. The value of a flow is the amount of flow generated at the source. The number can't be greater than the edge's capacity in the flow network, and also sum of the flow numbers coming into each node has to equal the sum of the flow numbers going out, except for the sink and source. After a few false starts trying to design the algorithm, (dynamic programming? Nope. Greedy? Nope) they get around to outlining Ford-Fulkerson, with the residual graph and all the goodies we covered in lecture. They prove that after every augmentation the graph remains–and use that and some other things to prove the algorithm terminates. It's pretty exciting.

Well if I thought the last section was jam-packed of analysis about maximum flows and the Ford-Fulkerson algoritm, boy was I in for a surprise because this section takes it to the extreme. First it formalizes the notion of s-t cuts, and proves useful properties about them, like the difference between the values of the edges out of a cut plus the sum of the values of the edges into the cut equals the value of the cut, which is used to prove that the capacity of the cut forms an upper bound on the value of the flow. Then en route to proving the optimality of the Ford-Fulkerson algorithm they prove that the max flow equals the min cut. Interesting thing they point out–they prove that with integers the FF algorithm terminates, but it's possible, they say, to have “pathological” choices if you widen it to reals, because it could augment by just a smaller and smaller amont each time.

This section is simply an application of network flow problems and the FF algorithm to this bipartite matching problem. The concept, like we covered in lecture, you just take the bipartite graph, plug half of it into the source, plug the other half of it into the sink, and then set all the edges to have a capacity of 1, and be directed towards the sink, and then run FF. The maximum flow you get will use the edges that you want for the matching of largest possible size. But in order to get there you have to prove it works. Most of it seems obvious, like that if you do this you're never going to get two edges going out of one of the edges on the source side of your graph when you run the Ford-Fulkerson. The running time of this is O(mn) because you can run Ford-Fulkerson in O(mC) using one of the methods, and for this graph, since the edges only have capacities of 1, C = n, so you get O(mn). Then it proves something interesting about “certificates” indicating whether a particular bipartite graph has a perfect matching or not. It turns out that, if there's no perfect matching, you'll always be able to find a set of nodes on one side of the bipartite graph which is larger than the set of nodes on the other side which have edges to nodes in the first set–and such always implies the abscence of a perfect matching. Kind of neat.