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

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

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

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

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

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

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

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

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