Basic flow definitions

Definition

On this page and all dependent pages, [math]\displaystyle{ G=(V,A) }[/math] is a symmetric, simple directed graph, unless said otherwise. For [math]\displaystyle{ a\in A }[/math], there are real values [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math]. The value [math]\displaystyle{ u(a) }[/math] is the upper bound of [math]\displaystyle{ a }[/math].

Remark: Simplicity and symmetry do not reduce generality. In fact, parallel arcs can be united with the upper bounds summed up. And 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.

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:

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

Let [math]\displaystyle{ G=(V,A) }[/math] be a directed graph. Without loss of generality, we assume [math]\displaystyle{ (v,w)\in A }[/math] if, and only if, [math]\displaystyle{ (w,v)\in A }[/math]. For [math]\displaystyle{ a\in A }[/math], there are real values [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math].

A flow-augmenting path from some node [math]\displaystyle{ s\in V }[/math] to some node [math]\displaystyle{ t\in V }[/math] is a path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] that may contain arcs in forward and backward, subject to:

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.

In the residual network of [math]\displaystyle{ (G,u) }[/math] with respect to [math]\displaystyle{ f }[/math], backward arcs need not be considered for flow-augmenting path.

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.

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.

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:

1. 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.
2. Obviously, maximum flows are blocking flows, but not vice versa.

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].