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