Изменения

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

То есть [[Определение сети, потока#Определение потока|закон сохранения потока ]] <tex>\sum\limits_v f(u,v)=0</tex> должен выполняться для '''всех''' без исключения вершин графа. ФактическиА значит, нет нужды в истоке и стоке.

Рассмотрим тривиальный случай, когда Когда все $l_i = $ равны $0$, то достаточно пустить поток нулевой величины ноль из каждой вершины, что и будет ответом. Поэтому далее в графе будут существовать ребра с положительно нижней пропускной способностью.

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

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

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

* В $G': f_i \leqslant c_i - l_i \Rightarrow 0 \leqslant f_i \leqslant c_i - l_i \Rightarrow l_i \leqslant f_i \leqslant c_i$, то есть все что удовлетворяет всем ограничениям.то Значит, этот поток и есть '''циркуляцию'''циркуляция.

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