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

Одна из упрощающих особенностей исходной формулировки задачи о максималь- ном потоке заключалась в том, что графе содержал только один источник s и один сток t. Теперь предположим, что в графе присутствует множество S источников, генерирующих поток, и множество T стоков, поглощающих поток.
Как и прежде, каждое ребро обладает целочисленной пропускной способностью.

С несколькими источниками и стоками не совсем понятно, как решить, какому из источников или стоков следует отдать предпочтение в задаче максимизации. Вместо того чтобы максимизировать величину потока, мы рассмотрим ситуацию, в которой источники имеют фиксированную величину поставки, а стоки — фик- сированную величину потребления, а наша цель заключается в передаче потока
от узлов со свободной поставкой к узлам с заданным потреблением. Представьте, например, что сеть представление систему дорог или железнодорожных линий, которая используется для поставки товаров с фабрик (поставка) в торговые точки (потребление). В такой постановке задачи нас будет интересовать не максимизация конкретной величины, а удовлетворение всего спроса с использованием доступной поставки.

Следовательно, мы имеем потоковую сеть G = (V, E) с пропускными способ- ностями ребер. С каждым узлом v V связывается уровень потребления dv. Если

dv > 0, значит, узел v потребляет dv единиц потока; узел выполняет функции стока и желает получать на dv единиц больше потока, чем отправлять далее. Если dv < 0, значит v имеет уровень потребления -dv; он является источником, и хочет отправ- лять на -dv единиц потока больше, чем получает. Если dv = 0, то узел v не является ни источником, ни стоком. Будем считать, что все пропускные способности и уров- ни потребления являются целыми числами.


Обозначим S множество всех узлов с отрицательным потреблением, и T — мно- жество всех узлов с положительным потреблением. Хотя узел v в S хочет переда- вать больше потока, чем получает, он может иметь поток по входящим ребрам; он будет компенсироваться потоком из v по выходящим ребрам. Сказанное относится (в противоположном направлении) и к множеству T.

В этой ситуации циркуляцией с потреблением {dv} называется функцияf которая связывает с каждым ребром неотрицательное вещественное число и удовлетворяет следующим двум условиям:

♦ (i) (Ограничения пропускной способности) Для всех e E выполняется усло- вие 0 < f (e) < c

♦ (ii) (Ограничения сохранения потока) Для каждого узла v V выполняется условие v,fn(v) -f°ut(v) = dv.

Сейчас вместо задачи максимизации нас интересует задача существования: требуется узнать, существует ли действительная циркуляция (то есть циркуляция, удовлетворяющая условиям (i) и (ii)).

Для примера рассмотрим экземпляр задачи на рис. 7.13, а. На этой схеме два узла являются источниками (уровни потребления -3 и -3); два узла являются стоками, с уровнями потребления 2 и 4. Величины потока на схеме образуют действительную циркуляцию, так как все уровни потребления удовлетворяются в соответствии с пропускными способностями.

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

(7.49) Если существует действительная циркуляция с потреблением {

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

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

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