**__Chapter 7.1: The Maximum-flow Problem and the Ford-Fulkerson Algorithm__**

We will be looking at //transportation networks// - networks whose edges carry some sort of traffic and whose nodes act as "switches" passing traffic between different edges.  Network models of this type have //capacities// on the edges, indicating how much they can carry; //source// nodes in the graph, which generate traffic; //sink// nodes which "absorb traffic" as it arrives; and the traffic, or //flow//, which is transmitted across the edges.

**Flow Networks**

A //flow network// is a directed graph with the following features
  * Associated with each edge e is a capacity.  Ce.
  * There is a single source node s
  * There is a single sink node t
  * Nodes other than s and t are called internal nodes.

The flow on an edge cannot exceed the capacity of the edge.  

**The Maximum-flow Problem**

Given a flow network, we will look to find the MAX flow possible.  The maximum-flow value equals the minimum capacity of the //minimum cut//.  This minimum cut follows the idea that we can divide the nodes of the graph into two sets, A and B, so that s is in A and t is in B.  Any flow that goes from s to t must cross from A to B, and thereby use up some of the edge capacity from A to B.

**Designing the Algorithm**

We can push flow forward on edges with leftover capacity, and backward on edges that are already carrying flow, to divert it into a different location.  This is better shown in the //residual graph// which provides a systematic waay to search for forward-backward operations. 

Let P be a single s-t path in the graph G --> P does not visit any node more than once.  bottleneck(P, f) is the minimum residual capacity of any edge on P, with respect to the flow f.  

  augment(f, P)
    Let b = bottleneck(P,f)
    For each edge (u,v) in P
      If e = (u,v) is a forward edge
        increase f(e) in G by b
      Else ((u,v) is a backward edge, and let e = (v,u))
        decrease f(e) in G by b
        
    return f

The result of this augment algorithm is a new flow f in G, obtained by increasing and decreasing the flow values on edges of P.

  Max-Flow
    Initially f(e) = 0 for all e in G
    While there is an s-t path in the residual graph Gf
      Let P be a simple s-t path in Gf
      f' = augment(f, P)
      f = f'
      Update the residual graph Gf to Gf'
      
    return f

This is called the //Ford-Fulkerson Algorithm//.  It can be implemented to run in O(mC) time, in which m is the number of edges in G, and C is the maximum capacity out of the source node s.

This chapter is very interesting, Ford and Fulkerson must have been some smart guys.  9/10.