Chapter 7

Network Flow notes

• Network flow problems include the bipartite matching problem, among others. Networks are graphs whose edges carry something and whose nodes facilitate passing traffic between edges.
• Network models can be seen as having capacity on edges, or how much they can carry.
• They have sources, or nodes that have no in-edges, and sinks, or nodes without out-edges.
• We define a flow network as
  • A digraph G=(V,E) with
  • Associated capacity for each edge, c_e
  • A single sink t
  • a single source s
• We say an s-t flow is a function f: (each edge in E) to a nonnegative real number so that f(e) = flow(e)
  • For each edge, 0⇐f(e)⇐c_e
  • For each node in V, excluding s and t, the flow into e is equal to the flow out of e.
• The value of a flow is the amount of flow generated at s.
• Given a flow network, what if we want to arrange our traffic to efficiently use our capacity?
• We do this as follows:
  • For each edge e, f(e) is 0 initially
  • While an s-t path remains in the residual graph
    • Consider a simple path s-t path, P
    • f' = augment(f,P)
    • f = f'
    • the residual graph is the residual graph of f'
• We use augment(f,P):
  • b = bottleneck(P,f)
  • for each (u,v)-edge e in P,
    • if e is a forward edge, increase f(e)+ = b
    • else e = v,u and f(e) - = b
  • return f
• If all capacities, this algorithm (the Ford-Fulkerson algorithm) terminates in C ( = sum(c_e) for all out edges of s) iterations of the while-loop
  • And it can be implemented in O(mC) time

• Consider an s-t cut: a partition (A,B) of V such that s∈A and t∈B. The capacity of an (A,B) cut, or c(A,B) is the sum of all c_e for each out edge e of A.
• For an s-t flow and an s-t cut (A,B), v(f) = the out flow of A - the in-flow of A
• For any s-t flow and any s-t cut (A,B), v(f) < = c(A,B).
• If f is an s-t flow so that the residual graph has no s-t path, there is an s-t cut (_A,_B) in G so that f(v) = c(_A,_B). Then, v(f) is the maximum of all flows in G and (_A,_B) has the minimum capacity of any s-t cut.
• the Ford-Fulkerson flow is a maximum flow

• We wish to