Алгоритмы поиска блокирующего потока: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
м (Исправлена опечатка в плагине определения)
Строка 2: Строка 2:
 
|Термин=Блокирующий поток
 
|Термин=Блокирующий поток
 
|Определение=поток $f$ в сети $G$, что в данной сети $G$ не существует увеличивающего пути (при этом в сети $G_f$ такой путь может существовать, то есть блокирующий поток не обязательно максимален)
 
|Определение=поток $f$ в сети $G$, что в данной сети $G$ не существует увеличивающего пути (при этом в сети $G_f$ такой путь может существовать, то есть блокирующий поток не обязательно максимален)
 +
}}
  
 
Довольно часто ([[алгоритм Диница]]) необходимо находить блокирующий поток в ациклической сети, ниже будут приведены несколько алгоритмов, которые это делают.
 
Довольно часто ([[алгоритм Диница]]) необходимо находить блокирующий поток в ациклической сети, ниже будут приведены несколько алгоритмов, которые это делают.

Версия 15:31, 3 февраля 2020

Определение:
Блокирующий поток —это поток $f$ в сети $G$, что в данной сети $G$ не существует увеличивающего пути (при этом в сети $G_f$ такой путь может существовать, то есть блокирующий поток не обязательно максимален)

Довольно часто (алгоритм Диница) необходимо находить блокирующий поток в ациклической сети, ниже будут приведены несколько алгоритмов, которые это делают.

Жадный алгоритм

Название говорит само за себя, будем жадно пускать поток вдоль произвольного увиличивающего пути в сети $G$. Данный алгоритм чем то похож на Алгоритм Форда-Фалкерсона, но в отличии от него мы не строим остаточную сеть, а всегда ищем увеличивающии пути в исходной сети $G$.

При пускании потока вдоль любого пути из нашей сети $G$ пропадет хотя бы одно ребро (насыщенное потоком) и при этом новых рёбер появится не может (они появляются в остаточной сети $G_f$, а не в $G$), а значит после не более $E$ итераций $t$ станет не достижимым из $s$, а значит наш поток $f$ - блокирующий. Один путь мы ищем с помощью $dfs$, за $O(E)$, следовательно время работы данного алгоритма - $O(E^2)$.

Удаляющий обход

В жадном алгоритме мы совершали много лишних действий. Будем делать то же самое, но теперь если не получилось найти увеличивающий путь пройди по ребру, то это ребро можно удалить, т.к. на любом пути содержащем это ребро точно будет насыщенное потоком.

Оценим время работы. Когда мы просматриваем ребро мы либо удалим его в дальнейшем, либо будет найден увеличивающий путь содержащий это ребро. Каждое ребро удаляется не более однгого раза, следовательно удалений $O(E)$. Как было сказано в жадном алгоритме понадобиться найти O(E) путей, а так как мы ищем простые пути их длинна $O(V)$, следовательно мы просматриваем $O(VE + E) = O(VE)$. Число совершенных действий равно числу просмотренных рёбер, следовательно время работы алгоритма $O(VE)$.

Алгоритм Малхотры — Кумара — Махешвари

напишу потом, все равно его никто и никогда не будет использовать



Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana