Изменения

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

Алгоритм "поднять-в-начало"

56 байт добавлено, 22:56, 4 января 2016
Нет описания правки
'''Алгоритм "поднять-в-начало" ''' (англ. ''relabel-to-front)''' ) основан на [[Метод проталкивания предпотока|методе проталкивание предпотока]], но из-за тщательного выбора порядка выполнения операций [[Метод проталкивания предпотока#Проталкивание (push)|проталкивания]] и [[Метод проталкивания предпотока#Подъем (relabel)|подъема]], время выполнения данного алгоритма составляет <tex>O(V^{3})</tex>, что асимптотически не хуже, чем <tex>O(V^{2}E)</tex>.
== Допустимые ребра ==
{{Определение
|definition=
'''Допустимое ребро ''' (англ. ''admissible edge)''' ) {{---}} ребро <tex>(u, v)</tex>, у которого <tex>c_{f}(u, v) > 0</tex> и <tex>h[u] = h[v] + 1</tex>. В противном случае <tex>(u, v)</tex> называется '''недопустимым ''' (англ. ''inadmissible)''').
}}
{{Определение
|definition=
'''Допустимая сеть ''' (англ. ''admissible network)''' ) {{---}} сеть <tex>G_{f, h} = (V, E_{f, h})</tex>, где <tex>E_{f, h}</tex> {{---}} множество допустимых ребер.
}}
Анонимный участник

Навигация