Нахождение потока в графе, в котором у каждого ребра указано минимальное и максимальное значение потока

Пусть дан граф G, в котором для каждого ребра помимо пропускной способности (максимального значения потока вдоль этого ребра) указано и минимальное значение потока, который должен проходить по этому ребру.

Здесь мы рассмотрим две задачи: 1) требуется найти произвольный поток, удовлетворяющий всем ограничениям, и 2) требуется найти минимальный поток, удовлетворяющий всем ограничениям.

Решение задачи 1

Обозначим через L_i минимальную величину потока, которая может проходить по i-му ребру, а через R_i - его максимальная величина.

Произведём в графе следующие изменения. Добавим новый исток S' и сток T'. Рассмотрим все рёбра, у которых L_i отлично от нуля. Пусть i - номер такого ребра. Пусть концы этого ребра (ориентированного) - это вершины A_i и B_i. Добавим ребро (S', B_i), у которого L = 0, R = L_i, добавим ребро (A_i, T'), у которого L = 0, R = L_i, а у самого i-го ребра положим R_i = R_i - L_i, а L_i = 0. Наконец, добавим в граф ребро из T в S (старых стока и истока), у которого L = 0, R = INF.

После выполнения этих преобразований все рёбра графа будут иметь L_i = 0, т.е. мы свели эту задачу к обычной задаче нахождения максимального потока (но уже в модифицированном графе с новыми истоком и стоком) (чтобы понять, почему именно максимального - читайте нижеследующее объяснение).

Корректность этих преобразований понять сложнее. Неформальное объяснение такое. Каждое ребро, у которого L_i отлично от нуля, мы заменяем на два ребра: одно с пропускной способностью L_i, а другое - с R_i-L_i. Нам требуется найти поток, который бы обязательно насытил первое ребро из этой пары (т.е. поток вдоль этого ребра должен быть равен L_i); второе ребро нас волнует меньше - поток вдоль него может быть любым, лишь бы он не превосходил его пропускной способности. Итак, нам требуется найти такой поток, который бы обязательно насытил некоторое множество рёбер. Рассмотрим каждое такое ребро, и выполним такую операцию: подведём к его концу ребро из нового истока S', подведём ребро из его начала к стоку T', само ребро удалим, а из старого стока T к старому истоку S проведём ребро бесконечной пропускной способности. Этими действиями мы проимитируем тот факт, что это ребро насыщено - из ребра будет вытекать L_i единиц потока (мы имитируем это с помощью нового истока, который подаёт на конец ребра нужное количество потока), а втекать в него будет опять же L_i единиц потока (но вместо ребра этот поток попадёт в новый сток). Поток из нового истока протекает по одной части графа, дотекает до старого стока T, из него протекает в старый исток S, затем течёт по другой части графа, и наконец приходит к началу нашего ребра, и попадает в новый сток T'. Т.е., если мы найдём в этом модифицированном графе максимальный поток (и в сток попадёт нужное количество потока, т.е. сумма всех значений L_i - иначе величина потока будет меньше, и ответа попросту не существует), то мы одновременно найдём поток в исходном графе, который будет удовлетворять все ограничениям минимума, и, разумеется, всем ограничениям максимума.

Решение задачи 2

Заметим, что по ребру из старого стока в старый исток с пропускной способностью INF протекает весь старый поток, т.е. пропускная способность этого ребра влияет на величину старого потока. При достаточно большой величине пропускной способности этого ребра (т.е. INF) старый поток ничем не ограничен. Если мы будем уменьшать пропускную способность, то и, начиная с некоторого момента, будет уменьшаться и величина старого потока. Но при слишком малом значении величина потока станет недостаточной, чтобы обеспечить выполнение ограничений (на минимальное значение потока вдоль рёбер). Очевидно, здесь можно применить бинарный поиск по значению INF, и найти такое её наименьшее значение, при котором все ограничения ещё будут удовлетворяться, но старый поток будет иметь минимальное значение.