6 Багатополюсні максимальні потоки

6.1 Умова реалізації

У попередньому розділі ми розглядали задачу про максимальні потоки між двома вузлами мережі. Всі інші вузли були проміжними; для них виконувалась умова збереження потоку.

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

Теорема про умови реалізації максимальних потоків. Для того щоби множина цілих невід’ємних чисел ( , ) були б множиною значень максимальних потоків у деякій мережі, необхідно і достатньо, щоби

(для будь-яких , , ) (6.1)

Із співвідношення (6.1) випливає, що

, (6.2)

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

Візьмемо три довільні вузли мережі і розглянемо величини максимальних потоків , і між ними. Виявляється, що серед цих трьох чисел у крайньому разі два повинні бути рівними. Дійсно, якщо б три числа були різні, то помістивши менше із них у ліву частину нерівності (6.1) ми б отримали протиріччя. Більш того, якщо одне із трьох чисел не рівне двом іншим, то воно повинно бути більшим, інакше ми знову отримуємо протиріччя з (6.1). Якщо нарисувати неорієнтованих дуг між всіма вузлами мережі, довжини яких пропорційні значенням максимальних потоків , то кожний трикутник буде мати по дві рівні сторони, а третя сторона буде більше або рівна іншим. Із співвідношення (6.2) випливає, що серед величин (у мережі з вузлами) існує не більше ніж різних.

6.2 Аналіз мережі

Нехай задана неорієнтована мережа з обмеженими пропускними можливостями дуг . Тоді для знаходження величин максимальних потоків достатньо розв’язати лише задач про максимальний потік, причому кожний раз задача вирішується у простішій формі ніж початкова.

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

Рисунок 6.1 – Процедура стиснення вузлів

У мережі на рис 6.1 величина максимального потоку , де , . Мінімальне січення утворюють дуги , і . Збільшення пропускних можливостей дуг, які не належать цьому мінімальному розрізу , не вплине на величину і може лише збільшити пропускну здатність інших січень, які розділюють і . Таким чином, при стисненні (рис. 6.1) вузлів , і в один вузол січення залишається мінімальним, яке розділює і . Отже, при обчисленні максимального потоку можна, наприклад, вузлу , і стиснути в один і здійснювати обчислення у мережі, яка показана на рис. 6.2.

Рисунок 6.2 – Мережа після стиснення вузлів

Тепер сформулюємо такі твердження.

Твердження 1. Нехай - мінімальне січення, яке розділює вузол і деякий вузол із , нехай . Тоді знайдеться мінімальне січення, яке розділює і і який не перетинається з січенням .

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

Твердження 3. Нехай - мінімальне січення, яке розділює задані вузли і , - довільний вузол із , - довільний вузол із . Тоді існує мінімальне січення , яке розділює вузли і яке не перетинається з січенням .

Розглянемо тепер довільну мережу , яка складається із вузлів. Будемо шукати величини максимальних потоків між заданими вузлами мережі . Ці вузлів, між якими шукається максимальний потік, будемо називати полюсами, а інші вузлів будемо називати звичайними або проміжними. Допустимо, що є деяка друга мережа , яка складається із вузлів, причому величини максимальних потоків між полюсами мережі рівні величинам максимальних потоків між вузлами мережі ^. Тоді можна знайти шукані величини максимальних потоків між вузлами, розглядаючи мережу . Виявляється, що для кожної мережі завжди існує еквівалентна їй мережа , яка є деревом ^**. Алгоритм, який ми зараз розглянемо, дає можливість за заданою мережею побудувати еквівалентне дерево . Алгоритм складається із двох кроків.

Крок 1 полягає у розв’язку задачі про максимальний потік між двома вибраними полюсами, причому зазвичай ця задача розв’язується для мережі, яка є меншою, ніж вихідна мережа , так як деяка множина вузлів стиснута в один вузол. При знаходженні максимального потоку виділяють мінімальне січення, а потім переходять до кроку 2.

Крок 2 полягає у знаходженні чергової дуги дерева з використанням мінімального січення, яке виділено на першому кроці. Дальше вибирається деяка нова пара полюсів і здійснюється стиснення деяких підмножин вузлів початкової мережі, у результаті такої операції отримуємо мережу, яка буде використана наступного разу на кроці 1. Після цього переходимо до кроку 1.

Алгоритм закінчується, коли знайдено дуг дерева.

Опишемо детальніше наведений алгоритм.

Спочатку довільним чином вибираємо два полюси і розв’язуємо для початкової мережі задачу про максимальний потік між ними. При цьому буде виділене мінімальне січення пропускною здатністю . Воно символічно буде зображатись двома «вершинами» з’єднаних дугою з пропускною здатністю (рис. 6.3). Ця дуга буде першою дерева . В одну із вершин помістимо всі вузли множини , а у другу – вузли множини . Самі ж вершини будемо позначати наступним чином: і т. д.

Рисунок 6.3 – Символічне зображення мінімального січення

Потім виберемо у побудованому дереві (рис. 6.3) будь-яку вершину, що вміщує два або більше полюсів, виділимо у ній два довільних полюси, стиснемо вузли другої вершини в один вузол і розв’яжемо про максимальний потік між двома виділеними полюсами у стисненій мережі. Наприклад, виділимо два полюси в . Тоді всі вузли із можна стиснути в один вузол. Розв’язок задачі про максимальний потік дає у стисненій мережі дає нове мінімальне січення з пропускною здатністю . Виходить дерево, яке показано на рис 6.4. Відмітимо, що вершина зв’язана дугою з вершиною , якщо множини і належать до одної і тої ж частини нового січення ; вершина з’єднується дугою з , якщо множини і належать до однієї і тої ж частини січення величини .

Рисунок 6.4 – Процес перетворення мережі

У подальшому процес розбиття вершин продовжується аналогічно. На кожному етапі розбиттю піддається деяка вершина , яка вміщує не менше двох полюсів. Якщо вершину вилучити із дерева, то воно розпадається на декілька компонент зв’язності (рис. 6.5). При розв’язку задачі про максимальний потік між двома полюсами із всі вузли, крім вузлів із , що попали в одну компоненту зв’язності, стискуються в один вузол. Після того як задача про максимальний потік розв’язана раз, буде побудовано дерево , кожна вершина Якого вміщує лише один полюс і, можливо, декілька проміжних полюсів.

Рисунок 6.5 – Мережа, вершина якої вміщує декілька полюсів

Зовсім не є очевидним, що побудоване дерево еквівалентно початковій мережі . Цей факт витікає із наступної тереми.

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

Приклад 6.1. Для мережі, яка наведена на рис. 6.6 знайти максимальні потоки між вузлами , , і . Числа поруч з дугами – їх пропускні здатності.

Рисунок 6.6 – Початкова структура мережі

Спочатку вибираємо два довільних вузла, наприклад, і , і знаходимо максимальний потік між ними. Отримуємо мінімальне січення величини13. Символічно це відтворює рис. 6.7.

Рисунок 6.7 – Мережа після стиснення вузлів

Потім знаходимо максимальний потік між і в мережі, яка показана на рис. 6.8. Ця мережа отримана шляхом стиснення вузлів , і (рис. 6.8а) в один вузол. У результаті маємо мінімальне січення величини 14 (рис. 6.8б). Відмітимо, що вершина з’єднана з вершиною , тому що вони розміщені на одній стороні у мінімальному січенні, що розділює і .

а) б)

Рисунок 6.8 – Мережа після першого етапу обчислень

Потім знаходимо максимальний потік між і у мережі, яка показана на рис. 6.8а. У результаті отримуємо мінімальне січення величини 15 як це показано на рис. 6.9.

Рисунок 6.9 – Символічне зображення мережі після другого етапу обчислень

Тепер кожна вершина в отриманому дереві вміщує тільки по одному полюсу. Таким чином, знайдені наступні величини максимальних потоків у мережі (рис. 6.9): , , . Вони дорівнюють відповідним величинам максимальних потоків у вихідній мережі (рис. 6.6).