Basic flow definitions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 29: Line 29:


== Valid distance labeling ==
== Valid distance labeling ==
'''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:
## 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>.
# If even <math>d(v)=d(w)+1</math>, <math>(v,w)</mah> is called an '''admissible arc'''.

Revision as of 11:07, 13 October 2014

Residual network

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

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

Therefore, 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] could be changed within the capacity constraints just by changes of the flow values of [math]\displaystyle{ (v,w) }[/math] and [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>(v,w)</mah> is called an admissible arc.