Chapter 7

For our purposes, we define a flow network as a graph G with a source node s and a sink node t with each edge e having a non-negative capacity ce. There are also two important conditions: the capacity condition and the conservation condition. The capacity condition restricts a flow of an edge to be less than or equal to its capacity. The conservation condition assures that, with the exception of the source and sink nodes, the flow into a node v equals the flow out of v. Thus, our problem is to maximize the flow within a flow network. The algorithm that achieves this does so using a residual graph, a clone of the original graph G with augmented edges indicating flow. Thus, the overall algorithm, the Ford-Fulkerson algorithm, combines an two different functions. One for augmenting an edge, and another for computing overall flow:

  Augment(f, P)
  b=bottleneck(P, f)
  for each edge in P
      if e=(u,v) is a forward edge then
          increase f(e) in G by b
      else e is a backward edge and e=(v,u)
          decrease f(e) in G by b
   return(f)
   

The overall algorithm is O(m). The overall readability of the section was 6/10.

This section is entirely concerned with analysis of the Ford-Fulkerson algorithm. There are several important principles applied within the algorithm. For starters, we know that the flow returned by the FF algorithm is the maximum flow. We know this by a very complex proof that utilizes cuts, or partitions of the nodes within a graph. More specifically, we use two cuts, A and B where s is in A and t is in B. The various proofs are confusing, but the overall takeaway is that the algorithm is correct and can run in O(m) time. The readability of this section was 4/10.