Max-Flow Problems: Difference between revisions
Jump to navigation
Jump to search
| Line 15: | Line 15: | ||
A maximum <math>(s,t)</math>-flow, that is, a nonnegative value <math>f(a)</math> for each arc <math>a\in A</math> such that the following two conditions are fulfilled: | A maximum <math>(s,t)</math>-flow, that is, a nonnegative value <math>f(a)</math> for each arc <math>a\in A</math> such that the following two conditions are fulfilled: | ||
# '''Capacity constraint:''' For each arc <math>a\in A</math>, it is <math>f(a)\leq u(a)</math>. | # '''Capacity constraint:''' For each arc <math>a\in A</math>, it is <math>f(a)\leq u(a)</math>. | ||
# '''Flow conservation condition:''' For each node <math>v\in V\setminus\{s,t\}</math>, it is <math>\sum_{a=(v,w)\in A}f(a) | # '''Flow conservation condition:''' For each node <math>v\in V\setminus\{s,t\}</math>, it is <math>\sum_{a=(v,w)\in A}f(a)=\sum_{a=(w,v)\in A}f(a)</math>. | ||
== Generalizations == | == Generalizations == | ||
Revision as of 12:49, 9 October 2014
Assumptions
For convenience, without loss of generality:
- In all variations below, all numbers are integral: real numbers may be approximated by uniformly distant numbers with a negligible loss of precision.
- 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:
- A directed graph [math]\displaystyle{ G=(V,A) }[/math].
- A source node [math]\displaystyle{ s\in V }[/math] and a target (a.k.a. sink) node [math]\displaystyle{ t\in V }[/math].
- 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:
- Capacity constraint: For each arc [math]\displaystyle{ a\in A }[/math], it is [math]\displaystyle{ f(a)\leq u(a) }[/math].
- 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
- 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: For eac arc
- 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 [math]\displaystyle{ 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).