Page 91 - 2589

  (u )    (u )  ; 0 x  x 0 ;x  . z (4.2)
 
u U x u U x
Функцію (u ) можна розглядати як кількість речовини, що

протікає (у одиницю часу) по дузі u  (х , ) у ) від х до у. Згідно з
умовою (4.1) ця кількість речовини не може перевищувати
пропускний здатності дуги (uс ). Згідно умові (4.2) в кожній

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

що потік, вихідний з вхідної вершини x , в точності рівний
0
потоку, що входить у вихідну вершину z :
 ( u )  ( u (,) u )  z

u U xа u U  z
Величина (z ) називають величиною потоку транспортної

мережі. На рис.4.9 наведений приклад транспортної мережі.
Цифри в розривах дуг означають пропускну спроможність дуги.
Стрілки вказують напрям потоків, а цифри біля стрілок -
величину потоку. До аналізу транспортних мереж зводяться

багато завдань, що виникають при плануванні постачань,
розподілі товарів між споживачами і т. п.
Для дослідження розподілу потоку по транспортній мережі

зручно ввести поняття перерізу транспортної мережі. Нехай
A  X - деяка множина, яка задовольняє умовам :
x  A , z  . A
0


Через U і через U позначимо відповідно множини дуг, що
A A

заходять в А і виходять з А. Повну сукупність дуг U U  U
A A A
назвемо перерізом транспортної мережі. Приклад перерізу А
наведений на рис.4.9,а.
Оскільки кожна частинка речовини, яка рухається від x до
0
z, обов’язково пройде по якій-небудь дузі перерізу, то загальний
потік через переріз буде рівним величині потоку транспортної

мережі, тобто для будь-якого перерізу А має місце
співвідношення
 z    u)(    u)( . (4.3)
 
u U A u U A

91