Изменения

о декомпозиции потока

Любой поток Пусть <tex>G = (V, E)</tex> — [[Определение сети, потока#flow_network|транспортная сеть]], <tex>f</tex> — [[Определение сети, потока#flow|транспортной сетипоток]] в <tex>G = (V, E)</tex>. Тогда <tex>|f|</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов. При этом все пути : <tex>|f| = \sum\limits_{i=1}^{}c_{i}\cdot f(p_{i}) + \sum\limits_{j=1}^{}d_{j}\cdot f(k_{j})</tex>, где <tex>p_{i}</tex> — путь из <tex>s</tex> в <tex>t</tex>, <tex>k_{j}</tex> — цикл, <tex>c_{i}</tex> и циклы имеет положительный поток<tex>d_{j}</tex> — константы.

Пусть <tex>s</tex> - — исток, <tex>t</tex> - — сток потока сети <tex>fG</tex>. Пусть из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>t</tex>, то найденный путь является путем из <tex>s</tex> в <tex>t</tex>, иначе по закону сохранения потока для вершины <tex>v_1</tex> из нее неё должно выходить хотя бы одно ребро с положительным потоком в некоторую вершину <tex>v_2</tex>. Будем продолжать этот процесс до тех пор, пока <tex>v_i</tex> не совпадет с <tex>t</tex> (найден путь <tex>p_{i}</tex> из <tex>s</tex> в <tex>t</tex>) либо с одной из ранее посещенных вершин (найден цикл <tex>v_j, k_{j < i</tex> или <tex>s}</tex> (найден цикл). Данный путь (цикл) будет иметь положительный поток <tex>f'</tex>(<tex>p_{i}</tex>) или <tex>f</tex>(<tex>k_{j}</tex>), равный минимальному среди потоков по всем ребрам рёбрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f'</tex>(<tex>p_{i}</tex>) или <tex>f</tex>(<tex>k_{j}</tex>), получаем новый поток. Будем продолжать описанный алгоритм до тех пор, пока поток из <tex>s</tex> не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для других вершин. Итак, поскольку потоки по всем ребрам рёбрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что после поиска одного пути (цикла) поток хотя бы по одному из ребер рёбер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.

Рассмотрим алгоритм, описанный в доказательстве теоремы. Построение декомпозиции потока можно записать с помощью псевдокода(на вход подается сеть <tex>G = (V, E)</tex>): 

'''function'''simpleDecomposition(<tex>s</tex>)''': <tex> Q \leftarrow = \varnothing </tex> <font color=green>// множество пройденных рёбер</font> <tex> P \leftarrow = \varnothing </tex> <font color=green>// множество посещённых вершин</font> <tex>v \leftarrow = s</tex> '''while''' <tex> v \neq notin P </tex> '''if''' <tex> v = t </tex> и '''break''' edge <tex> v e = \notin Q varnothing</tex> находим '''for''' <tex> u : (vuv,u): \in E</tex> '''if''' <tex> f(vuv,u)>0 </tex> <tex>e = (v,u)</tex> '''break''' '''if''' <tex>e = \neg \exists (vu): f(vu)>0 varnothing</tex> '''return''' NULL<tex>\varnothing</tex> <tex> Q \leftarrow Q \cup </tex>.push_back(vu) <tex>e</tex>) <tex> P \leftarrow = P \cup \{v \}</tex> <tex> v \leftarrow = u </tex> '''if''' <tex>v \in P </tex> <font color=green>// нашли цикл, удаляем из <tex>Q</tex> все ребрарёбра, найденные до того, как <tex>v</tex> была включена в <tex>P</tex></font> '''while''' (<tex>Q</tex>.begin.from <tex>\neq</tex> <tex>v</tex>) <tex>Q</tex>.pop_front() <tex>f(Q) \leftarrow = f(Q) </tex> - <tex>\min\limits_{uv (u,v) \in Q}f(uvu,v) </tex> '''return''' <tex>(f, Q)</tex>

'''function'''fullDecomposition(): <tex> d = \varnothing </tex> <font color=green>// собственно, декомпозиция графа: совокупность подмножеств, которые являются путями/циклами, и их поток</font> <tex>p = </tex> simpleDecomposition(<tex>s</tex>) <font color=green>// один из путей/циклов в графе и его поток</font> '''while'''(<tex>p \neq \varnothing</tex>) <tex> d = d \leftarrow \emptyset cup p </tex> <tex>p = </tex> simpleDecomposition(<tex>s</tex>) '''while for'''<tex> u \in V </tex> <tex> p = </tex> simpleDecomposition(s<tex>u</tex>) '''while''' (<tex> p \neq \varnothing</tex> NULL) <tex> d \leftarrow = d \cup \{p \} </tex> <tex>p = </tex> simpleDecomposition(<tex>u</tex>) '''return''' <tex>d</tex>

Действительно, каждый путь (цикл) содержит не более <tex>V</tex> вершин, следовательно , поиск пути (цикла) работает за <tex>O(V)</tex>. Т. к. декомпозиция потока содержит <tex>O(E)</tex> путей, то всего в ходе алгоритма при рассмотрении всех вершин будет осуществлено <tex>O(E)</tex> поисков путей (циклов) (в остальных случаях в силу отсутствия потока через вершину поиск пути вызываться не будет). Итого суммарное время работы составит <tex>O(VE)</tex>.}}

* ''КорменRavindra Ahuja, Томас Х., Лейзерсон, Чарльз И.Thomas Magnanti, Ривест, Рональд Л., Штайн КлиффордJames Orlin'' — '''Алгоритмы: построение и анализNetwork flows'''— Prentice-Hall, 2-е изданиеInc. Пер. с англ. — М.:Издательский дом "Вильямс"Upper Saddle River, New Jersey, 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус1993.)

[[Категория: Задача о максимальном потоке]]