Page 92 - 2589

Рисунок 4.9 - Розподіл потоку в транспортній мережі

Пропускною здатністю перерізу А називається суму
пропускних здатностей дуг, які заходять в цей переріз:
c( A)   c( u). (4.4)

u U 
A
Оскільки для будь-якої дуги має місце (u ) c (u ), то з (4.3)
і (4.4) випливає

  c (A ). (4.5)
z
5.8.2 Задача про найбільший потік

Задача про найбільший потік в транспортній мережі
формулюється наступним чином. При заданій конфігурації

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

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

92