Задача: циркуляция с потреблением и нижние границы

Наконец, немного обобщим приведенную задачу. Во многих ситуациях требуется не только обеспечить потребление в разных узлах, но и заставить поток исполь- зовать некоторые ребра. Для этого можно установить для ребер нижние границы наряду с обычными верхними границами, определяемыми пропускными способ- ностями ребер.

Рассмотрим потоковую сеть G = (V, Е) с пропускной способностью ce и нижней границей (, для каждого ребра е. Будем считать, что 0 < £, < ce для всех е. Как и прежде, каждому узлу v также назначен уровень потребление d, который может быть как положительным, так и отрицательным. Предполагается, что все уровни потребления, пропускные способности и нижние границы являются целыми числами.

Основные величины имеют тот же смысл, что и прежде, а нижняя граница i, означает, что величина потока через е должна быть не меньше £„. Таким образом, циркуляция в потоковой сети должна удовлетворять следующим двум условиям.

(i) (Ограничения пропускной способности.) Для всех е Е выполняется ус- ловие t'

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

Еще по теме Задача: циркуляция с потреблением и нижние границы:

  1. Общие признаки нарушения циркуляции энергии в канале
  2. НИЖНИЕ ЧАКРЫ
  3. Статья 324. Склонение несовершеннолетних к потреблению одурманивающих средств
  4. Статья 316. Незаконное публичное потребление наркотических средств
  5. 2.2.1. Область поиска, получения и потребления информации
  6. Статья 315. Склонение к потреблению наркотических средств, психотропных веществ или их аналогов
  7. Я-ГРАНИЦА
  8. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  9. 11.2.1. Область реализации права на поиск, получение и потребление информации в Интернет
  10. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  11. 14.1. Особенности информационных правоотношений, возникающих при производстве, распространении и потреблении библиотечной информации
  12. Границы эго
  13. Границы
  14. 18.1. Особенности информационных правоотношений, возникающих при производстве, передаче и потреблении персональных данных
  15. § 7. Смежные права и их границы