Basic flow definitions: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 1: Line 1:
== Residual network ==
== Residual network ==


'''Definition:'''
Let <math>G=(V,A)</math> be a directed graph. Without loss of generality, we assume <math>(v,w)\in A</math> if, and only if, <math>(w,v)\in A</math>. 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>.
Let <math>G=(V,A)</math> be a directed graph. Without loss of generality, we assume <math>(v,w)\in A</math> if, and only if, <math>(w,v)\in A</math>. 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 '''residual network''' of <math>(G,u)</math> with respect to <math>f</math> is the pair <math>(G',u_f)</math>, where <math>u_f</math> 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'</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''' of <math>(G,u)</math> with respect to <math>f</math> is the pair <math>(G',u_f)</math>, where <math>u_f</math> 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'</math> consists of all nodes of <math>G</math> and, specifically, of all arcs of <math>G</math> with positive residual capacities.


Therefore, the residual capacity of an arc <math>(v,w)\in A</math> is the amount by which the net flow from <math>v</math> could be changed within the capacity constraints just by changes of the flow values of <math>(v,w)</math> and <math>(w,v)</math>.
'''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> could be changed within the capacity constraints just by changes of the flow values of <math>(v,w)</math> and <math>(w,v)</math>.


== Flow-augmenting path ==
== Flow-augmenting path ==

Revision as of 11:10, 13 October 2014

Residual network

Definition: 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], where [math]\displaystyle{ 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]. 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] 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.