Разработка и анализ алгоритма с нижними границами

Наша стратегия заключается в сведении этой задачи к задаче нахождения циркуляции с уровнями потребления, но без нижних границ. (Как вы уже видели, последняя задача может быть сведена к стандартной задаче о максимальном потоке.)

Идея заключается в следующем: мы знаем, что по каждому ребру e необходимо передавать как минимум   единиц  потока.

Предположим, исходная циркуляция f0 определяется просто как . f0 удовлетворяет всем ограничениям пропускной способности (для нижних и верхних границ), но, вероятно, не удовлетворяет всем ограничениям потребления.

В частности, Обозначим эту величину Lv. Если Lv = dv, то ограничение потребления для v выполняется, а если нет — нужно наложить поверх f0 циркуляцию f1, которая исправит «дисбаланс» в v.

И какой пропускной способностью мы для этого располагаем? По каждому ребру уже передаются  единиц потока, поэтому для использования доступны еще  единиц.

Эти соображения заложены в основу следующего построения. Пусть граф G’ состоит из тех же узлов и ребер с пропускными способностями и уровнями потребления, но без нижних границ. Пропускная способность ребра e будет равна. Уровень потребления узла v будет равен dv−Lv.

Например, возьмем экземпляр графа на рис. 7.15(a). Перед вами тот же экземпляр, который был показан на рис. 7.13, но на этот раз одному из ребер назначена нижняя граница 2.

В части b эта нижняя граница устраняется, что приводит к снижению верхней границы для ребра и изменению потребления на двух концах ребра. В процессе становится ясно, что действительной циркуляции не существует, так как после применения этой конструкции появляется узел с уровнем потребления –5 и только 4 единицами пропускной способности на выходящих ребрах.

Утверждается, что наша общая конструкция создает эквивалентный экземпляр задачи с уровнями потребности, но без нижних границ; к этой задаче можно применить общий алгоритм.