Изменения

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

Алгоритм масштабирования потока

48 байт убрано, 21:33, 15 января 2011
Суть
== Суть ==
Пусть есть граф <tex>G</tex>, <tex>\forall (u,v)\in E\colon u_{(u,v)}\in\mathbb N</tex>. Суть алгоритма в нахождении сначала путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток. Пусть <tex>U</tex> - максимальная пропускная способность. Введем параметр <tex>\Delta = 2^{\lfloor\log_2U\rfloor}</tex>. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше <tex>\Delta</tex> и увеличивать поток вдоль этих путей. В конце шага будем уменьшать <tex>\Delta</tex> в два раза, и на следующем шаге будем искать увеличивающий путь с новым <tex>\Delta</tex>. При <tex>\Delta == 1</tex> данный алгоритм идентичен [[Алоритм_Эдмондса-Карпа | алгоритму Эдмондса - Карпа]], поэтому алгоритм масштабирования корректен.
== Оценка сложности ==
65
правок

Навигация