Изменения

Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \le leqslant E \le leqslant c_{2}V^2</tex>, существует [[Определение сети, потока|сеть]] <tex>G</tex> с <tex>V</tex> вершинами и <tex>E</tex> ребрами. При этом , такая что для любого максимального потока <tex>f</tex> в <tex>G</tex>, любая его остаточная декомпозиция должна содержать <tex>\Omega (E)</tex> слагаемых (т.е. путей или циклов), причем каждый из путей (циклов) в декомпозиции должен иметь длину <tex>\Omega (V)</tex>.

[[Файл:exampleDecompositionBarierExample.png|200px300px|thumb|right|Пример для <tex>V = 16 вершин</tex>, в который надо добавить нужное количество ребер]]Используются <div>Возьмем <tex>c_{1} = 1\dfrac{11}{10}</tex> и <tex>c_{2} = \fracdfrac{1}{9}</tex>. Константа <tex>c_1</tex> выбрана таким образом, чтобы между <tex>A</tex> и <tex>B</tex> было <tex>\Omega(E)</tex> ребер, а константа <tex>c_2</tex> выбрана такой, потому что в рассматриваемой сети нельзя провести большее количество ребер. Чтобы получить искомую сеть, строится сеть, изображенный изображенная на рисунке, после чего добавляются недостающие ребра (добавляется нужное количество ребер из <tex>A</tex> в <tex>B</tex>). Пропускные способности ребер из <tex>A</tex> в <tex>B</tex> равны <tex>1</tex>, остальных — <tex>+\infty</tex> (или просто достаточно большое число, например, <tex>V^2</tex>).</div>Теперь докажем саму теорему:* Максимальный поток по модулю равен потоку через разрез, который разделяет <tex>A</tex> и <tex>B</tex> (т.е. пересекает все ребра с пропускной способностью <tex>1</tex>). Поток по каждому пути в декомпозиции не превышает 1, а значит, этих путей не меньше, чем ребер между <tex>A</tex> и <tex>B</tex>, а их <tex>\Omega (E)</tex>.* По построению сети, любой путь из <tex>s</tex> в <tex>t</tex> содержит хотя бы <tex>\left(\dfrac{V}{3} + 3\right)</tex> ребер, что является <tex>\Omega (V)</tex>.