Max-Flow Problems

Assumptions

For convenience, without loss of generality:

1. In all variations below, all numbers are integral: real numbers may be approximated by uniformly distant numbers with a negligible loss of precision.
2. There are no parallel arcs in directed graphs: if there are parallel arcs, they may be replaced by one of them, with their upper bounds, lower bounds, and flow values summed up, respectively.

Standard version

Input:

1. A directed graph [math]\displaystyle{ G=(V,A) }[/math].
2. A source node [math]\displaystyle{ s\in V }[/math] and a target (a.k.a. sink) node [math]\displaystyle{ t\in V }[/math].
3. A nonnegative upper bound (a.k.a. capacity) [math]\displaystyle{ u(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math].

Output: A maximum [math]\displaystyle{ (s,t) }[/math]-flow, that is, a nonnegative value [math]\displaystyle{ f(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math] such that the following two conditions are fulfilled:

1. Capacity constraint: For each arc [math]\displaystyle{ a\in A }[/math], it is [math]\displaystyle{ f(a)\leq u(a) }[/math].
2. Flow conservation condition: For each node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math], it is [math]\displaystyle{ \sum_{a=(v,w)\in A}f(a)=\sum_{a=(w,v)\in A}f(a) }[/math].

Generalizations

1. For each arc [math]\displaystyle{ a\in A }[/math], there is a lower bound [math]\displaystyle{ \ell(a) }[/math], and [math]\displaystyle{ f(a)\geq\ell(a) }[/math] is additionally required. The lower bounds need not be nonnegative, so the flow values need not be nonnegative, either. This version may be reduced to the standard version as follows:
   1. For each arc [math]\displaystyle{ (v,w)\in A }[/math] with a lower bound [math]\displaystyle{ \ell(v,w)\lt 0 }[/math], add [math]\displaystyle{ -ell(v,w) }[/math]to the upper bound of [math]\displaystyle{ (w,v) }[/math] (or, if [math]\displaystyle{ (w,v) # More than one source and more than one target can be reduced to the standard version by adding a super-source node and a super-target node # Usually, the term ''generalized flow''' is reserved for the specific generalization in which for each node \lt math\gt v\in V\setminus\{vs,t\} }[/math], the ratio of the total sum of all incoming flow an the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).