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

Наша стратегия заключается в сведении этой задачи к задаче нахождения цир- куляции с уровнями потребления, но без нижних границ. (Как вы уже видели, последняя задача может быть сведена к стандартной задаче о максимальном потоке.) Идея заключается в следующем: мы знаем, что по каждому ребру е не- обходимо передавать как минимум f, единиц потока.
Предположим, исходная циркуляция/0 определяется просто как f,,{е) = £, ./0 удовлетворяет всем ограни- чениям пропускной способности (для нижних и верхних границ), но, вероятно, не удовлетворяет всем ограничениям потребления. В частности,

Обозначим эту величину L . Если Lv = dv, то ограничение потребления для v выполняется, а если нет — нужно наложить поверх/0 циркуляцию/,, которая исправит «дисбаланс» в v. Следовательно, потребуется /"4μ)“ J,'**(v) = ti„ —i⅛. И какой пропускной способностью мы для этого располагаем? По каждому ребру уже передаются i, единиц потока, поэтому для использования доступны еще с, — f, единиц.

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

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

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

а b

Рис. 7.15. a — экземпляр задачи о циркуляции с нижними границами: числа в узлах — уровни потребности, числа у ребер — пропускные способности. Одному из ребер назначается нижняя граница 2; b — результат преобразования этого элемента в эквивалентный экземпляр задачи о циркуляции без нижних границ


(7.52) Действительная циркуляция в G существует в том и только в том случае, если существует действительная циркуляция в G'. Если все уровни потребления, пропускные способности и нижние границы в G являются целыми числами и су- ществует действительная циркуляция, то эта действительная циркуляция является целочисленной.

Доказательство. Сначала предположим, что в G' существует циркуляция/'. Определим циркуляцию/в G по формуле f{fi} = f'(е)4- f,. В этом случае∕удов- летворяет ограничениям пропускной способности в G, и

поэтому также выполняются ограничения потребления в G.

И наоборот, предположим, что в G существует циркуляция f и определим в G' циркуляцию/' по формуле f'(е) = В этом случае/' удовлетворяет огра-

ничениям пропускной способности в G' и

поэтому также выполняются ограничения потребления в G'.

7.8.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка и анализ алгоритма с нижними границами:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  3. § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ
  6. АЛГОРИТМ УДАЧИ
  7. Алгоритм исцеления:
  8. Алгоритм избавления от боли
  9. 2. Специфика и алгоритмы работы с источниками.
  10. Алгоритм обработки результатов.
  11. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  12. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  13. Я-ГРАНИЦА
  14. 2.7. Разработка анкеты
  15. Границы эго
  16. Границы
  17. Разработка Плана