5 Оптимальні потоки у мережах
5.1 Поняття про мережу і основні визначення
Мережа складається із множин вершин і дуг (ребер), які з’єднують ці вузли. Якщо дуга має певну орієнтацію, то вона називається орієнтованоною або направленою. У тому випадку, коли орієнтація дуги не задана, то вона носить назву неорієнтованої. Неорієнтовану дугу називають ребром. На рис. 5.1 показана мережа із чотирьох вузлів і шести орієнтованих дуг.
Символом
будемо позначати
- тий вузол, а
- дугу, яка веде із вузла
до
.
Якщо вузли
мережі з’єднують ребра, то їх можна
позначати як символом
,
так і символом
.
Рисунок 5.1 – Мережа з орієнтованими дугами
Мережа називається
зв’язаною, якщо при будь-якому розбитті
множини вузлів на дві підмножини
і
знайдеться дуга
або
така, що
і
.
Іншими словами, мережа буде зв’язаною,
якщо є шлях між двома будь-якими вершинами.
Будемо вважати, що між двома вузлами
і
є не більше однієї орієнтованої і однієї
неорієнтованої дуги або лише одна
неорієнтована дуга (ребро). Не будемо
розглядати мережі з петлями.
Послідовність
дуг і вузлів мережі
,
,
,
,
,
…,
,
,
,
яка починається у вузлі
і закінчується вузлом
називається ланцюгом
або орієнтованим
ланцюгом. Якщо
,
то така послідовність вузлів і вершин
називається орієнтованим
циклом.
Ланцюг називається простим,
якщо він не вміщує циклів.
Приклад 5.1
● На рис 5.1
послідовність
,
,
,
,
є ланцюгом; ланцюгом є також послідовність
,
,
,
,
.
● Послідовність
,
,
,
(рис. 5.1) буде циклом.
У мережах розрізняють ланцюг і шлях. На відміну від ланцюга шляхом мережі можна рухатись і у напрямку, який протилежний орієнтації дуг. Для неорієнтованих мереж поняття ланцюга і шляху співпадають.
Приклад 5.2
● На рис 5.1 послідовність , , , , є шляхом.
Кожній дузі можна
поставити у відповідність деяке додатне
число
,
яке означає пропускну
здатність дуги (ребра).
У мережі виділяють два особливих вузла.
Один із них називається джерелом
(source)
і позначається
;
другий називається стоком
(flow)
і позначається
.
5.2 Задача про максимальний потік у мережі
Перш ніж сформулювати задачу про максимальний потік у мережі введемо спочатку поняття потоку у мережі. Потоком у мережі із джерела до стоку називається множина невід’ємних чисел (кожне із яких поставлено у відповідність деякій дузі мережі) за умови, що ці числа задовольняють наступним лінійним обмеженням:
(5.1)
,
для всіх
,
.
(5.2)
В обмеженнях (5.1) перша сума береться по дугам, які ведуть в , а друга – по вузлам, які виходять із .
Невід’ємне число
,
яке фігурує в (5.1) називається величиною
потоку. Число
називається потоком по дузі
.
Обмеження (5.1)
виражає той факт, що у кожний вузол (крім
джерела і стоку) приходить скільки
потоку скільки із нього виходить (умова
збереження) (рис. 5.2) Обмеження (5.2) означає,
що потік
по дузі обмежений пропускною здатністю
дуги
.
Рисунок 5.2 – Умова збереження потоків у вузлі
Тоді задача пошуку оптимальних потоків у мережі зводиться до максимізації цільової функції
(5.3)
при виконанні обмежень (5.1), (5.2).