Basic flow definitions: Difference between revisions
| Line 3: | Line 3: | ||
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> defined by <math>u_f(v,w):=u( | 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(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>. | ||
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>. | |||
== Flow-augmenting path == | == Flow-augmenting path == | ||
Revision as of 19:04, 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) }[/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)\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]