Изменения

Иначе говоря, [[Определение сети, потока#Определение потока|закон сохранения потока]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' вершин графа, а значит нет нужды в истоке и стоке. Когда все $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).

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

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

Требовалось найти циркуляцию в исходной сети, а значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в сети $G'$, который полностью насытит ребрарёбра, исходящие из истока. Действительно, этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, что и является необходимым требованием. Если этот поток существует, то будет выполнено:

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

* <tex>\mathtt{capminCap}</tex> {{---}} минимальная пропускная способность ребра* <tex>\mathtt{mincapmaxCap}</tex> {{---}} максимальная пропускная способность ребра

<tex>G'= {</tex> (<tex>V,\cup s\cup t</tex>,t}<tex>\varnothing</tex> ) <font color=green>// создаём новый граф с исходными вершинами и добавлением s и t {{---}} исток и сток</font>

<tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.mincapminCap) <tex>h</tex> = Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap maxCap - <tex>e</tex>.mincapminCap) <tex>k</tex> = Edge(<tex>e</tex>.from, <tex>t</tex>, <tex>0</tex>, <tex>e</tex>.minсapminCap) <tex>G' = G' \cup {</tex>(<tex>\varnothing</tex>, <tex>g,\cup h,\cup k}</tex>) maxFlow = getMaxFlow(<tex>G'</tex>) <font color=green>// наибольший поток в графе G'</font>

'''if''' <tex>f</tex>(<tex>e</tex>)<tex> < e</tex>.cap maxCap <font color=green>// если для текущего ребра flow < cap</font>