Basic flow definitions: Difference between revisions
Line 1: | Line 1: | ||
== Basic setting == | == Basic setting == | ||
On this page and all dependent pages, <math>G=(V,A)</math> is a [[Basic graph definitions#Directed and undirected graphs|symmetric, simple directed graph]], unless stated otherwise. For <math>a\in A</math>, there is a nonnegative '''upper bound''' <math>u(a)</math>. In some flow problems, there is a '''lower bound''' <math>\ell(a)</math> as well, which need not be nonnegative. It is then required <math>\ell(a)\leq f(a)\leq u(a)</math>, so <math>f(a)</math> may be negative if <math>\ell(a)</math> is so. In some flow problems, there is a real-valued (not necessarily nonnegative) '''cost factor''' <math>c(a)</math>. Other node and arc attributes may be occur in specific flow problems. | On this page and all dependent pages, <math>G=(V,A)</math> is a [[Basic graph definitions#Directed and undirected graphs|symmetric, simple directed graph]], unless stated otherwise. | ||
# For <math>a\in A</math>, there is a nonnegative '''upper bound''' <math>u(a)</math>. | |||
# In some flow problems, there is a '''lower bound''' <math>\ell(a)</math> as well, which need not be nonnegative. It is then required <math>\ell(a)\leq f(a)\leq u(a)</math>, so <math>f(a)</math> may be negative if <math>\ell(a)</math> is so. | |||
# In some flow problems, each node <math>v\in V</math> has a '''required balance''' (or '''balance''' for short) <math>b(v)</math>. | |||
# In some flow problems, there is a real-valued (not necessarily nonnegative) '''cost factor''' <math>c(a)</math>. | |||
Other node and arc attributes may be occur in specific flow problems. | |||
'''Neutral values of attributes:''' | |||
When a node or arc is added to a graph, it is sometimes appropriate to set its attributes to neutral values. The neutral values for upper and lower bounds are <math>+\infty</math> and <math>-\infty</math>, respectively. For cost factors and node balances, the neutral value is zero. | |||
'''Remark:''' | '''Remark:''' | ||
Simplicity and symmetry do not reduce generality in the context of flow problems: | Simplicity and symmetry do not reduce generality in the context of flow problems: | ||
# If there are two arcs <math>a_1</math> and <math>a_2</math>, say, from <math>v</math> to </math>w</math>, add a new node <math>u</math> to <math>V</math>, replace <math>a_1</math> by new arcs <math>(v,u)</math> and <math>(u,w)</math>, | # If there are two arcs <math>a_1</math> and <math>a_2</math>, say, from <math>v</math> to </math>w</math>, add a new node <math>u</math> to <math>V</math>, replace <math>a_1</math> by new arcs <math>(v,u)</math> and <math>(u,w)</math>, transfer the attribute values of <math>a_1</math> to <math>(v,u)</math> and set all attributes of <math>(u,w)</math> to their neutral values. | ||
# | # If there is a loop <math>(v,v)</math>, add a new node <math>w</math> to <math>V</math>, replace <math>(v,v)</math> by <math>(v,w)</math> and <math>(w,v)</math>, and set the attribute values analogously to the case of parallel arcs. | ||
If <math>(w,v)\not\in A</math> for some <math>(v,w)\in A</math>, we may add <math>(w,v)</math> with zero upper bound. | # If <math>(w,v)\not\in A</math> for some <math>(v,w)\in A</math>, we may add <math>(w,v)</math> with zero upper bound. | ||
'''Integrality assumption:''' | '''Integrality assumption:''' |
Revision as of 09:25, 9 November 2014
Basic setting
On this page and all dependent pages, [math]\displaystyle{ G=(V,A) }[/math] is a symmetric, simple directed graph, unless stated otherwise.
- For [math]\displaystyle{ a\in A }[/math], there is a nonnegative upper bound [math]\displaystyle{ u(a) }[/math].
- In some flow problems, there is a lower bound [math]\displaystyle{ \ell(a) }[/math] as well, which need not be nonnegative. It is then required [math]\displaystyle{ \ell(a)\leq f(a)\leq u(a) }[/math], so [math]\displaystyle{ f(a) }[/math] may be negative if [math]\displaystyle{ \ell(a) }[/math] is so.
- In some flow problems, each node [math]\displaystyle{ v\in V }[/math] has a required balance (or balance for short) [math]\displaystyle{ b(v) }[/math].
- In some flow problems, there is a real-valued (not necessarily nonnegative) cost factor [math]\displaystyle{ c(a) }[/math].
Other node and arc attributes may be occur in specific flow problems.
Neutral values of attributes: When a node or arc is added to a graph, it is sometimes appropriate to set its attributes to neutral values. The neutral values for upper and lower bounds are [math]\displaystyle{ +\infty }[/math] and [math]\displaystyle{ -\infty }[/math], respectively. For cost factors and node balances, the neutral value is zero.
Remark: Simplicity and symmetry do not reduce generality in the context of flow problems:
- If there are two arcs [math]\displaystyle{ a_1 }[/math] and [math]\displaystyle{ a_2 }[/math], say, from [math]\displaystyle{ v }[/math] to </math>w</math>, add a new node [math]\displaystyle{ u }[/math] to [math]\displaystyle{ V }[/math], replace [math]\displaystyle{ a_1 }[/math] by new arcs [math]\displaystyle{ (v,u) }[/math] and [math]\displaystyle{ (u,w) }[/math], transfer the attribute values of [math]\displaystyle{ a_1 }[/math] to [math]\displaystyle{ (v,u) }[/math] and set all attributes of [math]\displaystyle{ (u,w) }[/math] to their neutral values.
- If there is a loop [math]\displaystyle{ (v,v) }[/math], add a new node [math]\displaystyle{ w }[/math] to [math]\displaystyle{ V }[/math], replace [math]\displaystyle{ (v,v) }[/math] by [math]\displaystyle{ (v,w) }[/math] and [math]\displaystyle{ (w,v) }[/math], and set the attribute values analogously to the case of parallel arcs.
- If [math]\displaystyle{ (w,v)\not\in A }[/math] for some [math]\displaystyle{ (v,w)\in A }[/math], we may add [math]\displaystyle{ (w,v) }[/math] with zero upper bound.
Integrality assumption: All numerical node and arc attributes are integral.
In the context of flow problems, this assumption does not reduce generality, either: Choosing a sufficiently small [math]\displaystyle{ \delta\gt 0 }[/math] and replacing each attribute value by the nearest integral multiple of [math]\displaystyle{ \delta }[/math] has a negligible impact on the output.
Residual network
The residual network of [math]\displaystyle{ (G,u) }[/math] with respect to [math]\displaystyle{ f }[/math] is the pair [math]\displaystyle{ (G_f,u_f) }[/math], where [math]\displaystyle{ u_f }[/math] is defined by [math]\displaystyle{ u_f(v,w):=u(v,w)-f(v,w)+f(w,v) }[/math] for all [math]\displaystyle{ (v,w)\in A' }[/math]. The value [math]\displaystyle{ u_f(a) }[/math] is called the residual capacity of [math]\displaystyle{ a\in A }[/math] with respect to [math]\displaystyle{ f }[/math]. The graph [math]\displaystyle{ G_f }[/math] consists of all nodes of [math]\displaystyle{ G }[/math] and, specifically, of all arcs of [math]\displaystyle{ G }[/math] with positive residual capacities.
Remarks:
- Roughly speaking, the residual capacity of an arc [math]\displaystyle{ (v,w)\in A }[/math] is the amount by which the net flow from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] could be increased within the capacity constraints solely by increasing the flow value of [math]\displaystyle{ (v,w) }[/math] and decreasing the flow value of [math]\displaystyle{ (w,v) }[/math].
- Changes of [math]\displaystyle{ f }[/math] in [math]\displaystyle{ G }[/math] and changes of [math]\displaystyle{ u_f }[/math] in [math]\displaystyle{ G_f }[/math] are equivalent in a one-to-one correspondence. So, the view on [math]\displaystyle{ G }[/math] and [math]\displaystyle{ f }[/math] is exchangeable with the view on [math]\displaystyle{ G_f }[/math] and [math]\displaystyle{ u_f }[/math]. We will adopt both views in the discussion of the individual algorithms.
Flow-augmenting paths and saturated arcs
A flow-augmenting path (or augmenting path for short) from some node [math]\displaystyle{ s\in V }[/math] to some node [math]\displaystyle{ t\in V }[/math] is an ordinary path in the residual network [math]\displaystyle{ G_f }[/math]. Equivalently, a flow-augmenting path is a generalized path in [math]\displaystyle{ G }[/math] such that:
- [math]\displaystyle{ f(a)\lt u(a) }[/math] if [math]\displaystyle{ a\in A }[/math] is a forward arc;
- [math]\displaystyle{ f(a)\gt 0 }[/math] if [math]\displaystyle{ a\in A }[/math] is a backward arc.
An arc [math]\displaystyle{ a\in A }[/math] is saturated
- in forward direction if [math]\displaystyle{ f(a)=u(a) }[/math].
- in backward direction if [math]\displaystyle{ f(a)=0 }[/math].
We say that an arc of a path is saturated if it is saturated in the direction of this path. Clearly, a path is augmenting if, and only if, it contains no saturated arc in its direction.
Augmenting along a path
Let [math]\displaystyle{ p }[/math] denote some flow-augmenting path, and let [math]\displaystyle{ \varepsilon\gt 0 }[/math] such that
- [math]\displaystyle{ f(a)+\varepsilon\leq u(a) }[/math] if [math]\displaystyle{ a\in A }[/math] is a forward arc;
- [math]\displaystyle{ f(a)-\varepsilon\geq 0 }[/math] if [math]\displaystyle{ a\in A }[/math] is a backward arc.
In the residual network, augmenting [math]\displaystyle{ f }[/math] by [math]\displaystyle{ \varepsilon }[/math] along [math]\displaystyle{ p }[/math] means reducing all residual capacities by [math]\displaystyle{ \varepsilon }[/math]. Equivalently, for each arc [math]\displaystyle{ a \in A }[/math] on [math]\displaystyle{ p }[/math] in [math]\displaystyle{ G }[/math], this means:
- Increase the flow value by [math]\displaystyle{ \varepsilon }[/math] if [math]\displaystyle{ a }[/math] is a forward arc on [math]\displaystyle{ p }[/math].
- Decrease the flow value by [math]\displaystyle{ \min \{x,y \} }[/math] if [math]\displaystyle{ a }[/math] is a backward arc on [math]\displaystyle{ p }[/math].
Obviously, the capacity constraints are preserved. The flow conservation conditions are preserved at every internal node of [math]\displaystyle{ p }[/math]. To see that, let [math]\displaystyle{ v }[/math] be such an internal node, and let [math]\displaystyle{ u }[/math] and [math]\displaystyle{ w }[/math] denote the immediate predecessor and successor of [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math], respectively. Basically, there are four cases:
- Either [math]\displaystyle{ (u,v) }[/math] is on [math]\displaystyle{ p }[/math] as a forward arc or [math]\displaystyle{ (v,u) }[/math] is on [math]\displaystyle{ p }[/math] as a backward arc.
- Either [math]\displaystyle{ (v,w) }[/math] is on [math]\displaystyle{ p }[/math] as a forward arc or [math]\displaystyle{ (w,v) }[/math] is on [math]\displaystyle{ p }[/math] as a backward arc.
It is easy to check preservation of the flow conservation conditions at [math]\displaystyle{ v }[/math] for each of these four cases.
Augmenting up to saturation: Again, let [math]\displaystyle{ p }[/math] denote some flow-augmenting path.
- Let [math]\displaystyle{ \varepsilon_1\gt 0 }[/math] denote the minimum of the values [math]\displaystyle{ c(a)-f(a) }[/math] on all forward arcs of [math]\displaystyle{ p }[/math].
- Let [math]\displaystyle{ \varepsilon_2\gt 0 }[/math] denote the minimum of the values [math]\displaystyle{ f(a) }[/math] on all backward arcs of [math]\displaystyle{ p }[/math].
- Let [math]\displaystyle{ \varepsilon }[/math] denote the minimum of [math]\displaystyle{ \varepsilon }[/math] and [math]\displaystyle{ \varepsilon_2 }[/math].
Augmenting the flow [math]\displaystyle{ f }[/math] along [math]\displaystyle{ p }[/math] by [math]\displaystyle{ \varepsilon }[/math] yields at least one saturated arc.
Preflow
Preflows generalize ordinary flows as follows: Instead of an equation, the following inequality is to be fulfilled:
- [math]\displaystyle{ \sum_{w:(v,w)\in A}f(v,w)\leq\sum_{w:(w,v)\in A}f(w,v) }[/math].
The excess of [math]\displaystyle{ v\in V }[/math] is the difference between the right-hand side and the left-hand side of that inequality.
Pseudoflow
Valid distance labeling
Definition:
- Let [math]\displaystyle{ G=(V,A)) }[/math] be a directed graph, and for each arc [math]\displaystyle{ a\in A }[/math] let [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be defined such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math]. An assignment of a value [math]\displaystyle{ d(v) }[/math] to each node [math]\displaystyle{ v\in V }[/math] is a valid distance labeling if the following two conditions ar fulfilled:
- It is [math]\displaystyle{ d(t)=0 }[/math].
- For each arc [math]\displaystyle{ (v,w)\in A }[/math] in the residual network, it is [math]\displaystyle{ d(v)\leq d(w)+1 }[/math].
- If even [math]\displaystyle{ d(v)=d(w)+1 }[/math], [math]\displaystyle{ (v,w) }[/math] is called an admissible arc.
Blocking flow
Definition: Let [math]\displaystyle{ G=(V,A) }[/math] be a directed graph, let [math]\displaystyle{ s,t\in V }[/math], and for each arc [math]\displaystyle{ a\in A }[/math] let [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be real values such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math]. We say that [math]\displaystyle{ f }[/math] is a blocking flow if every flow augmenting [math]\displaystyle{ (s,t) }[/math]-path contains at least one backward arc.
Remarks:
- The name refers to an alternative, equivalent definition: Every ordinary [math]\displaystyle{ (s,t) }[/math]-path contains at least one saturated arc, which "blocks" the augmentation.
- Obviously, maximum flows are blocking flows, but not vice versa.
Cuts and saturated cuts
- Let [math]\displaystyle{ G=(V,A) }[/math] be a directed graph and [math]\displaystyle{ s,t\in V }[/math]. An [math]\displaystyle{ (s,t) }[/math]-cut (or cut for short) is a bipartition [math]\displaystyle{ (S,T) }[/math] of [math]\displaystyle{ V }[/math] such that [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\in T }[/math].
- For [math]\displaystyle{ a\in A }[/math], let [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be real values such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] ([math]\displaystyle{ f }[/math] need not be a flow here). A cut [math]\displaystyle{ (S,T) }[/math] is saturated if:
- [math]\displaystyle{ f(v,w)=u(v,w) }[/math] for every arc [math]\displaystyle{ (v,w)\in A }[/math] such that [math]\displaystyle{ v\in S }[/math] and [math]\displaystyle{ w\in T }[/math].
- [math]\displaystyle{ f(v,w)=0 }[/math] for every arc [math]\displaystyle{ (v,w)\in A }[/math] such that [math]\displaystyle{ v\in T }[/math] and [math]\displaystyle{ w\in S }[/math].