76
правок
Изменения
Теорема, доказательство
{{Теорема
|about=
о декомпозиции потока
|statement=
Любой поток <tex>f</tex> [[Определение сети, потока|транспортной сети]] <tex>G = (V, E)</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов. При этом все пути и циклы имеет положительный поток.
|proof=
Пусть <tex>s</tex> - исток, <tex>t</tex> - сток потока <tex>f</tex>. Если поток ненулевой, то из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>s</tex>, то найденный путь является путем из <tex>s</tex> в <tex>t</tex>, иначе по закону сохранения потока для вершины <tex>v_1</tex> из нее должно выходить хотя бы одно ребро с положитедьным потоком в некоторую вершину <tex>v_2</tex>. Будем продолжать этот процесс до тех пор, пока <tex>v_i</tex> не совпадет с <tex>t</tex> (найден путь из <tex>s</tex> в <tex>t</tex>) либо с <tex>v_j, j < i</tex> или <tex>s</tex> (найден цикл). Данный путь (цикл) будет иметь положительный поток <tex>f'</tex>, равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f'</tex>, получаем поток, к которому снова применим этот процесс. Заметим, что в результате однократного запуска этого процесса поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.
}}
|about=
о декомпозиции потока
|statement=
Любой поток <tex>f</tex> [[Определение сети, потока|транспортной сети]] <tex>G = (V, E)</tex> можно представить в виде совокупности <tex>O(E)</tex> путей из истока в сток и циклов. При этом все пути и циклы имеет положительный поток.
|proof=
Пусть <tex>s</tex> - исток, <tex>t</tex> - сток потока <tex>f</tex>. Если поток ненулевой, то из <tex>s</tex> выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину <tex>v_1</tex>. Если <tex>v_1</tex> совпадает с <tex>s</tex>, то найденный путь является путем из <tex>s</tex> в <tex>t</tex>, иначе по закону сохранения потока для вершины <tex>v_1</tex> из нее должно выходить хотя бы одно ребро с положитедьным потоком в некоторую вершину <tex>v_2</tex>. Будем продолжать этот процесс до тех пор, пока <tex>v_i</tex> не совпадет с <tex>t</tex> (найден путь из <tex>s</tex> в <tex>t</tex>) либо с <tex>v_j, j < i</tex> или <tex>s</tex> (найден цикл). Данный путь (цикл) будет иметь положительный поток <tex>f'</tex>, равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину <tex>f'</tex>, получаем поток, к которому снова применим этот процесс. Заметим, что в результате однократного запуска этого процесса поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.
}}
