§3 Програмування на сітках Деякі відомості про графи

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

Граф  це сукупність множини точок , які називаються вершинами графу, та відрізків , які називаються ребрами графу, на площині або у просторі.

Г рафи можна зобразити, наприклад, так:

Р ис. 1. Рис. 2. Рис. 3.

Рис. 4 Рис. 5. Рис.6.

Дві вершини називаються суміжними, якщо існує ребро, що з’єднує ці вершини, наприклад, на рисунку 1 всі вершини несуміжні, на рисунку 3 вершини суміжні, а вершини – ні.

Граф називається орієнтованим, якщо вказаний напрямок ребер (див. рис. 2, 4, 6) і неорієнтованим, якщо такий напрямок не вказаний (див. рис.1, 3, 5).

Граф називається зв’язним, якщо будь-які його дві вершини можна з’єднати послідовністю ребер (див. рис. 2–5).

З кожним ребром графу у задачах пов’язують деякі числові характеристики, наприклад, пропускну спроможність і таке інше. У таких випадках кажуть, що ребрам графу приписана певна вага, граф називають зваженим.

Потоки на сітках

Сітка – це зважений граф без жодної петлі та циклу, орієнтований в одному загальному напрямку від вершини , яка розглядається як вхід (джерело) графу, до вершини , яка є виходом (стоком) графу.

Припустимо, що по ребру можна пропустити деяку кількість речовини (вантаж, ресурс, інформація і т. і.)

Рис. 7.

Максимальна кількість речовини, яку може пропустити за одиницю часу ребро , називається його пропускною спроможністю і позначається . Пропускна спроможність у зворотному напрямку позначається (див. рис. 7).

В загальному випадку . Якщо вершини та не з’єднані ребром, то будемо вважати . Наприклад, для сітки на рисунку 7 пропускна спроможність .

Кількість речовини , яка протікає по ребру в одиницю часу, називається потоком по ребру. Потік з вершини V_i в вершину V_j позначимо .

Теорема. Потік по ребру не перевищує його пропускну спроможність . (3.1)

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

Для будь-якої вершини, крім джерела і стоку, кількість речовини, яка надходить у цю вершину, дорівнює кількості речовини, яка витікає з неї (умова збереження потоку) – у проміжних вершинах потоки не створюються і не зникають

. (3.2)

Звідси випливає, що загальна кількість речовини, яка витікає із джерела , збігається із загальною кількістю речовини, яка надходить у стік , тобто

. (3.3)

Лінійну функцію називають величиною потоку на сітці.

Поставимо задачу про відшукання максимального потоку на сітці, тобто такого розв’язку системи обмежень (3.1)–(3.2), який максимізує лінійну функцію (3.3).

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

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