Basic flow definitions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(56 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Basic definitions ==
# [[Basic graph definitions]]
== 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.  
On this page and all dependent pages, <math>G=(V,A)</math> is an [[Basic graph definitions#Directed and undirected graphs|anti-symmetric, simple directed graph]], unless stated otherwise.  
# For <math>a\in A</math>, there is a nonnegative '''upper bound''' <math>u(a)</math>.
# 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.
# In some flow problems, there is a '''lower bound''' <math>\ell(a)</math> as well, which need not be nonnegative.
# In some flow problems, each node <math>v\in V</math> has a '''required balance''' (or '''balance''' for short) <math>b(v)</math>. We also speak of the '''node balance'''.
# In some flow problems, each node <math>v\in V</math> has a '''required balance''' (or '''balance''' for short) <math>b(v)</math>. We also speak of the '''node balance'''.
# In some flow problems, there is a real-valued (not necessarily nonnegative) '''cost factor''' <math>c(a)</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 occur in specific flow problems.
Other node and arc attributes may occur in specific flow problems. Unless stated otherwise, there are no  node or arc attributes except for the upper bounds on arcs.


'''Neutral values of attributes:'''
'''Neutral values of attributes:'''
Line 11: Line 15:


'''Remark:'''
'''Remark:'''
Simplicity and symmetry do not reduce generality in the context of flow problems:
[[Basic graph definitions#Directed and undirected graphs|Simplicity and anti-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>, transfer the attribute values of <math>a_1</math> to <math>(v,u)</math> and set all attributes of <math>u</math> and of <math>(u,w)</math> to their neutral values.
# 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</math> and 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 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 and lower bound.
# If <math>(v,w),(w,v)\in A</math>, add a new node <math>u</math> to <math>V</math>, replace  <math>(v,w)</math> by new arcs <math>(v,u)</math> and <math>(u,w)</math>, and set the attribute values analogously to the case of parallel arcs.


'''Integrality assumption:'''
'''Integrality assumption:'''
All numerical node and arc attributes are integral.
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>\delta>0</math> and replacing each attribute value by the nearest integral multiple of <math>\delta</math> has a negligible impact on the output.
In the context of flow problems, this assumption usually does not reduce generality, either: Choosing a sufficiently small <math>\delta>0</math> and replacing each attribute value by the nearest integral multiple of <math>\delta</math> has a negligible impact on the output, at least in the classical types of flow problems.
 
== Feasible flow ==


== Feasible flow and flow value ==
Let <math>f</math> be an arc weighting, that is, a value <math>f(a)</math> is given for each arc <math>a\in A</math>.


'''Capacity constraints:'''
'''Capacity constraints:'''
Let <math>f</math> be an arc weighting, that is, a value <math>f(a)</math> is given for each arc <math>a\in A</math>.
# We say that <math>f</math> fulfills the '''capacity constraints''' if <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# We say that <math>f</math> fulfills the '''capacity constraints''' if <math>0\leq f(a)\leq u(a)</math> for all <math>a\in A</math>.
# If lower bounds <math>\ell</math> are given, the condition <math>f(a)\geq 0</math> is to be replaced by <math>f(a)\geq\ell(a)</math>. In particular, <math>f(a)</math> may be negative if <math>\ell(a)</math> is so.
# If lower bounds <math>\ell</math> are given, the condition <math>f(a)\geq 0</math> is to be replaced by <math>f(a)\geq\ell(a)</math>. In particular, <math>f(a)</math> may be negative if <math>\ell(a)</math> is so.
Line 30: Line 35:
'''Flow conservation condition:'''
'''Flow conservation condition:'''
Let <math>W\subseteq V</math>.
Let <math>W\subseteq V</math>.
# An arc weighting fulfills the flow conservation condition with respect to <math>W</math> if for all nodes <math>v\in V</math>: <math>\sum_{w\in V\atop(v,w)\in A}f(v,w)-\sum_{w\in V\atop(w,v)\in A}f(w,v)=0</math>.
# An arc weighting fulfills the flow conservation condition with respect to <math>W</math> if for all nodes <math>v\in V\setminus W</math>: <math>\sum_{w\in V\atop(v,w)\in A}f(v,w)-\sum_{w\in V\atop(w,v)\in A}f(w,v)=0</math>.
# If there are balance values <math>b(v)</math> for all nodes <math>v\in V\setminus W</math>, the right-hand side of this condition is not zero but <math>b(v)</math>.
# If there are balance values <math>b(v)</math> for all nodes <math>v\in V\setminus W</math>, the right-hand side of this condition is not zero but <math>b(v)</math>.


A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
'''Feasibility:'''
# A '''feasible flow''' (or '''flow''' for short) with respect to <math>W\subseteq V</math> is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
# For <math>S,T\subseteq V</math>, a '''feasible <math>(S,T)</math>-flow''' is a feasible flow with respect to <math>W=S\cup T</math>.
# For <math>s,t\in V</math>, a '''feasible <math>(s,t)</math>-flow''' is a feasible flow with respect to <math>W=\{s,t\}</math>.


== Preflow ==
== Preflow ==


# Preflows generalize feasible flows as follows: Instead of an equation, the following inequality is to be fulfilled for each <math>v\in V\setminus W</math>: <math>\sum_{w:(v,w)\in A}f(v,w)-\sum_{w:(w,v)\in A}f(w,v)\geq 0</math> (resp., <math>\geq b(v)</math>, if node balances are given).
# Preflows generalize feasible flows as follows: Instead of an equation, the following inequality is to be fulfilled for each <math>v\in V\setminus W</math>: <math>\sum_{w:(w,v)\in A}f(w,v)-\sum_{w:(v,w)\in A}f(v,w)\geq 0</math> (resp., <math>\geq b(v)</math>, if node balances are given).
# The '''excess''' of <math>v\in V\setminus W</math> is the value of the left-hand side of that inequality.
# The '''excess''' of <math>v\in V\setminus W</math> is the value of the left-hand side of that inequality. A node is '''active''' if its excess is strictly positive.


== Flow value ==
== Flow value ==


Let <math>S,T\in V</math> such that <math>S\cap T=\emptyset</math>, and let <math>f</math> be a flow with respect to <math>S\cup T</math>. The '''flow value''' <math>v(f)</math> of <math>f</math> is defined by
Let <math>S,T\subseteq V</math> such that <math>S\cap T=\emptyset</math>, and let <math>f</math> be a flow with respect to <math>S\cup T</math>. The '''flow value''' <math>v(f)</math> of <math>f</math> is defined by
:<math>\sum_{s\in S,v\in V\setminus S\atop(s,v)\in A}f(s,v)-\sum_{s\in S,v\in V\setminus S\atop(v,s)\in A}f(v,s)</math>.
:<math>v(f):=\sum_{s\in S,v\in V\setminus S\atop(s,v)\in A}f(s,v)-\sum_{s\in S,v\in V\setminus S\atop(v,s)\in A}f(v,s)</math>.


'''Remark:'''
'''Remark:'''
A straightforward induction on <math>k\geq|S|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>|V_S|=k</math>, it is
A straightforward induction on <math>k\geq|V_S|</math> shows that for all partitions <math>(V_S,V_T)</math> of <math>V</math> with <math>S\subseteq V_S</math>, <math>T\subseteq V_T</math> and <math>|V_S|=k</math>, it is
:<math>v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_T,w\in V_S\atop(v,w)\in A}f(v,w)</math>.
:<math>v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_S,w\in V_T\atop(w,v)\in A}f(w,v)</math>.
In particular, mirror-symmetrically to the definition of <math>v(f)</math>, it is
In particular, mirror-symmetrically to the definition of <math>v(f)</math>, it is
:<math>v(f)=\sum_{v\in V\setminus T,t\in T\atop(v,t)\in A}f(v,t)-\sum_{v\in V\setminus T,t\in T\atop(t,v)\in A}f(t,v)</math>.
:<math>v(f)=\sum_{v\in V\setminus T,t\in T\atop(v,t)\in A}f(v,t)-\sum_{v\in V\setminus T,t\in T\atop(t,v)\in A}f(t,v)</math>.
Line 53: Line 61:
== Residual network ==
== Residual network ==


The '''residual network''' of <math>(G,u)</math> with respect to an arc weighting <math>f</math> is the pair <math>(G_f,u_f)</math>, where <math>u_f</math> is defined by  <math>u_f(v,w):=u(v,w)-f(v,w)+f(w,v)</math> for all <math>(v,w)\in A'</math>. The value <math>u_f(a)</math> is called the '''residual capacity''' of <math>a\in A</math> with respect to <math>f</math>. The graph <math>G_f</math> consists of all nodes of <math>G</math> and, specifically, of all arcs of <math>G</math> with positive residual capacities.
The '''residual network''' <math>(G_f,u_f)</math> of <math>(G,u)</math> with respect to an arc weighting <math>f</math> is defined as follows: It is <math>G_f=(V,A_f)</math>, and for each arc <math>(v,w)\in A</math>, we have:
# <math>(v,w)\in A_f</math> with <math>u_f(v,w)=u(v,w)-f(v,w)</math> if <math>u(v,w)-f(v,w)>0</math>.
# <math>(w,v)\in A_f</math> with <math>u_f(w,v)=f(v,w)</math> if <math>f(v,w)>0</math>.
The value <math>u_f(a)</math> of an arc <math>a\in A_f</math>is called the '''residual capacity''' of <math>a\in A</math> with respect to <math>f</math>.


'''Remarks:'''
'''Remark:'''
# Roughly speaking, the residual capacity of an arc <math>(v,w)\in A</math> is the amount by which the net flow from <math>v</math> to <math>w</math> could be increased within the capacity constraints solely by increasing the flow value of <math>(v,w)</math> and decreasing the flow value of <math>(w,v)</math>.
Changes of <math>f</math> in <math>G</math> and changes of <math>u_f</math> in <math>G_f</math> are equivalent in an obvious way. Since <math>G</math> is anti-symmetric, this equivalence is one-to-one. So, the view on <math>G</math> and <math>f</math> is exchangeable with the view on <math>G_f</math> and <math>u_f</math>. We will adopt both views simultaneously in the presentation and discussion of the individual algorithms. An implementation of an algorithm may be based on <math>(G,f)</math> or on <math>(G_f,u_f)</math> or even on both representations simultaneously.
# Changes of <math>f</math> in <math>G</math> and changes of <math>u_f</math> in <math>G_f</math> are equivalent in a one-to-one correspondence. So, the view on <math>G</math> and <math>f</math> is exchangeable with the view on <math>G_f</math> and <math>u_f</math>. We will adopt both views in the discussion of the individual algorithms.


== Flow-augmenting paths and saturated arcs ==
== Flow-augmenting paths and saturated arcs ==
Line 71: Line 81:
== Augmenting along a path ==
== Augmenting along a path ==


Let <math>p</math> denote some flow-augmenting path, and let <math>\varepsilon>0</math> such that
Let <math>p</math> denote some flow-augmenting path in <math>G</math>, and let <math>\varepsilon>0</math> such that
# <math>f(a)+\varepsilon\leq u(a)</math> if <math>a\in A</math> is a forward arc;
# <math>f(a)+\varepsilon\leq u(a)</math> if <math>a\in A</math> is a forward arc;
# <math>f(a)-\varepsilon\geq 0</math> if <math>a\in A</math> is a backward arc.
# <math>f(a)-\varepsilon\geq 0</math> if <math>a\in A</math> is a backward arc.
In the residual network, '''augmenting''' <math>f</math> by <math>\varepsilon</math> along <math>p</math> means reducing all residual capacities by <math>\varepsilon</math>. Equivalently, for each arc <math>a \in A</math> on <math>p</math> in <math>G</math>, this means:   
In the residual network <math>(G_f,u_f)</math>, '''augmenting''' <math>f</math> by <math>\varepsilon</math> along the [[Basic graph definitions#Paths|ordinary path]] induced by <math>p</math> means reducing all residual capacities by <math>\varepsilon</math>. Equivalently, for each arc <math>a \in A</math> on <math>p</math> in <math>G</math>, this means:   
# Increase the flow value by <math>\varepsilon</math> if <math>a</math> is a forward arc on <math>p</math>.
# Increase the flow value by <math>\varepsilon</math> if <math>a</math> is a forward arc on <math>p</math>.
# Decrease the flow value by <math>\min \{x,y \}</math> if <math>a</math> is a backward arc on <math>p</math>.
# Decrease the flow value by <math>\varepsilon</math> if <math>a</math> is a backward arc on <math>p</math>.
Obviously, the capacity constraints are preserved. The flow conservation conditions are preserved at every [[Basic graph definitions#Paths|internal node]] of <math>p</math>. To see that, let <math>v</math> be such an internal node, and let <math>u</math> and <math>w</math> denote the immediate predecessor and successor of <math>v</math> on <math>p</math>, respectively. Basically, there are four cases:
Obviously, the capacity constraints are preserved. The flow conservation conditions are preserved at every [[Basic graph definitions#Paths|internal node]] of <math>p</math>. To see that, let <math>v</math> be such an internal node, and let <math>u</math> and <math>w</math> denote the immediate predecessor and successor of <math>v</math> on <math>p</math>, respectively. Basically, there are four cases:
*Either <math>(u,v)</math> is on <math>p</math> as a forward arc or <math>(v,u)</math> is on <math>p</math>  as a backward arc.
*Either <math>(u,v)</math> is on <math>p</math> as a forward arc or <math>(v,u)</math> is on <math>p</math>  as a backward arc.
Line 84: Line 94:
'''Augmenting up to saturation:'''
'''Augmenting up to saturation:'''
Again, let <math>p</math> denote some flow-augmenting path.
Again, let <math>p</math> denote some flow-augmenting path.
# Let <math>\varepsilon_1>0</math> denote the minimum of the values <math>c(a)-f(a)</math> on all forward arcs of <math>p</math>.
# Let <math>\varepsilon_1>0</math> denote the minimum of the values <math>u(a)-f(a)</math> on all forward arcs of <math>p</math>.
# Let <math>\varepsilon_2>0</math> denote the minimum of the values <math>f(a)</math> on all backward arcs of <math>p</math>.
# Let <math>\varepsilon_2>0</math> denote the minimum of the values <math>f(a)</math> on all backward arcs of <math>p</math>.
# Let <math>\varepsilon</math> denote the minimum of <math>\varepsilon</math> and <math>\varepsilon_2</math>.
# Let <math>\varepsilon</math> denote the minimum of <math>\varepsilon</math> and <math>\varepsilon_2</math>.
Augmenting the flow <math>f</math> along <math>p</math> by <math>\varepsilon</math> yields at least one saturated arc.
Augmenting the flow <math>f</math> along <math>p</math> by <math>\varepsilon</math> yields at least one saturated arc.
== Cuts and saturated cuts ==
# Let <math>G=(V,A)</math> be a directed graph and <math>s,t\in V</math>. An <math>(s,t)</math>-'''cut''' (or '''cut''' for short) is a bipartition <math>(S,T)</math> of <math>V</math> such that <math>s\in S</math> and <math>t\in T</math>.
# For <math>a\in A</math>, let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math> (<math>f</math> need not be a flow here). A cut <math>(S,T)</math> is '''saturated''' if:
## <math>f(v,w)=u(v,w)</math> for every arc <math>(v,w)\in A</math> such that <math>v\in S</math> and <math>w\in T</math>.
## <math>f(v,w)=0</math> for every arc <math>(v,w)\in A</math> such that <math>v\in T</math> and <math>w\in S</math>.


== Valid distance labeling ==
== Valid distance labeling ==


'''Definition:'''
'''Definition:'''
# Let <math>G=(V,A))</math> be a directed graph, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be defined such that <math>0\leq f(a)\leq u(a)</math>. An assignment of a value <math>d(v)</math> to each node <math>v\in V</math> is a '''valid distance labeling''' if the following two conditions ar fulfilled:
# Let <math>G=(V,A)</math> be a directed graph, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be defined such that <math>0\leq f(a)\leq u(a)</math>. An assignment of a value <math>d(v)</math> to each node <math>v\in V</math> is a '''valid distance labeling''' if the following two conditions ar fulfilled:
## It is <math>d(t)=0</math>.
## It is <math>d(t)=0</math>.
## For each arc <math>(v,w)\in A</math> in the residual network, it is <math>d(v)\leq d(w)+1</math>.
## For each arc <math>(v,w)\in A</math> in the residual network, it is <math>d(v)\leq d(w)+1</math>.
# If even <math>d(v)=d(w)+1</math>, <math>(v,w)</math> is called an '''admissible arc'''.
# If even <math>d(v)=d(w)+1</math>, <math>(v,w)</math> is called an '''admissible arc'''.
== Blocking flow ==
'''Definition:'''
Let <math>G=(V,A)</math> be a directed graph, let <math>s,t\in V</math>, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math>. We say that <math>f</math> is a '''blocking flow''' if every flow augmenting <math>(s,t)</math>-path contains at least one backward arc.
'''Remarks:'''
# The name refers to an alternative, equivalent definition: Every ordinary <math>(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>G=(V,A)</math> be a directed graph and <math>s,t\in V</math>. An <math>(s,t)</math>-'''cut''' (or '''cut''' for short) is a bipartition <math>(S,T)</math> of <math>V</math> such that <math>s\in S</math> and <math>t\in T</math>.
# For <math>a\in A</math>, let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math> (<math>f</math> need not be a flow here). A cut <math>(S,T)</math> is '''saturated''' if:
## <math>f(v,w)=u(v,w)</math> for every arc <math>(v,w)\in A</math> such that <math>v\in S</math> and <math>w\in T</math>.
## <math>f(v,w)=0</math> for every arc <math>(v,w)\in A</math> such that <math>v\in T</math> and <math>w\in S</math>.

Latest revision as of 13:42, 17 November 2015

Basic definitions

  1. Basic graph definitions

Basic setting

On this page and all dependent pages, [math]\displaystyle{ G=(V,A) }[/math] is an anti-symmetric, simple directed graph, unless stated otherwise.

  1. For [math]\displaystyle{ a\in A }[/math], there is a nonnegative upper bound [math]\displaystyle{ u(a) }[/math].
  2. In some flow problems, there is a lower bound [math]\displaystyle{ \ell(a) }[/math] as well, which need not be nonnegative.
  3. 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]. We also speak of the node balance.
  4. 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 occur in specific flow problems. Unless stated otherwise, there are no node or arc attributes except for the upper bounds on arcs.

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 anti-symmetry do not reduce generality in the context of flow problems:

  1. If there are two arcs [math]\displaystyle{ a_1 }[/math] and [math]\displaystyle{ a_2 }[/math], say, from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ 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 }[/math] and of [math]\displaystyle{ (u,w) }[/math] to their neutral values.
  2. 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.
  3. If [math]\displaystyle{ (v,w),(w,v)\in A }[/math], add a new node [math]\displaystyle{ u }[/math] to [math]\displaystyle{ V }[/math], replace [math]\displaystyle{ (v,w) }[/math] by new arcs [math]\displaystyle{ (v,u) }[/math] and [math]\displaystyle{ (u,w) }[/math], and set the attribute values analogously to the case of parallel arcs.

Integrality assumption: All numerical node and arc attributes are integral.

In the context of flow problems, this assumption usually 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, at least in the classical types of flow problems.

Feasible flow

Let [math]\displaystyle{ f }[/math] be an arc weighting, that is, a value [math]\displaystyle{ f(a) }[/math] is given for each arc [math]\displaystyle{ a\in A }[/math].

Capacity constraints:

  1. We say that [math]\displaystyle{ f }[/math] fulfills the capacity constraints if [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] for all [math]\displaystyle{ a\in A }[/math].
  2. If lower bounds [math]\displaystyle{ \ell }[/math] are given, the condition [math]\displaystyle{ f(a)\geq 0 }[/math] is to be replaced by [math]\displaystyle{ f(a)\geq\ell(a) }[/math]. In particular, [math]\displaystyle{ f(a) }[/math] may be negative if [math]\displaystyle{ \ell(a) }[/math] is so.

Flow conservation condition: Let [math]\displaystyle{ W\subseteq V }[/math].

  1. An arc weighting fulfills the flow conservation condition with respect to [math]\displaystyle{ W }[/math] if for all nodes [math]\displaystyle{ v\in V\setminus W }[/math]: [math]\displaystyle{ \sum_{w\in V\atop(v,w)\in A}f(v,w)-\sum_{w\in V\atop(w,v)\in A}f(w,v)=0 }[/math].
  2. If there are balance values [math]\displaystyle{ b(v) }[/math] for all nodes [math]\displaystyle{ v\in V\setminus W }[/math], the right-hand side of this condition is not zero but [math]\displaystyle{ b(v) }[/math].

Feasibility:

  1. A feasible flow (or flow for short) with respect to [math]\displaystyle{ W\subseteq V }[/math] is an arc weighting that satisfies the capacity constraints and the flow conservation condition.
  2. For [math]\displaystyle{ S,T\subseteq V }[/math], a feasible [math]\displaystyle{ (S,T) }[/math]-flow is a feasible flow with respect to [math]\displaystyle{ W=S\cup T }[/math].
  3. For [math]\displaystyle{ s,t\in V }[/math], a feasible [math]\displaystyle{ (s,t) }[/math]-flow is a feasible flow with respect to [math]\displaystyle{ W=\{s,t\} }[/math].

Preflow

  1. Preflows generalize feasible flows as follows: Instead of an equation, the following inequality is to be fulfilled for each [math]\displaystyle{ v\in V\setminus W }[/math]: [math]\displaystyle{ \sum_{w:(w,v)\in A}f(w,v)-\sum_{w:(v,w)\in A}f(v,w)\geq 0 }[/math] (resp., [math]\displaystyle{ \geq b(v) }[/math], if node balances are given).
  2. The excess of [math]\displaystyle{ v\in V\setminus W }[/math] is the value of the left-hand side of that inequality. A node is active if its excess is strictly positive.

Flow value

Let [math]\displaystyle{ S,T\subseteq V }[/math] such that [math]\displaystyle{ S\cap T=\emptyset }[/math], and let [math]\displaystyle{ f }[/math] be a flow with respect to [math]\displaystyle{ S\cup T }[/math]. The flow value [math]\displaystyle{ v(f) }[/math] of [math]\displaystyle{ f }[/math] is defined by

[math]\displaystyle{ v(f):=\sum_{s\in S,v\in V\setminus S\atop(s,v)\in A}f(s,v)-\sum_{s\in S,v\in V\setminus S\atop(v,s)\in A}f(v,s) }[/math].

Remark: A straightforward induction on [math]\displaystyle{ k\geq|V_S| }[/math] shows that for all partitions [math]\displaystyle{ (V_S,V_T) }[/math] of [math]\displaystyle{ V }[/math] with [math]\displaystyle{ S\subseteq V_S }[/math], [math]\displaystyle{ T\subseteq V_T }[/math] and [math]\displaystyle{ |V_S|=k }[/math], it is

[math]\displaystyle{ v(f)=\sum_{v\in V_S,w\in V_T\atop(v,w)\in A}f(v,w)-\sum_{v\in V_S,w\in V_T\atop(w,v)\in A}f(w,v) }[/math].

In particular, mirror-symmetrically to the definition of [math]\displaystyle{ v(f) }[/math], it is

[math]\displaystyle{ v(f)=\sum_{v\in V\setminus T,t\in T\atop(v,t)\in A}f(v,t)-\sum_{v\in V\setminus T,t\in T\atop(t,v)\in A}f(t,v) }[/math].

Residual network

The residual network [math]\displaystyle{ (G_f,u_f) }[/math] of [math]\displaystyle{ (G,u) }[/math] with respect to an arc weighting [math]\displaystyle{ f }[/math] is defined as follows: It is [math]\displaystyle{ G_f=(V,A_f) }[/math], and for each arc [math]\displaystyle{ (v,w)\in A }[/math], we have:

  1. [math]\displaystyle{ (v,w)\in A_f }[/math] with [math]\displaystyle{ u_f(v,w)=u(v,w)-f(v,w) }[/math] if [math]\displaystyle{ u(v,w)-f(v,w)\gt 0 }[/math].
  2. [math]\displaystyle{ (w,v)\in A_f }[/math] with [math]\displaystyle{ u_f(w,v)=f(v,w) }[/math] if [math]\displaystyle{ f(v,w)\gt 0 }[/math].

The value [math]\displaystyle{ u_f(a) }[/math] of an arc [math]\displaystyle{ a\in A_f }[/math]is called the residual capacity of [math]\displaystyle{ a\in A }[/math] with respect to [math]\displaystyle{ f }[/math].

Remark: 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 an obvious way. Since [math]\displaystyle{ G }[/math] is anti-symmetric, this equivalence is one-to-one. 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 simultaneously in the presentation and discussion of the individual algorithms. An implementation of an algorithm may be based on [math]\displaystyle{ (G,f) }[/math] or on [math]\displaystyle{ (G_f,u_f) }[/math] or even on both representations simultaneously.

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:

  1. [math]\displaystyle{ f(a)\lt u(a) }[/math] if [math]\displaystyle{ a\in A }[/math] is a forward arc;
  2. [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

  1. in forward direction if [math]\displaystyle{ f(a)=u(a) }[/math].
  2. 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 in [math]\displaystyle{ G }[/math], and let [math]\displaystyle{ \varepsilon\gt 0 }[/math] such that

  1. [math]\displaystyle{ f(a)+\varepsilon\leq u(a) }[/math] if [math]\displaystyle{ a\in A }[/math] is a forward arc;
  2. [math]\displaystyle{ f(a)-\varepsilon\geq 0 }[/math] if [math]\displaystyle{ a\in A }[/math] is a backward arc.

In the residual network [math]\displaystyle{ (G_f,u_f) }[/math], augmenting [math]\displaystyle{ f }[/math] by [math]\displaystyle{ \varepsilon }[/math] along the ordinary path induced by [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:

  1. Increase the flow value by [math]\displaystyle{ \varepsilon }[/math] if [math]\displaystyle{ a }[/math] is a forward arc on [math]\displaystyle{ p }[/math].
  2. Decrease the flow value by [math]\displaystyle{ \varepsilon }[/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.

  1. Let [math]\displaystyle{ \varepsilon_1\gt 0 }[/math] denote the minimum of the values [math]\displaystyle{ u(a)-f(a) }[/math] on all forward arcs of [math]\displaystyle{ p }[/math].
  2. 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].
  3. 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.

Cuts and saturated cuts

  1. 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].
  2. 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:
    1. [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].
    2. [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].

Valid distance labeling

Definition:

  1. 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:
    1. It is [math]\displaystyle{ d(t)=0 }[/math].
    2. 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].
  2. If even [math]\displaystyle{ d(v)=d(w)+1 }[/math], [math]\displaystyle{ (v,w) }[/math] is called an admissible arc.