<wikitex>==Определениезадачи==
{{Определение
|definition=
'''Циркуляцией''' называется поток Поток нулевой величины в [[Определение сети, потока|сети]] $G(V, E)$ нулевой величины называется '''циркуляцией''' (смангл. рисунок 1''circulation problem''). Каждое ребро $e_i$ имеет $l_i$ и $c_i$ {{---}} минимальная и максимальная пропускная способности соответственно. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая пропускным способностям рёбер.
}}
[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]
То есть Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.
</wikitex>
==Постановка задачи==
<wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: $l_i$ {{---}} минимальная пропускная способность и $c_i$ {{---}} максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности.
Когда все $l_i$ равны $0$, достаточно пустить поток нулевой величины из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.
</wikitex>
==Решение==
<wikitex>Для решения этой задачи заменим исходную сеть $G$ на $G'$ следующим образом. Сначала добавим в граф вершины $s$ {{---}} исток и $t$ {{---}} сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим ребра $s \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} t$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$ (см. рисунок 2).
'''return''' true
==Источникиинформации==
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']
* [http://e-maxx.ru/algo/flow_with_limits e-maxxMAXimal :: algo :: flow with limits]* [https://en.wikipedia.org/wiki/Circulation_problem Wikipedia — Circulation problem]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о максимальном потоке]]
