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.
In this section, we revisit the Bipartite Matching Problem where we wish to find the largest bipartite matching in a graph G. The algorithm that achieves this builds off of the concept of flow networks. The algorithm takes an undirected bipartite graph and constructs a directed flow network from it. Interestingly enough, the size of the maximum matching in G is equal to the maximum flow in the corresponding flow network graph of G. The algorithm is more expensive, however, running in O(mn) time. Overall the readability of this section is 7/10.
The Maximum-Flow problem can be extended