Page 94 - 2589

Знаходження найбільшого потоку. Нехай  — повний
z
потік, а  (x , ) y — потік в дузі u  (x , ) y , направлений від

вершини x до вершини y . Процес збільшення  полягає в
z
розмітці вершин графа індексами, які вказують на шлях, на якому
можливе збільшення потоку. Попередньо всі вершини графа

повинні бути пронумеровані.
Відмічаємо x індексом 0. Якщо x — вже позначена
0 i
вершина, то позначаємо індексом i всі непозначені вершини, в
які йдуть ненасичені дуги з x , тобто вершини y , для яких
i
( x , y ) U і (x , y ) c (x , ) y , (4.9)
i i i
та індексом  всі непозначені вершини, з яких йдуть дуги в
i
вершину x , тобто вершини y , для яких
i
( y, x ) U і ( y , x )  0. (4.10)
i i
Якщо в результаті цього процесу виявиться позначеною

вершина z, то між вершинами x і z знайдеться ланцюг, всі
0
вершини якого різні і (з точністю до знаку) позначені номерами

попередніх вершин. Потік у всіх ребрах цього ланцюга можна
збільшити на одиницю в напрямку від x до z,
0
 (u )   (u ), якщо u ;
 (u )  (  u )  1, якщо u ;

і якщо проходження здійснюється у напрямку протилежному
орієнтації дуги, зменшується на одиницю, тобто;

 (u )  (  u )  1, якщо u 
В результаті цього процесу отримується новий потік по
мережі     1, величина якого зростає. Далі цей процес
z z
повторюється.
Якщо потік неможливо збільшити описаним методом, тобто

якщо стає неможливим помітити вершину z, то він є найбільшим
потоком мережі. Дійсно, нехай V — множина непозначених
вершин, які включають, звичайно, і вершину z. Отже, V це такий

переріз, який не має вихідних дуг (в іншому випадку деякі
вершини цього перерізу були б позначені від’ємними індексами),
а всі вхідні дуги насичені:

U   U ;U   ; 
V V V
 (4.11)
 )(u  (uc ) для u U  .
V 
При цьому

94