• Summary:

This chapter goes back to the bipartite matching problem from the beginning of the term. One problem is to determine the size of the largest matching in a bipartite graph, which needs new techniques to solve. They develop a new class of problems - network flow problems - that include bipartite matching as a special case. They develop a polynomial-time algorithm for the Maximum-Flow Problem and show how it works for bipartite matching and other problems. The first section models transportation networks with graphs. Edges have capacities, and there are source and sink nodes in the graph. Traffic is referred to as flow. A flow network is a directed graph where each edge has a nonnegative capacity, and there's a single source s and a single sink node t (other than s and t, the nodes are internal nodes). No edge enters s, no edge leaves t. All capacities are integers. There's at least one edge incident to each node. Flow has to be between zero and the capacity for every edge. Except for s and t, the amount of flow entering a node has to equal the amount leaving the node. So a goal is to figure out how to get maximum flow from s to t on a graph. They go through an example of why greedy doesn't work. Then they get into the Ford-Fulkerson algorithm. You keep track of the graph and the flow on every edge and also of a residual graph. In the residual graph, the “remaining capacity” (i.e. capacity minus flow) is represented by a forward edge, the flow is represented by a backward edge. Augmenting paths in the residual graph are paths from s to t (i.e. paths that you can add more flow to). The bottleneck of the augmenting path is the minimum residual capacity of any edge in the augmenting path. So in order to augment a path, you just push as much flow as possible (determined by the bottleneck) onto every edge in that path (and update the residual graph). They go through and show that this gives a flow and doesn't violate any of the rules (like conservation). Then they give the Ford-Fulkerson algorithm: all flows 0 in the graph to begin with, while there's an augmenting path in the residual graph, augments the path and updates the residual graph. They prove that it will terminate because every iteration increases the overall flow values (and for integer costs, that has to be at least one each time), and they put an upper bound on the number of iterations, by using C, which is the capacity out of s. If the overall flow is increased by one each iteration, then the absolute highest it can go is C. If these capacities are all integers, then Ford-Fulkerson completes in O(mC) time because each iteration takes O(m) work to find an augmenting path.

• Questions and Insights:

None. The non-integer, non-rational-number idea is pretty interesting; I think it would be neat to see how that runs (I mean, obviously I could make one and go through it … maybe I will sometime).

• Readability:

Great :)

• Summary:

• Questions and Insights:

None.

• Readability:

Great :)

 
  * **Summary:**

• Questions and Insights:

• Readability: