Flow augmenting path

Материал из WikiGrapp
Версия от 16:35, 27 апреля 2011; Glk (обсуждение | вклад) (Новая страница: «'''Flow augmenting path''' --- путь (цепь), увеличивающий поток. For a given flow <math>f(N)</math> of a net <math>N</math>, a '''flow au…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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]