Chapter 7 - Network Flow

The section begins by defining the problem. We will be examining directed graphs with weights along the edges. These weights denote capacities of traffic that can pass through each node. The section dives into exactly what a flow network is. A flow network contains edges with a non-negative number as its capacity, a single source node s, and a single sink node t.

The section then defines what the flow function is, that is, the amount of traffic carried through a node. It maps each edge to a real number. For each edge, the flow of that edge must be less than or equal to that edge's capacity. Additionally, for each node v other than s and t, we have the summation of flow into v equal to the summation of flow out of v. And the value of a flow (for a graph) f, is defined to be the amount of flow generated at the source.

With all of this in mind, we are able to define the problem. Our goal is to find the maximum flow for a given network flow. The section begins by walking through different possible solutions to this problem. It concludes to push forward on edges with leftover capacity and push backwards on edges that are already carrying flow. We then define the residual graph of G. In the residual graph, the node set is the same. For every amount the flow of an edge is less than that edge's capacity, we have that many leftover units of capacity. We also create backwards edges with a capacity of the edge in question.

In order to solve the problem, the section lays out an augmenting path algorithm. This algorithm takes a flow f and an s-t path as inputs. It then considers each edge in the path. If the edge is a forward edge, then we increase the flow of e in G by the bottleneck, and decrease the flow of e in G by the bottleneck if the edge is a backward edge.

We use this algorithm to generate our Max-Flow algorithm. The max flow initially sets all flows equal to zero. And while there is an s-t path in the residual graph, we let P be an s-t path in the residual graph, let f' = augment(f,P), update f to be f', and update the residual graph to be the residual graph with this new flow f'.

The section then walks through a variety of different proofs which back up the intuition behind the algorithm. At every stage of the algorithm, the flow values and the residual capacities are integers. Later in the section, we denote the value C as the summation of capacities of edges out of s. The section walks through the proof that the algorithm terminates in at most C iterations of this summation. And it concludes this part of the section by outlining the proof that the Ford-Fulkerson Algorithm can be implemented to run in O(mC) time.

I would rate the readability of this section at 7/10.

In this section, we continue to analyze the Ford Fulkerson algorithm.

The section begins by defining a cut, which is a division of the nodes such that s lies in one division, call it A, and B lies in the other division, call it B. The section walks through the proof that, for any s-t cut, the value of the flow if the flow out of A minus the flow into A. And from this, we can prove that if f is an s-t flow, and (A,B) is an s-t cut, then the value of f is less than or equal to the capacity of (A,B). This inequality is useful for us in proving the optimality of the Ford Fulkerson Algorithm.

The section then walks into the driving point of the section: That the Max-Flow Equals the Min-Cut. That is, if f is an s-t flow, and there is no path in the residual graph, then there is an s-t cut (A*,B*) in G for which the value of the flow equals the capacity of (A*,B*). Consequently, f has the maximum value of any flow in G, and (A*,B*) has the minimum capacity of any s-t cut in G. Within this proof, the section proves that this cut must exist, and from that conclusion, we are able to derive the conclusion that all edges out of A* are saturated with flow and all edges into A* are unused. Therefore, the summation of the capacities out of A* is equal to the flow of the graph.

This fact combined with the fact from earlier, that for any s-t cut, the flow out of A minus the flow into A equals the value of the flow of the graph, gives us the optimality of the Ford-Fulkerson Algorithm. And from here, the section walks through the proof that we can compute an s-t cut of minimum capacity in O(m), which helps further explain the overall runtime of the algorithm.

The section concludes by discussing some details of integer assumptions behind the algorithm. They note that for all practical applciations, we will be working with rational numbers or integers. However, if we were to work with real numbers using the Ford Fulkerson Algorithm, it may not ever terminate or may take an exorbitant number of iterations.

I would rate the readability of this section at 8/10.