Flow augmenting path

Flow augmenting path --- путь (цепь), увеличивающий поток.

For a given flow [math]\displaystyle{ f(N) }[/math] of a net [math]\displaystyle{ N }[/math], a flow augmenting path is a path [math]\displaystyle{ Q }[/math] of [math]\displaystyle{ N }[/math] such that for each [math]\displaystyle{ (v_{i},v_{i+1}) \in Q }[/math]:

(a) if [math]\displaystyle{ (v_{i},v_{i+1}) }[/math] is a forward-edge, then:

[math]\displaystyle{ \Delta_{i} = c(v_{i},v_{i+1}) - f(v_{i},v_{i+1}) \gt 0 }[/math]

and

(b) if [math]\displaystyle{ (v_{i},v_{i+1}) }[/math] is reverse-edge, then:

[math]\displaystyle{ \Delta_{i} = f(v_{i},v_{i+1}) \gt 0. }[/math]

If [math]\displaystyle{ Q }[/math] is an augmenting path, then we define [math]\displaystyle{ \Delta }[/math] as follows:

[math]\displaystyle{ \Delta = \min \Delta_{i} \gt 0. }[/math]

If an augmenting path [math]\displaystyle{ Q }[/math] exists, then we can construct a new flow [math]\displaystyle{ f'(N) }[/math] such that the value of [math]\displaystyle{ f'(N) }[/math] is equal to the value of [math]\displaystyle{ f(N) }[/math] plus [math]\displaystyle{ \Delta }[/math]. We do this by changing the flow for each [math]\displaystyle{ (v_{i},v_{i+1}) }[/math] of [math]\displaystyle{ Q }[/math] as follows:

(a) if [math]\displaystyle{ (v_{i},v_{i+1}) }[/math] is a forward-edge, then:

[math]\displaystyle{ f(v_{i},v_{i+1}) \leftarrow f(v_{i},v_{i+1}) + \Delta }[/math]

and

(b) if [math]\displaystyle{ (v_{i},v_{i+1}) }[/math] is reverse-edge, then:

[math]\displaystyle{ f(v_{i+1},v_{i}) \leftarrow f(v_{i+1},v_{i} - \Delta. }[/math]

If [math]\displaystyle{ Q }[/math] is an augmenting path, then we define [math]\displaystyle{ \Delta }[/math] as follows:

[math]\displaystyle{ \Delta = \min \Delta_{i} \gt 0. }[/math]