Теорема о декомпозиционном барьере — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 8 промежуточных версий 4 участников) | |||
Строка 3: | Строка 3: | ||
о декомпозиционном барьере | о декомпозиционном барьере | ||
|statement= | |statement= | ||
− | Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \ | + | Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \leqslant E \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>. |
|proof= | |proof= | ||
− | [[Файл: | + | [[Файл:DecompositionBarierExample.png|300px|thumb|right|Пример для <tex>V = 16</tex>, в который надо добавить нужное количество ребер]] |
− | <div> | + | <div>Возьмем <tex>c_{1} = \dfrac{11}{10}</tex> и <tex>c_{2} = \dfrac{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>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>( | + | * По построению сети, любой путь из <tex>s</tex> в <tex>t</tex> содержит хотя бы <tex>\left(\dfrac{V}{3} + 3\right)</tex> ребер, что является <tex>\Omega (V)</tex>. |
}} | }} | ||
+ | |||
+ | '''Следствие:''' Алгоритмы, которые могут выписать декомпозицию потока вместе с поиском самого потока ([[Схема алгоритма Диница|Алгоритм Диница]], [[Алгоритм Эдмондса-Карпа]], [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину| Алгоритм Форда-Фалкерсона]] и подобные) не могут работать быстрее чем за <tex>O(VE)</tex>, так как декомпозиция может быть сама по себе большой. | ||
+ | |||
+ | ==См. также== | ||
+ | *[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину| Алгоритм Форда-Фалкерсона]] | ||
+ | *[[Алгоритм Эдмондса-Карпа]] | ||
+ | *[[Схема алгоритма Диница| Алгоритм Диница]] | ||
+ | *[[Алгоритм поиска блокирующего потока в ациклической сети]] | ||
+ | |||
+ | ==Источники информации== | ||
+ | * [https://youtu.be/PMqO0UCezqo?t=1h39m57s Андрей Станкевич: Лекториум, дополнительные главы алгоритмов, лекция 11] | ||
+ | |||
+ | [[Категория: Алгоритмы и структуры данных]] | ||
+ | [[Категория: Задача о максимальном потоке ]] |
Текущая версия на 19:05, 4 сентября 2022
Теорема (о декомпозиционном барьере): |
Существуют положительные вещественные числа сеть с вершинами и ребрами, такая что для любого максимального потока в , любая его остаточная декомпозиция должна содержать слагаемых (т.е. путей или циклов), причем каждый из путей (циклов) в декомпозиции должен иметь длину . и , такие что для любых натуральных и , удовлетворяющих неравенствам , существует |
Доказательство: |
Возьмем
и . Константа выбрана таким образом, чтобы между и было ребер, а константа выбрана такой, потому что в рассматриваемой сети нельзя провести большее количество ребер. Чтобы получить искомую сеть, строится сеть, изображенная на рисунке, после чего добавляется нужное количество ребер из в . Пропускные способности ребер из в равны , остальных — (или просто достаточно большое число, например, ).Теперь докажем саму теорему:
|
Следствие: Алгоритмы, которые могут выписать декомпозицию потока вместе с поиском самого потока (Алгоритм Диница, Алгоритм Эдмондса-Карпа, Алгоритм Форда-Фалкерсона и подобные) не могут работать быстрее чем за , так как декомпозиция может быть сама по себе большой.
См. также
- Алгоритм Форда-Фалкерсона
- Алгоритм Эдмондса-Карпа
- Алгоритм Диница
- Алгоритм поиска блокирующего потока в ациклической сети