Basic flow definitions: Difference between revisions

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


Let <math>G=(V,A)</math> be a directed graph , <math>\ell(a)</math> and <math>u(a)</math> and <math>f(a)\in[\ell(a)\ldots 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> defined by  <math>u_f(v,w):=u(vw)-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>.


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

Revision as of 18:54, 12 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)\lt math\gt defined by \lt math\gt u_f(v,w):=u(vw)-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].

Flow-augmenting path

Let [math]\displaystyle{ G=(V,A)\lt /math be a directed graph , \lt math\gt \ell(a) }[/math] and [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a)\in[\ell(a)\ldots u(a)] }[/math]

Preflow

Pseudoflow

Valid distance labeling