Page 80 - 4496

максимальним (тому що він дорівнює величині деякого
перетину), а даний перетин є мінімальним.

Рисунок 3.11 – Граф з насиченими дугами

2 Вершина s також входить в Y, і нехай друге число її
позначки  s > 0. Тоді, мабуть, що між вершинами t й s існує
ланцюг (що складається зі спрямованих ребер - прямих і
зворотних дуг), що з'єднує ці вершини
Схематично це може бути представлено

t

Відмітимо, що дуга, що виходить із джерела, і дуга, що
входить у стік, повинні бути обов'язково прямими. Додамо  s
до c ij для прямих дуг цього ланцюга (по побудові видно, що
отримане число буде менше або дорівнює q ij) і віднімемо це  s
з c ij для зворотних дуг (може вийти негативне число, але воно
обов'язково буде за абсолютною величиною менше q ij, тому
що по побудові  s  c ij+q ij, а це означає, що зворотна дуга
міняє напрямок, стає прямою дугою і його “навантаження”
буде дорівнює модулю числа c  s  q . Тоді нові числа для
ij
ij
дуг, що входять у наш ланцюг, а також “старі” cij для всіх дуг,
що не входять у наш ланцюг, утворять новий потік з вершини
t у вершину s. Крім того, величина нового потоку в порівнянні
зі старим збільшилася на  s > 0 . Для нового потоку знову
проведемо ту ж процедуру й т.д.
Тому що щораз величина потоку збільшується,
принаймні, на 1 (пропускні здатності ребер є цілими числами),
а величина максимального потоку обмежена (величиною
мінімального перетину), те ця процедура не може тривати
нескінченно й, виходить, на якомусь кроці одержимо потік,
77