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.

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

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