Изменения

Пусть <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>s</tex> не станет нулевым. Потребуем теперь, чтобы потоки из других вершин стали нулевыми. Для этого повторим поиск циклов вышеописанным способом для всех вершин. Итак, к которому снова применим этот процесспоскольку потоки по всем ребрам равны нулю, то мы получили искомую декомпозицию потока. Заметим, что в результате однократного запуска этого процесса после поиска пути (цикла) поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более <tex>E</tex> таких операций.