======  7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm ======
The Problem Motivation:

A few concepts:
to model **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 several ingredients: **capacities** on the edges, indicating how
much they can carry; **source nodes** in the graph, which generate traffic; **sink
**(or destination) nodes in the graph, which can "absorb" traffic as it arrives;
and fina~y, the **traffic** itself, which is transmitted across the edges.


Flow Networks definition:  
a flow network is a directed graph G = (V, E) with the following features.
Associated with each edge e is a capacity, which is a nonnegative number
that we denote ce.

a Flow network is a directed graph G = (V, E) with the following features.
o Associated with each edge e is a capacity, which is a nonnegative number
  that we denote ce.
o There is a single source node s e V.
o There is a single sink node t ~ V

The Problem:

The Maximum-Flow Problem Given a flow network, the goal is to
arrange the traffic so as to make as efficient use as possible of the available
capacity. 
Thus the basic algorithmic problem we will consider is the following:
Given a flow network, find a flow of maximum possible value

Attempt: Greedy - local informatioon is not enough to solve for global optimum


We can define the Residual Graph, which provides a systematic way to search for forward-backward operations in order to find the maximum flow.
Given a flow network , and a flow  on , we define the residual graph  of  with respect to  as follows.
1. The node set of  is the same as that of G
2. Each edge  of  is with a capacity of c(e)-f(e).
3. Each edge  of  is with a capacity of f(e).flipped over.



====== 7.2 Maximum Flows and Minimum Cuts in a Network ======

goal is to show that the flow that is returned by the Ford-F~kerson
Algorithm has the maximum possible value of any flow in G.Prove optimality.

find the min cut:
Find an s-t cut of minimum capacity

flow value lemma/pf --- the idea of flow conservation

Corollary. Let f be any flow, and let (A, B) be
any cut. If v(f) = cap(A, B), then f is a max
flow and (A, B) is a min cut.


f is an s-t-flow such that there is no s-t path in the residual graph
then there is an s-t cut (A*,B*) in G for which v(f) = c(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.

useful lemma,
Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) =fin(B) -f°Ut(B).

Pf on P374.

If f is an s-t-flow such that there is no s-t path in the residual graph
then there is an s-t cut (A*,B*) in G for which v(f) = c(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. .....

Proof. The statement claims the existence of a cut satisfying a certain desirable
property; thus we must now identify such a cut. To this end, let A* denote the
set of all nodes v in G for which there is an s-v path in @. Let B* denote.~e
set of all other nodes: B* = V - A*.


Runtime analysis:
O(Cm)


Intereting/readable: 6/6



====== 7.3 Choosing Good Augmenting Paths ======

Big idea: Good choice of augmentation path can improve bounds significantly.

augmentation increases the value of the maximum
flow by the bottleneck capacity of the selected path; so if we choose paths
with large bottleneck capacity, we will be making a lot of progress.

maintain a so-called scaling parameter to avoid looking at exactly the largest bottleneck 
P379

The algorithms on  p380


analysis of the running time:

The number of iterations o[ the outer While loop is at most 1 +[log2 C].
we are using paths that augment the flow by a great amount, and so there should be relatively few augmentations.

Let f be the [low at the end of the A-scaling phase. There is an s-t
cut (A, B) in G for which c(A, B) < v(f) + mA, where m is the number of edges
in the graph G. Consequently, the maximum [low in the network has value at
most v(f) + m A.

Proof on P380.

Interesting/readable: 5/6