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

Материал из Викиконспекты
Версия от 15:50, 19 декабря 2010; 192.168.0.2 (обсуждение) (Теорема о декомпозиционном барьере)
Перейти к: навигация, поиск
Теорема (о декомпозиционном барьере):
Существуют положительные вещественные числа [math]c_{1}[/math] и [math]c_{2}[/math], такие что для любых натуральных [math]V[/math] и [math]E[/math], удовлетворяющих неравенствам [math]c_{1}V \le E \le c_{2}V^2[/math], существует сеть [math]G[/math] с [math]V[/math] вершинами и [math]E[/math] ребрами. При этом для любого максимального потока [math]f[/math] в [math]G[/math], любая его остаточная декомпозиция должна содержать [math]\Omega (E)[/math] слагаемых (т.е. путей или циклов), причем каждый из путей (циклов) в декомпозиции должен иметь длину [math]\Omega (V)[/math].
Доказательство:
[math]\triangleright[/math]
--
[math]\triangleleft[/math]