7.3 Багатополюсні ланцюги максимальної пропускної здатності
Нехай задана мережа з пропускними можливостями дуг . Назвемо пропускною здатністю шляху із вузла до вузла величину найменшу із пропускних можливостей дуг цього шляху. Шлях із в будемо називати шляхом з максимальною пропускною
здатністю, якщо його пропускна здатність не менше, ніж пропускна здатність будь-якого іншого шляху із в . Тернарна операція, яка аналогічна операції (7.2), може бути використана для знаходження шляхів з максимальною пропускною здатністю між всіма парами вузлів мережі. У цьому випадну тернарна операція має наступний вигляд:
(7.4)
для всіх
,
і здійснюється послідовно для
.
Разом з обчисленням
матриці
обчислюється довідкова матриця розміру
,
яка аналогічна довідковій матриці, що
розглянута раніше. Елемент
цієї матриці спочатку набуває значення
,
а потім
7.4 Потоки мінімальної вартості
Будемо розглядати
мережу, в якій кожній дузі
поставлена у відповідність дугова
вартість
,
тобто вартість доставки одиниці потоку
із вузла
в
по дузі
.
Необхідно знайти потік із джерела в
стік, який має задану величину і набуває
мінімальної вартості.
Формально задача зводиться до наступного:
мінімізувати
(7.5)
за умов
(7.6)
,
.
(7.7)
При цьому мається на увазі, що величина не перевищує величину максимального потоку в , у противному разі задача не має розв’язку.
Розглянемо два алгоритми розв’язку задачі (7.5) – (7.7). Перший з них, який запропонований Басакером і Гоуеном, має наступний вигляд:
Крок 0. Покласти всі дугові потоки і величину потоку рівним нулеві.
Крок
1. Визначити
модифіковані дугові вартості
,
що залежать від величини уже знайденого
потоку, наступним чином:
Крок 2. Знайти найкоротший ланцюг (тобто ланцюг мінімальної вартості) із в , використовуючи дугові вартості , що знайдені на кроці 1. Потім пропускати по цьому ланцюгу потік до тих пір поки він не перестане бути найкоротшим ланцюгом. Отримати величину нового потоку, прибавивши до величини старого величину потоку, що протікає по ланцюгу, який розглядається.
Другий алгоритм, який запропонований Клейном, формулюється наступним чином:
Крок 1. Знайти будь-який допустимий потік величини із джерела у стік . Це можна зробити методом підбору або за допомогою вирішення задачі про максимальний потік, в якій обчислення необхідно проводити до досягнення максимальним потоком величини .
Крок2. Визначити модифіковані вартості наступним чином:
Крок3. Використовуючи
величини
,
знайти у мережі цикл від’ємної вартості
(такі цикли
скорочено називатимемо негативними) .
Якщо його не існує, то знайдений потік
буде оптимальним. Якщо такий цикл
знайдеться, то добавити у мережу потік
по ньому величини
,
де
.
Мінімум береться по дугам негативного
циклу. Якщо у мережі є декілька негативних
циклів, то добавляється потік по кожному
із них. Перейти до кроку 2.
Розглянуті алгоритми дають змогу знайти потік величини , якщо число не перевершує величини максимального потоку. Зовсім не очевидно, що ці алгоритми дають можливість знайти оптимальний потік. Наступна теорема формує необхідні і достатні умови існування такого оптимального потоку. Вона розглядається як основна в теорії потоків мінімальної вартості.
Теорема 7.1. Потік величини оптимальний тоді і тільки тоді, коли у мережі з модифікованими дуговими вартостями не існує негативних циклів.
Приклад 7.3. Нехай
у мережі, яка подана на рис. 7.3, перше
число біля кожної дуги вказує на її
пропускну здатність
,
а друге число – її дугова вартість
.
Всі дуги не орієнтовані. Необхідно
знайти потік величини 2 (
)
мінімальної вартості.
Перший етап обчислень
Крок 1. Вважаємо, що всі .
Крок 2 .Знаходимо
найкоротший ланцюг із
в
,
використовуючи як довжини дуг
.
Отримаємо ланцюг
,
,
,
,
,
,
або
,
,
,
,
,
,
.
Вибравши перший ланцюг, отримаємо (до
нульових значень
додаємо одиницю):
.
Переходимо до другого етапу обчислень,
починаючи з кроку 1.
Рисунок 7.3 – Мережа з вказаними пропускними можливостями дуг і дуговими вартостями
Другий етап обчислень
Крок 1. Обчислюємо модифіковані вартості наступним чином:
,
так як
,
,
,
так як
,
,
,
так як
,
,
Всі інші .
Крок 2 .
Знаходимо найкоротший ланцюг із
в
,
використовуючи як довжини нові
модифіковані вартості
(рис. 7.4). Отримуємо ланцюг
,
,
,
,
загальною вартістю 1+2+(-2)+2+2=5. Пропустивши
одиницю потоку по цьому ланцюгу, отримуємо
у кінцевому підсумку потік, який показаний
на рис. 7.5.
Рисунок 7.4 – Мережа з проставленими модифікованими вартостями
Відмітимо, що
подальше збільшення величини потоку
обмежене значеннями пропускних
можливостей дуг
і
,
для яких
.
Рисунок 7.5 – Мережа мінімальної вартості
Перевіряємо умови:
для вузла
.
Оскільки
і
,
то
;
для вузла
.
(
і
).
Таким чином, отримана мережа є мережею оптимальної вартості, для якої виконуються обмеження на баланс потоків і обмеження на величину потоків у кожній із дуг.
Доповнення – це множина вершин мережі , які належать , але не належать .
Дві мережі, які мають рівні величини максимальних потоків між деякою множиною вузлів, називаються потоково-еквівалентними або просто еквівалентними відносно цієї множини вузлів.
** Дерево – це мережа (граф) без циклів.