338
правок
Изменения
Нет описания правки
'''Алгоритм "поднять-в-начало" (relabel-to-front)''' основан на [[Метод проталкивания предпотока|методе проталкивание предпотока]], но из-за тщательного выбора порядка выполнения операций [[Метод проталкивания предпотока#Проталкивание (push)|проталкивания]] и [[Метод проталкивания предпотока#Подъем (relabel)|подъема]], время выполнения данного алгоритма составляет <tex>O(V^{3})</tex>, что асимптотически не хуже, чем <tex>O(V^{2}E)</tex>.
== Определения ==
<tex>G = (V, E)</tex> - [[Определение сети, потока#Определение сети|сеть]] с истоком <tex>s</tex> и стоком <tex>t</tex>, <tex>f</tex> - [[Метод проталкивания предпотока#Определения|предпоток]] в <tex>G</tex>, <tex>h</tex> - [[Метод проталкивания предпотока#Определения|функция высоты]].
{{Определение
|definition=
'''Допустимое ребро (admissible edge)''' - ребро <tex>uv</tex>, у которого <tex>c_{f}(u, v) > 0</tex> и <tex>h(u) = h(v) + 1</tex>. В противном случае <tex>uv</tex> называется '''недопустимым (inadmissible)'''.
}}
{{Определение
|definition=
'''Допустимая сеть (admissible network)''' - сеть <tex>G_{f, h} = (V, E_{f, h})</tex>, где <tex>E_{f, h}</tex> - множество допустимых ребер.
}}
== Идея ==
== Операция разгрузки (discharged) ==
== Схема алгоритма ==
== Анализ ==
== Источники ==
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785.
* [http://ru.wikipedia.org/wiki/Алгоритм_проталкивания_предпотока Алгоритм проталкивания предпотока — Википедия]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
