Basic flow definitions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 1: Line 1:
== Definition ==
== Definition ==
On this page and all dependent pages, <math>G=(V,A)</math> is a [[Basic graph definitions#Directed and undirected graphs|simple directed graph]], unless said otherwise. For <math>a\in A</math>, there are real values <math>u(a)</math> and <math>f(a)</math> such that <math>0\leq f(a)\leq u(a)</math>.
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 said otherwise. For <math>a\in A</math>, there are real values <math>u(a)</math> and <math>f(a)</math> such that <math>0\leq f(a)\leq u(a)</math>. The value <math>u(a)</math> is the '''upper bound''' of <math>a</math>.
 
'''Remark:'''
Simplicity and symmetry do not reduce generality. In fact, parallel arcs could be united with the upper bounds summed up. And 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.


== Residual network ==
== Residual network ==

Revision as of 17:28, 8 November 2014

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 could 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',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' }[/math] consists of all nodes of [math]\displaystyle{ G }[/math] and, specifically, of all arcs of [math]\displaystyle{ G }[/math] with positive residual capacities.

Remark: 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 just by increasing the flow value of [math]\displaystyle{ (v,w) }[/math] and decreasing the flow value of [math]\displaystyle{ (w,v) }[/math].

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.

Pseudoflow

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