Network Flow

Flow Network

  • A flow network (or just network) N consists of
    • A weighted digraph G with nonnegative integer edge weights, where the weight of an edge e is called the capacity c(e) of e
    • Two distinguished vertices, s and t of G, called the source and sink, respectively, such that s has no incoming edges and t has no outgoing edges.
  • Example: Network_Flow

Flow

  • A flow f for a network N is is an assignment of an integer value f(e) to each edge e that satisfies the following properties:
    • Capacity Rule: For each edge e, 0 ≤ f (e) ≤ c(e)
    • Conservation Rule: For each vertex v ≠ s,t
      Network_Flow_Formula
      where E−(v) and E+(v) are the incoming and outgoing edges of v, resp.
  • The value of a flow f , denoted |f|, is the total flow from the source, which is the same as the total flow into the sink
  • Example:

Network_Flow_Example

Maximum Flow

  • A flow for a network N is said to be maximum if its value is the largest of all flows for N
  • The maximum flow problem consists of finding a maximum flow for a given network N
  • Applications: Hydraulic systems, Electrical circuits, Traffic movements

Max Flow

Cut

  • A cut of a network N with source s and sink t is a partition χ = (Vs,Vt) of the vertices of N such that s ∈ Vs and t ∈ Vt
    • Forward edge of cut χ: origin in Vs and destination in Vt
    • Backward edge of cut χ: origin in Vt and destination in Vs
  • Flow f(χ) across a cut χ: total flow of forward edges minus total flow of backward edges
  • Capacity c(χ) of a cut χ: total capacity of forward edges
  • Example:
    • c(χ) = 24
    • f(χ) = 8

Network_Flow_Cut

Flow and Cut

  • Lemma:
    • The flow f(χ) across any cut χ is equal to the flow value |f|
  • Lemma:
    • The flow f(χ) across a cut χ is less than or equal to the capacity c(χ) of the cut
  • Theorem:
    • The value of any flow is less than or equal to the capacity of any cut, i.e., for any flow f and any cut χ, we have |f| ≤ c(χ)

Network_Flow_And_Cut

Augmenting Path

  • Consider a flow f for a network N
  • Let e be an edge from u to v:
    • Residual capacity of e from u to v: Δ f(u, v) = c(e) − f (e)
    • Residual capacity of e from v to u: Δ f(v, u) = f (e)
  • Let π be a path from s to t 􀂄 The residual capacity Δf(π) of π is the smallest of the residual capacities of the edges of π in the direction from s to t
  • A path π from s to t is an augmenting path if Δf(π) > 0 Network_Flow_Augmenting_Path

Flow Augmentation

  • Lemma:
    • Let π be an augmenting path for flow f in network N. There exists a flow f′ for N of value | f′ | = |f | + Δf(π)
  • Proof:
    • We compute flow f′ by modifying the flow on the edges of π
      • Forward edge: f′ (e) = f(e) + Δf(π)
      • Backward edge: f′ (e) = f(e) − Δf(π) Network_Flow_Augmention

Ford-Fulkerson’s Algorithm

  • Initially, f(e) = 0 for each edge e
  • Repeatedly
    • Search for an augmenting path π
    • Augment by Δf(π) the flow along the edges of π
  • A specialization of DFS (or BFS) searches for an augmenting path
    • An edge e is traversed from u to v provided Δf(u, v) > 0
Algorithm FordFulkersonMaxFlow(N)
  for all e ∈ G.edges()
    setFlow(e, 0)
  while G has an augmenting path π
    { compute residual capacity Δ of π }
    Δ ← ∞
    for all edges e ∈π
      { compute residual capacity δ of e }
      if e is a forward edge of π
        δ ← getCapacity(e) − getFlow(e)
      else { e is a backward edge }
        δ ← getFlow(e)
      if δ <Δ
        Δ ←δ
    { augment flow along π }
    for all edges e ∈π
      if e is a forward edge of π
        setFlow(e, getFlow(e) + Δ)
      else { e is a backward edge }
        setFlow(e, getFlow(e) −Δ)

Max-Flow and Min-Cut

  • Termination of Ford-Fulkerson’s algorithm
    • There is no augmenting path from s to t with respect to the current flow f
  • Define
    • Vs set of vertices reachable from s by augmenting paths
    • Vt set of remaining vertices
  • Cut χ = (Vs,Vt) has capacity c(χ) = |f|
    • Forward edge: f(e) = c(e)
    • Backward edge: f(e) = 0
  • Thus, flow f has maximum value and cut χ has minimum capacity
  • Tehorem: The value of a maximum flow is equal to the capacity of a minimum cut

Network_Max_Flow_Min_Cut

Example

Network_Flow_Final_Example Network_Flow_Final_Example

Analysis

  • In the worst case, Ford-Fulkerson’s algorithm performs |f| flow augmentations, where f is a maximum flow
  • Example
    • The augmenting paths found alternate between π1 and π2
    • The algorithm performs 100 augmentations
  • Finding an augmenting path and augmenting the flow takes O(n + m) time
  • The running time of Ford- Fulkerson’s algorithm is O(|f*|(n + m))

Network_Flow