338
правок
Изменения
м
Нет описания правки
|id = Лемма4
|statement =
Когда операция <tex>'''discharge</tex> ''' вызывает в операцию <tex>push(u, v)</tex>, то для пары вершин <tex>(u, v)</tex> применима операция проталкивания.
|proof =
Проверки операции <tex>'''discharge</tex>''', сделанные до вызова операции проталкивания, гарантируют то, что операция <tex>push</tex> будет вызвана только тогда, когда она применима. То есть <tex>e(u) > 0</tex>, <tex>c_{f}(u, v) > 0</tex> и <tex>h(u) = h(v) + 1</tex>.
}}
|id = Лемма5
|statement =
Когда операция <tex>'''discharge</tex> ''' вызывает в операцию <tex>relabel(u)</tex>, то для вершины <tex>u</tex> применим подъем.
|proof =
Из [[Алгоритм "поднять-в-начало"#Лемма3|леммы об изменении допустимой цепи (для операции relabel)]] и условия <tex>e(u) > 0</tex> следует, что для доказательства данной леммы необходимо показать, что все ребра выходящие из <tex>u</tex>, являются недопустимыми.
Каждый проход операции <tex>'''discharge(u)</tex> ''' начинается с головы списка <tex>N[u]</tex> и оканчивается, когда <tex>current[u] = null</tex>. Именно тогда вызывается <tex>relabel(u)</tex> и начинается новый проход. К концу прохода все ребра, выходящие из <tex>u</tex>, станут недопустимыми, так как из [[Алгоритм "поднять-в-начало"#Лемма2|леммы об изменении допустимой цепи (для операции push)]] следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина <tex>u</tex> не подвергается подъему во время прохода, а любая другая вершина <tex>v</tex>, для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из [[Алгоритм "поднять-в-начало"#Лемма3|леммы об изменении допустимой цепи (для операции relabel)]]. Значит, в конце прохода все ребра, выходящие из <tex>u</tex>, останутся недопустимыми.
}}
Инициализируем предпоток и высоты, с помощью операции [[Метод проталкивания предпотока#Схема алгоритма|initializePreflow]], список <tex>L</tex> {{---}} список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель <tex>current</tex> каждой вершины <tex>u</tex>, чтобы он указывал на первую вершину в списке <tex>u</tex>.
Пройдем по списку <tex>L</tex> разгружая вершины, начиная с первой вершины. И если операция <tex>'''discharge</tex> ''' изменила высоту вершины, то перемещаем ее в начало списка <tex>L</tex>. Передвинем указатель на следующую вершину списке <tex>L</tex>, если после разгрузки была изменена высота, то берем следующую вершину в новом списке <tex>L</tex>.
'''relabelToFront(s, t)'''
Пусть '''фаза''' {{---}} время между двумя последовательными операциями подъема. Так как всего, по [[Метод проталкивания предпотока#Лемма6|лемме (6)]], выполняется <tex>O(V^{2})</tex> подъемов, значит, в алгоритме всего <tex>O(V^{2})</tex> фаз.
Если операция <tex>'''discharge</tex> ''' не выполняет подъем, то следующий ее вызов происходит дальше по списку <tex>L</tex> <tex>(</tex>длина <tex>L</tex> меньше <tex>|V|)</tex>. Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более <tex>|V|</tex> вызовов <tex>'''discharge</tex>'''.
Таким образом, цикл '''while''' процедуры <tex>relabelToFront</tex> выполняет работу (без учета операций вызываемых в <tex>'''discharge</tex>'''), за <tex>O(V^{3})</tex>.
Оценим работу выполнения внутри операции <tex>'''discharge</tex>''':
#Обновление указателя <tex>current[u]</tex> выполняется <tex>O(deg(u))</tex> в том случае, когда вершина <tex>u</tex> подвергается подъему. Значит, для всех вершин время составляет <tex>O(V deg(u))</tex>. Следовательно, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], время равно <tex>O(VE)</tex>.
#Пусть <tex>u</tex> {{---}} произвольная вершина сети. Она может быть поднята не более <tex>O(V)</tex> раз, время каждого подъема <tex>O(deg(u))</tex>. Значит, время всех подъемов ограничивается <tex>O(VE)</tex>.
#Из [[Метод проталкивания предпотока#Лемма8|леммы (8)]] следует, что количество насыщающих проталкиваний составляет <tex>O(VE)</tex>. Ненасыщающее проталкивание уменьшает избыток до <tex>0</tex>, после чего разрядка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов <tex>'''discharge</tex>''', то есть <tex>O(V^{3})</tex>.
Таким образом, время выполнения операции <tex>relabelToFront</tex> составляет <tex>O(V^{3} + VE)</tex>, что эквивалентно <tex>O(V^{3})</tex>.
