Теорема о декомпозиционном барьере — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 2 участников)
Строка 9: Строка 9:
 
Теперь докажем саму теорему:
 
Теперь докажем саму теорему:
 
* Максимальный поток по модулю равен потоку через разрез, который разделяет <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>(\dfrac{V}{3} + 3)</tex> ребер, что является <tex>\Omega (V)</tex>.
+
* По построению сети, любой путь из <tex>s</tex> в <tex>t</tex> содержит хотя бы <tex>\left(\dfrac{V}{3} + 3\right)</tex> ребер, что является <tex>\Omega (V)</tex>.
 
}}
 
}}
  
'''Следствие:''' Алгоритмы, которые могут выписать декомпозицию потока вместе с поиском самого потока ([[Схема алгоритма Диница| Алгоритм Диница]], [[Алгоритм Эдмондса-Карпа]], [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину| Алгоритм Форда-Фалкерсона]] и подобные) не могут работать быстрее чем за <tex>O(VE)</tex>, так как декомпозиция может быть сама по себе большой.
+
'''Следствие:''' Алгоритмы, которые могут выписать декомпозицию потока вместе с поиском самого потока ([[Схема алгоритма Диница|Алгоритм Диница]], [[Алгоритм Эдмондса-Карпа]], [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину| Алгоритм Форда-Фалкерсона]] и подобные) не могут работать быстрее чем за <tex>O(VE)</tex>, так как декомпозиция может быть сама по себе большой.
  
 
==См. также==
 
==См. также==
Строка 19: Строка 19:
 
*[[Схема алгоритма Диница| Алгоритм Диница]]
 
*[[Схема алгоритма Диница| Алгоритм Диница]]
 
*[[Алгоритм поиска блокирующего потока в ациклической сети]]
 
*[[Алгоритм поиска блокирующего потока в ациклической сети]]
 
  
 
==Источники информации==
 
==Источники информации==
[https://youtu.be/PMqO0UCezqo?t=1h39m57s Андрей Станкевич: Лекториум, дополнительные главы алгоритмов, лекция 11]
+
* [https://youtu.be/PMqO0UCezqo?t=1h39m57s Андрей Станкевич: Лекториум, дополнительные главы алгоритмов, лекция 11]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о максимальном потоке ]]
 
[[Категория: Задача о максимальном потоке ]]

Текущая версия на 19:05, 4 сентября 2022

Теорема (о декомпозиционном барьере):
Существуют положительные вещественные числа [math]c_{1}[/math] и [math]c_{2}[/math], такие что для любых натуральных [math]V[/math] и [math]E[/math], удовлетворяющих неравенствам [math]c_{1}V \leqslant E \leqslant 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]V = 16[/math], в который надо добавить нужное количество ребер
Возьмем [math]c_{1} = \dfrac{11}{10}[/math] и [math]c_{2} = \dfrac{1}{9}[/math]. Константа [math]c_1[/math] выбрана таким образом, чтобы между [math]A[/math] и [math]B[/math] было [math]\Omega(E)[/math] ребер, а константа [math]c_2[/math] выбрана такой, потому что в рассматриваемой сети нельзя провести большее количество ребер. Чтобы получить искомую сеть, строится сеть, изображенная на рисунке, после чего добавляется нужное количество ребер из [math]A[/math] в [math]B[/math]. Пропускные способности ребер из [math]A[/math] в [math]B[/math] равны [math]1[/math], остальных — [math]+\infty[/math] (или просто достаточно большое число, например, [math]V^2[/math]).

Теперь докажем саму теорему:

  • Максимальный поток по модулю равен потоку через разрез, который разделяет [math]A[/math] и [math]B[/math] (т.е. пересекает все ребра с пропускной способностью [math]1[/math]). Поток по каждому пути в декомпозиции не превышает 1, а значит, этих путей не меньше, чем ребер между [math]A[/math] и [math]B[/math], а их [math]\Omega (E)[/math].
  • По построению сети, любой путь из [math]s[/math] в [math]t[/math] содержит хотя бы [math]\left(\dfrac{V}{3} + 3\right)[/math] ребер, что является [math]\Omega (V)[/math].
[math]\triangleleft[/math]

Следствие: Алгоритмы, которые могут выписать декомпозицию потока вместе с поиском самого потока (Алгоритм Диница, Алгоритм Эдмондса-Карпа, Алгоритм Форда-Фалкерсона и подобные) не могут работать быстрее чем за [math]O(VE)[/math], так как декомпозиция может быть сама по себе большой.

См. также

Источники информации