This chapter is about a set of problems that grow from the Bipartite Matching Problem we talked about earlier. We can use this algorithm/idea to develop a general set of problems about traffic flow on networks.

Graphs can be used to model transportation networks, which have a capacity on the edges, a source(start) node, a sink(end) node, and the traffic across the edges. A flow network is a directed graph with a capacity for each edge, c(e), and a single source and sink node. No edges go into the source and no edges go out of the sink. The flow is a function f(e) that represents the flow on each edge. The flow into a node must equal the flow out of a node and f(e) must not exceed c(e). The value of the flow v(f) is the amount of flow generated at the source. Our goal is to arrange the traffic to efficiently use the capacity. We develop the proof along with the fact that the max-flow value equals the min-capacity at any cut.

We cannot use dynamic programming because we can run out of paths before reaching the max-flow. Therefore, we need to be able to push flow forward and backwards. We do this with the residual graph, where the nodes are the same, the forward edges represent unused capacity, and backward edges represent the flow on the edge. The algorithms on pages 343-344 find the maximum flow. The idea is to look for an augmenting path the adjust the flow and capacity on each edge in the path based on the bottleneck. We know the flow value strictly increases with each augmentation, and the running time is O(mC),