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 algorithm, we can determine that it runs in O(mC) time where m is the number of edges in the graph and C is the sum of the capacities of the flow out of an edge.

This section discusses an analysis of the Ford-Fulkerson Algorithm. This analysis is performed in terms of flows and cuts. We can begin this analysis by dividing the nodes of the graph into two sets, A and B. The division places an upper bound on the maximum possible flow, since all flow crosses from A to B at some location. Cuts gives us a natural upper bound on the values of flows. We can actually measure the flow value by keeping track of the amount of flow sent across a cut. We can probe this through manipulation of sums.

We can see that the value of every flow is upper-bounded by the capacity of every cut. The Ford-Fulkerson Algorithm ends when the flow has no s-t patch in the residual graph, which proves its maximality. With a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time.

Overall this section was a little bit difficult to read. It reminded me of what we had done in class, but I still feel as if I need another review of this topic. Out of 10, I would score this section a 5 for readability.