Page 17 - 4517

ЛАБОРАТОРНА РОБОТА № 4
ПРИКЛАД ЗНАХОДЖЕННЯ МАКСИМАЛЬНОГО
ПОТОКУ В МЕРЕЖІ
(4 год.)

Мета: одержання практичних навичок знаходження
максимального потоку в мережі.

Теоретичні відомості

Мережа складається із множин вершин і дуг (ребер), які
з’єднують ці вузли. Якщо дуга має певну орієнтацію, то вона
називається орієнтованоною або направленою. У тому випадку,
коли орієнтація дуги не задана, то вона носить назву
неорієнтованої. Неорієнтовану дугу називають ребром. На рис.
4.1 показана мережа із чотирьох вузлів і шести орієнтованих
дуг.
Символом N будемо позначати i - тий вузол, а A - дугу,
i ij
яка веде із вузла N до N . Якщо вузли мережі з’єднують ребра,
i j
то їх можна позначати як символом A , так і символом A .
ij ji

Рисунок 4.1 – Мережа з орієнтованими дугами

15