Итерация 1

Каждой дуге (v_i, v_j) приписывают пометку [ x_ij; b_ij], где x_ij – текущий дуговой поток, b_{ij –} пропускная способность дуги. приписываем вершине S пометку [∞;-]. Из источника S максимальный поток идет в вершину 2; вершине 2 приписываем пометку [+3;S], так как q₂=min[q_s;b_s2]=min[∞;3]=3. из вершины 2 максимального пропускная способность принадлежит дуге (2,t) ведущей в сток t. Приписываем стоку пометку [2;2], так как q_t=min[q₂;b_2t] = min[3;2]=2. изменение дуговых потоков возможно на 2 единицы: x_s2=2, x_2t=2. Дуги получают пометки, показанные на рисунке 2.

[0,4] рис.2 первая итерация

[0,3] 3

[2,2] 0

[0,2] [2,3]

[0,1]

поток равен 2 ед.

[0,2] 2

[0,1]