Graphs can be used to model transportation networks, which are networks whose edges carry “traffic” and whose nodes pass the traffic between the edges. These graphs have the following:
• capacities - for each edge, indicate how much it can carry • source nodes - generate traffic • sink/destination nodes - can "absorb" arriving traffic • traffic - transmitted across edges
We will refer to traffic as flow, and say a flow network is a directed graph G = (V, E) that has all above characteristics. Specifically, each edge e has a capacity, denoted ce, s is the source node, and t is the sink node. All other nodes are internal nodes. The Maximum-Flow Problem asks to find an algorithm that takes a flow network and returns a flow of maximum possible value. We need to define something called a residual graph in order to do this. A residual graph helps us systematically search for forward and backward operations on the edges. Here is the definition of a residual graph:
"Given a flow network G, and a flow f on G, we define the residual
graph Gf of G with respect to f as follows:
1) The node set of Gf is the same as that of G
2) For each edge e = (u, v) on G on which f(e) < ce,
there are ce - f(e) "leftover" units of capacity on
which we could try pushing flow forward. So we include
the edge e = (u, v) in Gf, with a capacity of ce - f(e).
We will call edges included this way forward edges.
3) For each edge e = (u, v) on G on which f(e) > 0,
there are f(e) units of flow that we can "undo" if we
want to, by pushing flow backward. So we include
the edge e' = (u, v) in Gf, with a capacity of f(e)...
We will call edges included this way forward edges."
The augment algorithm yields a new flow f' in G:
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 = (u,v)
decrease f(e) in G by b
return(f)
The Ford-Fulkerson Algorithm finds the max flow:
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)
update f to be f'
update the residual graph Gf to be Gf'
return f
The running time of this algorithm is O(mC) where C is the number of iterations and m is the edges. This section was pretty clear and the algorithms seem straightforward. 8.
An s-t cut is a partition (A,B) of the vertex set V such that s in A and t in B. c(A, B) denotes the capacity of a cut and is the sum of all the edges out of A. There are several facts to show that cuts provide natural upper bounds on the value of flows:
1) Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) = fout(A) - fin(A) 2) Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) ≤ c(A,B)
The following property proves the maximality of the Ford-Fulkerson Algorithm: If f is an s-t flow such that there is no s-t path in the residual graph Gf, then there is ab 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. We can compute an s-t cut of minimum capacity in O(m) time if we are given a flow f of max value.
This section seemed to just extend my knowledge of the last section so I would rate it a 7.
We will now finally see how to solve the Bipartite Matching Problem, where we want to find a matching in G of largest possible size. A matching M in G is a subset of the edges M in E such that each node appears in at most one edge in M. To do this we have a graph G and construct a flow network G', then direct all edges in G from X to Y. Add a node s and edge (s,x) from s to each node in X. Add a node t and edge (y,t) from each node in Y to t. Give each edge in G' capacity 1. Then compute maximum s-t flow in G'. This can be used to solve our matching.
We know that the size of the max matching in G = the value of the max flow in G' and the edges in such a matching in G are the edges that carry flow from X to Y in G'. We can use the Ford-Fulkerson Algorithm to find a maximum matching in a bipartite graph in O(mn) running time. This section was more confusing because they didn't really explain how to apply the FF Algorithm, so a 6.
There are many applications of the Maximum-Flow Problem. The two big ones are Circulations with Demands and Circulations with Demands and Lower Bounds. Both can be reduced to the Maximum-Flow Problem. These applications have more than one source node and more than one sink node. There are algorithms that can help generalize these problems to be able to use the algorithms we already wrote.
I think this section was clear and concise. It was less important to take notes and more beneficial to just read and absorb the ways that different problems can use the same algorithm. So the section is like a 9.5.