• 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, …

• Questions and Insights:

• Readability: