Page 93 - 2589

називається повним, якщо кожен шлях з x в z містить по
0
крайній мірі одну насичену дугу.
Повний потік для даної транспортної мережі не являється
строго визначеною величиною і залежить від напрямку потоків в

окремих дугах. Так, на рис.4.9,а і 4.9,в дано два різних розподіли
потоку по одній і тій же транспортній мережі. Насичені дуги
позначені жирними лініями. В обох випадках потоки являються
повними, хоча їхні величини відрізняється.

Алгоритм для знаходження найбільшого потоку,
запропонований Фордом і Фалкерсоном, полягає в поступовому

збільшенні потоку  доти, поки він не стане найбільшим. При
z
цьому припускається, що пропускні можливості дуг c (u )

представляють собою цілі числа, так що потоки по дугах також
будуть виражатися цілими числами. Знаходження найбільшого
потоку відбувається в 2 етапи.

Перший: знаходження повного потоку.
Другий: знаходження найбільшого потоку.

Знаходження повного потоку. Нехай  (u ) – деякий

розподіл потоку по дугах транспортної мережі. Шукаємо шлях 

з x в z, всі дуги якого ненасичені і вважаємо:
0

 )(u 1 при u  ;
 )(u   (4.8)
  )(u при u  .
При цьому потік  зміниться до величини    1   .
z z z z
Таким шляхом виконуємо поступове збільшення  до тих пір,
z
поки він не стане повним.

Приклад 4.7: Знайдемо повний потік на транспортній мережі
(рис.4.9,а). Послідовно розглядаємо наступні шляхи, відмічаючи

насичені дуги жирними лініями:
  (x , x , x , z ),  ( )  1 — насичується дуга (x , x );
1 0 1 3 1 0 1
  (x , x , x , x , z ),  ( )  1 — насичуються дуги (x , x ) і
2 0 2 4 3 2 4 3
(x , ) z
3
  (x , x , x , z ),  ( )  2 — насичується дуга (x , x ).
3 0 2 4 3 2 4
Видно, що більше немає шляхів з x в z, які б містили
0
ненасичені дуги. Отже, отриманий потік буде повним
   ( )  ( )  ( )  4.
z 1 2 3

93