One often uses graphs to model transport systems or networks. Network models of this type have several ingredients: capacities on the edges, indicating how much traffic they carry, source nodes that generate traffic and sink nodes which absorb the traffic, and the traffic itself.

Flow Networks. We refer to the traffic as flow, generated at the source nodes, transmitted across edges, and absorbed at sink nodes. All edges in a flow network are associated with an edge cost that is a nonnegative number that we denote Ce. Also, no edges enter the source and no edges leave the sink.

Defining Flow. An s-t flow is a function f that maps each edge e to a nonegative real number, f(e) represents the amount of flow carried by edge e. f(e) must be less than or equal to an edge e's capacity (also greater than 0) and the amount of flow coming into a node must equal the amount of flow leaving it, except for the source and sink nodes.

The maximum flow problem. Given a flow network, a natural goal is to arrange traffic so as to make as efficient use as possible of the available capacity. Basically, find a flow of maximum possible value.

Designing the Algorithm. There is no algorithm known for the Maximum-Flow Prolem taht could really be viewed as naturally belonging to the dynamic programming paradigm. We shall thus use the residual grtaph to demonstrate how pushing forward and backward flow helps us attain a path s-t with maximum flow. Residual Graph. After pushing 20 units of flow along the paths s,u,v,t:

• the node set of the residual graph is the same as that of the original graph
• For each edge with f(e)< Ce, there are Ce-f(e) leftover units of capacity.
• For each edge of G, there are f(e) units of flow that we can undo by pushing flow backward.

If f(e) is less than the capacity and greater than 0, it results in both a forward edge and a backward edgebeing included in Gf. Augmenting Paths in a Residual Graph. Let P be a simple path form s to t in Gf. We define the bottleneck(P,f) to be the minimum residual capacity of any edge on P with respect to the flow.The algorithm for augment on an s-t path is on page 342. The result of augment(f,P) is obtained by increasing and decreasing flow values on edges of P. The algorithm to compute an s-t flow in G is on page 344. And we will call this the Ford-Fulkerson Algorithm after the two reserachers who developed it in 1956. Does the While loop in the Algorithm terminate?

Analyzing the Algorithm. We knoe that the flow and residual capacities in Gf are integers. And if thios is true(which is proven on page 344), then the Algorithm terminates in at most C iterations of the While loop, where C is the sum of all flow leaving s. The Ford-fulkerson Algorithm can be implemented to run in O(mC) time.

This section seems a little bit more complicated in the book than explained in class, thus I give it a 7.5/10 scale.