Редактирование: Теорема о декомпозиционном барьере

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
о декомпозиционном барьере
 
о декомпозиционном барьере
 
|statement=
 
|statement=
Существуют положительные вещественные числа <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>.
+
Существуют положительные вещественные числа <tex>c_{1}</tex> и <tex>c_{2}</tex>, такие что для любых натуральных <tex>V</tex> и <tex>E</tex>, удовлетворяющих неравенствам <tex>c_{1}V \le E \le 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>, в который надо добавить нужное количество ребер]]
+
[[Файл:example.png|200px|thumb|right|Пример для <tex>V = 16</tex>, в который надо добавить нужное количество ребер]]
<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>
+
<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>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>\left(\dfrac{V}{3} + 3\right)</tex> ребер, что является <tex>\Omega (V)</tex>.
+
* По построению сети, любой путь из <tex>s</tex> в <tex>t</tex> содержит хотя бы <tex>(n-2[\frac{n-1}{3}]+1)</tex> ребер, что является <tex>\Omega (V)</tex>.
 
}}
 
}}
 
'''Следствие:''' Алгоритмы, которые могут выписать декомпозицию потока вместе с поиском самого потока ([[Схема алгоритма Диница|Алгоритм Диница]], [[Алгоритм Эдмондса-Карпа]], [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину| Алгоритм Форда-Фалкерсона]] и подобные) не могут работать быстрее чем за <tex>O(VE)</tex>, так как декомпозиция может быть сама по себе большой.
 
 
==См. также==
 
*[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину| Алгоритм Форда-Фалкерсона]]
 
*[[Алгоритм Эдмондса-Карпа]]
 
*[[Схема алгоритма Диница| Алгоритм Диница]]
 
*[[Алгоритм поиска блокирующего потока в ациклической сети]]
 
 
==Источники информации==
 
* [https://youtu.be/PMqO0UCezqo?t=1h39m57s Андрей Станкевич: Лекториум, дополнительные главы алгоритмов, лекция 11]
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о максимальном потоке ]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: