Потоки з обмеженнями знизу

У звичайній потоковій мережі потік на ребрі обмежений лише пропускною здатністю $c(e)$ зверху та значенням 0 знизу. У цій статті ми розглянемо потокові мережі, де додатково вимагаємо, щоб потік на кожному ребрі мав певне значення, тобто обмежуємо потік знизу функцією нижніх меж $d(e)$:

$$d(e) \le f(e) \le c(e)$$

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

Це узагальнення звичайної задачі про потік, оскільки, поклавши $d(e) = 0$ для всіх ребер $e$, ми отримаємо звичайну потокову мережу. Зауважимо, що у звичайній потоковій мережі знайти допустимий потік надзвичайно просто: достатньо покласти $f(e) = 0$, і це вже допустимий потік. Проте, якщо потік на кожному ребрі має задовольняти нижню межу, то знайти допустимий потік раптом стає доволі складно.

Ми розглянемо дві задачі:

1. знайти довільний потік, який задовольняє всі обмеження;
2. знайти мінімальний потік, який задовольняє всі обмеження.

Коли підходить цей алгоритм?

• Кожне ребро має не лише верхню межу (пропускну здатність), а й нижню межу $d(e)$, яку потік зобов'язаний пропустити? (якщо нижніх меж немає, $d(e)=0$ → звичайний максимальний потік)
• Потрібно спершу знайти допустимий потік (бо за наявності нижніх меж навіть існування такого потоку нетривіальне)?
• Задача зводиться до побудови допоміжної мережі й запуску звичайного алгоритму максимального потоку (Дініц / Едмондс-Карп) на ній?

Пошук довільного потоку

Внесемо в мережу такі зміни. Ми додаємо нове джерело $s'$ і новий стік $t'$, нове ребро з джерела $s'$ до кожної іншої вершини, нове ребро з кожної вершини до стоку $t'$, а також одне ребро з $t$ до $s$. Крім того, означимо нову функцію пропускної здатності $c'$ так:

• $c'((s', v)) = \sum_{u \in V} d((u, v))$ для кожного ребра $(s', v)$.
• $c'((v, t')) = \sum_{w \in V} d((v, w))$ для кожного ребра $(v, t')$.
• $c'((u, v)) = c((u, v)) - d((u, v))$ для кожного ребра $(u, v)$ старої мережі.
• $c'((t, s)) = \infty$

Якщо в новій мережі існує насичувальний потік (потік, у якому кожне ребро, що виходить із $s'$, повністю заповнене, що рівносильно тому, що кожне ребро, яке входить у $t'$, повністю заповнене), то мережа з обмеженнями знизу має допустимий потік, і сам потік легко відновити з нової мережі. Інакше не існує потоку, який задовольняє всі умови. Оскільки насичувальний потік обов'язково є максимальним потоком, його можна знайти будь-яким алгоритмом пошуку максимального потоку, наприклад алгоритмом Едмондса-Карпа або алгоритмом проштовхування передпотоку.

Коректність цих перетворень зрозуміти важче. Можна міркувати про це так. Кожне ребро $e = (u, v)$ з $d(e) > 0$ спершу замінюється двома ребрами: одним з пропускною здатністю $d(i)$, а іншим — з $c(i) - d(i)$. Ми хочемо знайти потік, який насичує перше ребро (тобто потік уздовж цього ребра має дорівнювати його пропускній здатності). Друге ребро менш важливе — потік уздовж нього може бути будь-яким, аби лиш не перевищував його пропускної здатності. Розглянемо кожне ребро, яке має бути насиченим, і виконаємо таку операцію: проведемо ребро з нового джерела $s'$ до його кінця $v$, проведемо ребро з його початку $u$ до нового стоку $t'$, видалимо саме ребро, а зі старого стоку $t$ до старого джерела $s$ проведемо ребро нескінченної пропускної здатності. Цими діями ми моделюємо те, що це ребро насичене: з $v$ виходитиме додатково $d(e)$ потоку (ми моделюємо це новим джерелом, яке подає у $v$ потрібну кількість потоку), а $u$ також проштовхуватиме $d(e)$ додаткового потоку (але замість старого ребра цей потік піде безпосередньо в новий стік $t'$). Потік зі значенням $d(e)$, який спершу йшов уздовж шляху $s - \dots - u - v - \dots t$, тепер може піти новим шляхом $s' - v - \dots - t - s - \dots - u - t'$. Єдине, що було спрощено в означенні нової мережі, — це те, що якщо процедура створила кілька ребер між однією і тією ж парою вершин, то вони об'єднуються в одне ребро із сумарною пропускною здатністю.

Мінімальний потік

Зауважимо, що вздовж ребра $(t, s)$ (зі старого стоку до старого джерела) з пропускною здатністю $\infty$ тече весь потік відповідної старої мережі. Тобто пропускна здатність цього ребра впливає на значення потоку старої мережі. Надавши цьому ребру достатньо велику пропускну здатність (тобто $\infty$), ми робимо потік старої мережі необмеженим. Обмежуючи це ребро меншими пропускними здатностями, ми зменшуємо значення потоку. Проте, якщо обмежити це ребро надто малим значенням, то мережа не матиме насиченого розв'язку, тобто відповідний розв'язок для початкової мережі не задовольнятиме нижні межі ребер. Очевидно, тут можна скористатися бінарним пошуком, щоб знайти найменше значення, за якого всі обмеження все ще задовольняються. Це дає мінімальний потік початкової мережі.

Відеоматеріали