Изменения

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

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

11 байт добавлено, 17:05, 5 января 2017
м
Нет описания правки
Теперь докажем саму теорему:
* Максимальный поток по модулю равен потоку через разрез, который разделяет <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>.
}}

Навигация