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
• Wordy but interesting, 7/10

• 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
• Reminded me of real analysis, straightforward, 7/10

• We wish to match edges to a subset such that each node appears in max one edge of the edge subset, such that the matching has the largest possible size.
• We solve this as follows:
  • Look at G, constructing a flow network by directing all edges in G from X to Y, then adding a node s and an (s,x) edge from s to each node in X. We add a node t and an edge (y,t) from every edge in Y to t. We give every edge in the flow network a capacity of 1. Then we compute the maximum s-t flow.
• The size of the maximum matching in G equals the max flow in the flow network G' and edges carrying flow from X to Y in G' are in the matching in G.
  • We can do this in O(mn) time.
  • What if the graph has no perfect matching?
    • If this isn't the case, for all A in side X of G, we have more nodes in A's adjacent nodes than in the A component.
    • Either we can find a perfect matching or an appropriate subset _G in O(mn) time.
  • 4/10

• What if we have a set of sources and a set of sinks?
• Consider the case where sources have fixed supply and sinks have fixed demand, like rainway lines shipping from factories to retail outlets.
• Now the circulation fulfills
  • for each edge e, 0⇐f(e)⇐c_e
  • for each vertex v, the in minus out flows equal the demand of v.
• We can also do this with circulations that have lower bounds for demand.
• Boring and wordy, 2/10