Изменения

<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$.

Каждое ребро изначального графа заменяется на три новых. Если по ребру $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'$, то есть для всех исходных вершин;