Изменения

'''Циркуляцией''' называется поток Поток нулевой величины в [[Определение сети, потока|сети]] $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)l_i$, в которой про каждое ребро равны $e_i0$ известны , достаточно пустить поток нулевой величины: $l_i$ {{---}} минимальная пропускная способность из каждой вершины, что и $c_i$ {{---}} максимальная пропускная способностьбудет ответом. Необходимо выяснить, существует ли Поэтому далее в этой сети циркуляция, удовлетворяющая требованиям, наложенным на пропускные способностиграфе будут существовать рёбра с положительной нижней пропускной способностью.

Если рассматривать тривиальный случай==Решение==Для решения этой задачи заменим исходную сеть $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). </wikitex>

==Решение==<wikitex>Для решения этой задачи нам понадобится изменить исходную сеть $G$ в $G'$ следующим образом[[Файл:Циркуляция.png|frame|center|Рисунок 2. Сначала добавим в Слева - изначальный граф вершины $x$ {{---}} новый исток и $y$ {{---}} новый сток. Для каждого ребра заданы его нижняя и верхняя пропускные способности. Справа - граф после преобразований рёбер.]] Каждое ребро изначального графа заменяется на три новых. Если по ребру $e_i = (v_{from} \xrightarrow, v_{to})$ в исходной сети протекает поток $l_i\leqslant f_i \leqslant c_i$, то в новой сети по ребру $(s, c_i} v_{to})$ должен течь поток, равный $ добавим ребра l_i$, то есть его пропускной способности. Поток, который вытекает из $x \xrightarrowv_{0from}$ по ребру в $G$, заменяется на поток, l_iкоторый протекает по рёбрам $(v_{from} , v_{to})$ и $u_(v_{from} \xrightarrow, t)$ (поскольку сумма их пропускных способностей в полученном графе равна $c_i$). Аналогично, для вершины $v_{0to}$ суммарный входящий поток не изменился. Таким образом, любой допустимый поток по любому ребру в изначальном графе можно распределить между тремя рёбрами в полученном графе. Заметим, что в сети $G'$ все $l_i} y= 0$, то есть мы имеем обыкновенную сеть. Требовалось найти циркуляцию в исходной сети, а также сделаем значит проверить существование потока, для которого выполнено равенство <tex>\sum\limits_v f(u,v) = 0</tex> для всех вершин графа. Это равносильно существованию потока между вершинами $s$ и $t$ в ребре сети $G'$e_i, который полностью насытит рёбра, исходящие из истока. Действительно, этот поток в исходном графе насытит $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$, что удовлетворяет всем ограничениям.Значит, этот поток и есть циркуляция.  Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все рёбра из истока, то и никакой другой по величине поток этого сделать не сможет, значит, l_i = 0циркуляции нет. Для получения величин потоков вдоль каждого ребра в изначальной сети достаточно прибавить к потокам вдоль рёбер в сети $G'$соответствующие значения минимальной пропускной способности.

Проанализируем новую сеть. Каждое ребро изначального графа мы заменили на три новых. Тот факт, что по изначальному ребру $e_i$ должен течь поток $l_i ==Псевдокод==Конструктор ребра принимает следующие аргументы:* <tex>\leqslant f_i mathtt{from}</tex> {{---}} вершина начала ребра* <tex>\leqslant c_i$ означает, что в новой сети по ребру $(x, v_mathtt{to})$ должен течь поток, равный $l_i$, то есть его пропускной способности. Поток, который раньше мог вытекать из $v_</tex> {{---}} вершина конца ребра* <tex>\mathtt{minCap}</tex> {{from---}}$ по изначальному ребру, заменяется на поток, который может течь по ребрам $(v_минимальная пропускная способность ребра* <tex>\mathtt{frommaxCap}, v_</tex> {{to---}}максимальная пропускная способность ребра '''function''' circulation(<tex>V,E</tex>): <tex>G'=</tex> (<tex>V \cup s \cup t</tex>, <tex>\varnothing</tex>)$ <font color=green>// создаём новый граф с исходными вершинами и $(v_добавлением s и t {{from---}}исток и сток</font> '''for''' <tex>e : e\in E</tex> <tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, y<tex>0</tex>, <tex>e</tex>.minCap)$ <tex>h</tex> = Edge(это ясно из того<tex>e</tex>.from, что сумма их пропускных способностей в полученном графе равна $c_i$)<tex>e</tex>. То же самое верно и в вершине $v_{to}$, куда суммарный возможный входящий поток не изменился<tex>0</tex>, <tex>e</tex>.maxCap - <tex>e</tex>.minCap) <tex>k</tex> = Edge(<tex>e</tex>. Таким образомfrom, <tex>t</tex>, ясно<tex>0</tex>, что любой допустимый <tex>e</tex>.minCap) <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> '''for''' <tex>e : e\in E'</tex> '''and''' <tex>e</tex>. Заметим, что в этом самом графе все $l_i from <tex>= 0$, то есть мы имеем обыкновенную сетьs</tex> '''if''' <tex>f</tex>(<tex>e</tex>) <tex> < e</tex>.maxCap <font color=green>// если для текущего ребра flow < cap</font> '''return''' false '''return''' true

От нас требовалось найти циркуляцию в исходной сети, то есть проверить, есть ли такой поток, что <tex>\sum\limits_v f(u,v)=0<=Источники информации==* [http:/tex> выполнено для всех вершин этого графа/dl. Но это равносильно существованию потока между вершинами $x$ и $y$ в сети $G'$, который полностью насытит ребра, исходящие из истокаdropbox. Действительно, этот факт будет означать, что этот поток в исходном графе насытит $i$com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-ое ребро как минимум на $l_i$, то и является нужным требованиемIqbal.pdf M. Если этот поток существует, то мы будем иметь:* $\sum\limits_v f(u,v)=0,$ где $u \in V'Ashraf Iqbal {{---\{x,y\}, v \in V}'''Graph Theory and Algorithms'''$, то есть для всех исходных вершин;]* В $G'[http: f_i \leqslant c_i - l_i \Rightarrow 0 \leqslant f_i \leqslant c_i //e- l_i \Rightarrow l_i \leqslant f_i \leqslant c_i$, то есть все удовлетворяет ограничениямmaxx.ru/algo/flow_with_limits MAXimal :: algo :: flow with limits]то есть '''циркуляцию'''* [https://en.wikipedia. org/wiki/Circulation_problem Wikipedia — Circulation problem]

Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то [[Категория:Алгоритмы и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков по каждому ребру изначальной сети в случае, если циркуляция есть, достаточно просто прибавить к потокам в ребрах $e'_i$ величины $l_i$.структуры данных]]</wikitex>[[Категория:Задача о максимальном потоке]]