Циркуляция потока

<wikitex>==Определение задачи==

Определение:

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

Рисунок 1. Пример графа и циркуляции в нем (поток/пропуск.способность)

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

Рисунок 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$, то есть мы имеем обыкновенную сеть.

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

• $\sum\limits_v f(u,v)=0,$ где $u \in V'-\{s,t\}, 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$, что удовлетворяет всем ограничениям.

Значит, этот поток и есть циркуляция.

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

Псевдокод

[math]G=\varnothing[/math]                                           // пустой граф, вершины 0 и n + 1 - исток и сток, в исходном графе n вершин и m рёбер
for [math]e : e\in E[/math]                                       // ребро с полями (from, to, min_cap, cap)
    edge [math]t[/math]([math]0[/math], [math]e[/math].to, [math]0[/math], [math]e[/math].min_cap)
    edge [math]g[/math]([math]e[/math].from, [math]e[/math].to, [math]0[/math], [math]e[/math].cap [math]-e[/math].min_cap)
    edge [math]h[/math]([math]e[/math].from, [math]n+1[/math], [math]0[/math], [math]e[/math].min_cap)
    [math]G = G \cup {t,g,h}[/math]
max_flow = getmaxflow([math]G[/math])                         // наибольший поток в графе G
for [math]e : e\in E[/math] and [math]e[/math].from [math]=s[/math]
    if [math]f[/math]([math]e[/math])[math]\lt  e[/math].cap                               // если для текущего ребра flow < cap
        return false
return true

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

• M. Ashraf Iqbal —Graph Theory and Algorithms
• MAXimal :: algo :: flow with limits
• Wikipedia — Circulation problem