Page 18 - 4517

Мережа називається зв’язаною, якщо при будь-якому
розбитті множини вузлів на дві підмножини X і X знайдеться
дуга A або A така, що N  X і N  X . Іншими словами,
ij ji i j
мережа буде зв’язаною, якщо є шлях між двома будь-якими
вершинами. Будемо вважати, що між двома вузлами N і N є
i j
не більше однієї орієнтованої і однієї неорієнтованої дуги або
лише одна неорієнтована дуга (ребро). Не будемо розглядати
мережі з петлями.
Послідовність дуг і вузлів мережі N , A , N , , N , …,
1 12 2 3
N , A , N , яка починається у вузлі N і закінчується
k 1  k 1,k k 1
вузлом N називається ланцюгом або орієнтованим ланцюгом.
k
Якщо N  N , то така послідовність вузлів і вершин
1 k
називається орієнтованим циклом. Ланцюг називається
простим, якщо він не вміщує циклів.
Теоретичні відомості викладені в конспекті лекцій [1] на
сторінках 84 – 113.

Завдання до лабораторної роботи

Для мережі, яка показана на рис. А.1 (додаток А), знайти
максимальний потік.
Приклад вигляду мережі для індивідуального
варіанта № 33 представлено рисунку 4.2.

Індивідуальні завдання

Індивідуальне завдання представлене в додатку А.

16