Теорема о декомпозиции

Теорема (о декомпозиции потока):

Любой поток [math]f[/math] транспортной сети [math]G = (V, E)[/math] можно представить в виде совокупности [math]O(E)[/math] путей из истока в сток и циклов. При этом все пути и циклы имеет положительный поток.

Доказательство:

[math]\triangleright[/math]

Пусть [math]s[/math] - исток, [math]t[/math] - сток потока [math]f[/math]. Если поток ненулевой, то из [math]s[/math] выходит хотя бы одно ребро с положительным потоком. Пойдем по этому ребру, попадем в вершину [math]v_1[/math]. Если [math]v_1[/math] совпадает с [math]s[/math], то найденный путь является путем из [math]s[/math] в [math]t[/math], иначе по закону сохранения потока для вершины [math]v_1[/math] из нее должно выходить хотя бы одно ребро с положитедьным потоком в некоторую вершину [math]v_2[/math]. Будем продолжать этот процесс до тех пор, пока [math]v_i[/math] не совпадет с [math]t[/math] (найден путь из [math]s[/math] в [math]t[/math]) либо с [math]v_j, j \lt i[/math] или [math]s[/math] (найден цикл). Данный путь (цикл) будет иметь положительный поток [math]f'[/math], равный минимальному среди потоков по всем ребрам пути (цикла). Уменьшая поток каждого ребра этого пути (цикла) на величину [math]f'[/math], получаем поток, к которому снова применим этот процесс. Заметим, что в результате однократного запуска этого процесса поток хотя бы по одному из ребер обнулится, следовательно, для полного представления потока потребуется не более [math]E[/math] таких операций.

[math]\triangleleft[/math]