====== 7.7 Extensions to the Maximum-Flow Problem ======
\\
===== The Problem: Circulations with Demands =====

  * Directed graph G = (V, E)
  * Edge capacities c(e), e ∈ E
  * Node supply and demands d(v), v ∈ V:
    * If d(v) > 0: node v has demand of d(v) flow--> The node is a sink and wishes to receive d(v) units more flow than it sends out
    * If d(v) < 0: The node v has a supply of -d(v)--> The node is a source and wishes to send out -d(v) units more flow than it receives
    * If d(v) = 0: Then the node is neither a source nor a sink.
  * A circulation is a function that satisfies:
    * For each e ∈ E: 0 ≤ f(e) ≤ c(e) (capacity condition)
    * For each v ∈ V: f<sup>in</sup>(v) - f<sup>out</sup>(v) = d(v)(Demand conditions)
  * Feasibility Problem: We want to know if there exists a circulation that satisfies the just-mentioned conditions
  * If there exists a feasible circulation with demands {d(v)}, then ∑<sub>v</sub> d(v) =0\\
\\
===== Designing And Analyzing an Algorithm for Circulations =====
\\
  * The problem of finding feasible circulation can be reduced to the problem of finding a maximum s-t flow in a different network.
  * Add new source s and sink t
  * For each v with d(v) < 0, add edge (s, v) with capacity -d(v)
  * For each v with d(v) > 0, add edge (v, t) with capacity d(v)
  * ∑<sub>v:d(v)>0</sub>d(v) = ∑<sub>v:d(v)< 0</sub>-d(v). Let's call this common value D.
  * Claim: G has circulation iff G' has max flow of value D
  * Given (V, E, c, d), there //does not exist// a circulation iff there exists a node partition (A, B) such that:
    * Σ<sub>v∈B</sub> d(v) > cap(A, B) => demand by nodes in B exceeds supply of nodes in B + max capacity of edges going from A --> B\\
\\
===== The Problem: Circulations with Demands And Lower Bounds =====
\\
  * In many problems, not only do we want to satisfy demands at various nodes, but we also want to enforce the flow to make use of certain edges.
  * That's why we need to place //lower bounds// on edges as well as the //upper bounds// restricted by the capacities
  * Feasible circulation
    * Directed graph G = (V, E)
    * Edge capacities c(e) and lower bounds l(e)(Force flow to use certain edges), e ∈ E
    * Node supply and demands d(v), v ∈ V
  * A circulation is a function that satisfies:
    * For each e ∈ E: 0 ≤ l(e) ≤ f(e) ≤ c(e) (capacity)
    * For each v ∈ V: f<sup>in</sup>(v) - f<sup>out</sup>(v) = d(v)(conservation)
    * Goal: Decide whether or not there exists a feasible circulation(the circulation that satisfies the above conditions)\\
\\
=====  Designing And Analyzing an Algorithm with Lower Bounds ====
\\
  * Strategy: Reduce the problem to the one of finding a circulation with demands but no lower bounds, which can in turn be reduced to the Maximum-Flow Problem.
  * How to proceed?:
    * On each edge, we need to send at least l(e) units of flow.
    * Update demands of both endpoints\\
\\
I give this section a 7/10.