Изменения

Перейти к: навигация, поиск

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

56 байт добавлено, 09:06, 29 декабря 2010
Нет описания правки
|proof=
[[Файл:example.png|200px|thumb|right|Пример для <tex>V = 16</tex>, в который надо добавить нужное количество ребер]]
<div>Используются <tex>c_{1} = 1</tex> и <tex>c_{2} = \frac{1}{9}</tex> (<tex>V \le E \le \frac{V^2}{9}</tex>). Чтобы получить искомую сеть, строится сеть, изображенный на рисунке, после чего добавляются недостающие ребра (добавляется нужное количество ребер из <tex>A</tex> в <tex>B</tex>(а именно, <tex>E-V+1</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>(n-2[\frac{n-1}{3}]+1)</tex> ребер, что является <tex>\Omega (V)</tex>.
}}
Анонимный участник

Навигация