Изменения
Новая страница: «== Теорема о декомпозиционном барьере == {{Теорема |about= о декомпозиционном барьере |statement= Су…»
== Теорема о декомпозиционном барьере ==
{{Теорема
|about=
о декомпозиционном барьере
|statement=
Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \le E \le 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>.
|proof=
--
}}
{{Теорема
|about=
о декомпозиционном барьере
|statement=
Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \le E \le 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>.
|proof=
--
}}
