Chapter 7: Network Flow

This section discusses modeling networks involving capacities, source nodes, sink nodes, and the direction of transmission. This transmission is considered flow, from the source nodes through the edges to the sink nodes. A flow network must have a non-negative capacity at each edge, a source node (s), and a sink node (t). All other nodes are considered internal nodes. A flow must have two conditions. First, it can only carry up to and including as much capacity as it has. Second, the flow out of the node must equal the flow into the node. A goal here is to find the flow with the maximum value. We do so by analyzing various “cuts” of the graph. The minimum cut is where the maximum flow value equals the minimum capacity.

Finding a maximum flow using a greedy algorithm won't necessarily work. Instead, we want to find our flow by pushing forward on edges with leftover capacity and backward on edges already carrying flow. This becomes a residual graph, a way to perform these operations. We can then augment paths in the residual graph to find the maximum capacity flow. This is done by identifying the bottleneck in each push of flow.

This methodology is known as the Ford-Fulkerson Algorithm. Through analyzing the