Изменения

==Определение==<wikitex>{{Определение

'''Циркуляцией''' называется поток Поток нулевой величины в [[Определение сети, потока|сети]] $G(V, E)$ нулевой величиныназывается '''циркуляцией''' (англ. ''circulation problem''). Каждое ребро $e_i$ имеет $l_i$ и $c_i$ {{---}} минимальная и максимальная пропускная способности соответственно. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая пропускным способностям рёбер.

[[Файл:Циркул2.png|frame|справа|Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)]]

То есть Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока ]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' без исключения вершин графа. Фактически, а значит нет нужды в истоке и стоке.</wikitex> ==Постановка задачи==<wikitex>Рассмотрим сеть $G(V, E)$, в которой про каждое ребро $e_i$ известны величины: Когда все $l_i$ {{---}} минимальная пропускная способность и $c_i$ {{---}} максимальная пропускная способность. Необходимо выяснить, существует ли в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способности.  Рассмотрим тривиальный случай, когда все равны $l_i = 0$, то достаточно пустить поток нулевой величины ноль из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра рёбра с положительно положительной нижней пропускной способностью. </wikitex>

<wikitex>Для решения этой задачи нам понадобится изменить заменим исходную сеть $G$ в на $G'$ следующим образом. Сначала добавим в граф вершины $xs$ {{---}} новый исток и $yt$ {{---}} новый сток. Для каждого ребра $e_i = v_{from} \xrightarrow{l_i, c_i} v_{to}$ добавим ребра рёбра $x s \xrightarrow{0, l_i} v_{to}$ и $u_{from} \xrightarrow{0, l_i} yt$, а также сделаем в ребре $e_i$ изменения: $c_i = c_i - l_i, l_i = 0$(см. рисунок 2).

[[Файл:Циркул3Циркуляция.png|frame|center|Рисунок 2. Слева - изначальный граф. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований рёбер.]]

Каждое ребро изначального графа мы заменили заменяется на три новых. Если по изначальному ребру $e_i = (v_{from}, v_{to})$ должен течь в исходной сети протекает поток $l_i \leqslant f_i \leqslant c_i$, то в новой сети по ребру $(xs, v_{to})$ должен течь поток, равный $l_i$, то есть его пропускной способности. Поток, который раньше мог вытекать вытекает из $v_{from}$ по изначальному ребрув $G$, заменяется на поток, который может течь протекает по ребрам рёбрам $(v_{from}, v_{to})$ и $(v_{from}, yt)$ (это ясно из того, что поскольку сумма их пропускных способностей в полученном графе равна $c_i$). Аналогично в вершине , для вершины $v_{to}$, суммарный возможный входящий поток в которую не изменился. Таким образом, любой допустимый поток по любому ребру в изначальном графе можно распределить между тремя ребрами рёбрами в полученном графе. Заметим, что в этом самом графе сети $G'$ все $l_i = 0$, то есть мы имеем обыкновенную сеть.

Требовалось найти циркуляцию в исходной сети, то есть а значит проверитьсуществование потока, есть ли такой поток, что для которого выполнено равенство <tex>\sum\limits_v f(u,v)=0</tex> выполнено для всех вершин этого графа. Но это Это равносильно существованию потока между вершинами $xs$ и $yt$ в сети $G'$, который полностью насытит ребрарёбра, исходящие из истока. Действительно, это значит, что этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, то что и является нужным необходимым требованием. Если этот поток существует, то мы будем иметьбудет выполнено:* $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{xs,yt\}, v \in V'$, то есть для всех исходных вершин;* В $G': f_i \leqslant c_i - l_i \Rightarrow 0 \leqslant f_i \leqslant c_i - l_i \Rightarrow l_i \leqslant f_i + l_i \leqslant c_i$, то есть все что удовлетворяет всем ограничениям.то Значит, этот поток и есть '''циркуляцию'''циркуляция.

Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их рёбра из истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков по каждому ребру вдоль каждого ребра в изначальной сети в случае, если циркуляция есть, достаточно просто прибавить к потокам вдоль рёбер в ребрах сети $eG'_i$ величины $l_i$соответствующие значения минимальной пропускной способности.

G Конструктор ребра принимает следующие аргументы:* <tex>\mathtt{from}</tex> {{---}} вершина начала ребра* <tex>\mathtt{to}</ пустой граф, вершины 0 и n + 1 tex> {{--- исток и сток}} вершина конца ребра n, m; * <tex>\mathtt{minCap}</tex> {{---}} минимальная пропускная способность ребра* <tex>\mathtt{maxCap}</ вершин, ребер в исходном графеtex> {{---}} максимальная пропускная способность ребра edge '''function''' circulation(<tex>V,E</tex>): <tex>G'=</ ребро с полями tex> (from<tex>V \cup s \cup t</tex>, to, min_cap, cap<tex>\varnothing</tex>) Для i <font color= 1 to mgreen>// создаём новый граф с исходными вершинами и добавлением s и t {{---}} исток и сток</font> считать ребро edge '''for''' <tex>e : e\in E</tex> добавить в граф G ребро <tex>g</tex> = Edge(0<tex>s</tex>, edge<tex>e</tex>.to, <tex>0</tex>, edge<tex>e</tex>.min_capminCap) добавить в граф G ребро <tex>h</tex> = Edge(edge<tex>e</tex>.from, edge<tex>e</tex>.to, <tex>0</tex>, edge<tex>e</tex>.cap maxCap - edge<tex>e</tex>.min_capminCap) добавить в граф G ребро <tex>k</tex> = Edge(edge<tex>e</tex>.from, n + 1<tex>t</tex>, <tex>0</tex>, edge<tex>e</tex>.min_capminCap) <tex>G'=G' \cup </tex>(<tex>\varnothing</tex>, <tex>g \cup h \cup k</tex>) max_flow maxFlow = getMaxFlow(<tex>G'</tex>) <font color= green>// наибольший поток в графе G'</font> Для всех ребер, инцидентных истоку '''for''' <tex>e : e\in E'</tex> '''and''' <tex>e</tex>.from <tex>=s</tex> '''if''' <tex>f</tex>(<tex>e</tex>) <tex> < e</tex>.maxCap <font color=green>// если для текущего ребра flow < cap </font> '''return''' false циркуляции НЕТ'''return''' true

==Источникиинформации==

* [http://e-maxx.ru/algo/flow_with_limits e-maxxMAXimal :: algo :: flow with limits]* [https://en.wikipedia.org/wiki/Circulation_problem Wikipedia — Circulation problem] [[Категория:Алгоритмы и структуры данных]][[Категория:Задача о максимальном потоке]]