Алгоритм "поднять-в-начало" — различия между версиями
Whiplash (обсуждение | вклад) (→Допустимые ребра) |
м (rollbackEdits.php mass rollback) |
||
(не показана 61 промежуточная версия 9 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Алгоритм "поднять-в-начало" (relabel-to-front | + | '''Алгоритм "поднять-в-начало"''' (англ. ''relabel-to-front'') основан на [[Метод проталкивания предпотока|методе проталкивание предпотока]], но из-за тщательного выбора порядка выполнения операций [[Метод проталкивания предпотока#Проталкивание (push)|проталкивания]] и [[Метод проталкивания предпотока#Подъем (relabel)|подъема]], время выполнения данного алгоритма составляет <tex>O(V^{3})</tex>, что асимптотически не хуже, чем <tex>O(V^{2}E)</tex>. |
== Допустимые ребра == | == Допустимые ребра == | ||
Строка 5: | Строка 5: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Допустимое ребро (admissible edge | + | '''Допустимое ребро''' (англ. ''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= | |definition= | ||
− | '''Допустимая сеть (admissible network | + | '''Допустимая сеть''' (англ. ''admissible network'') {{---}} сеть <tex>G_{f, h} = (V, E_{f, h})</tex>, где <tex>E_{f, h}</tex> {{---}} множество допустимых ребер. |
}} | }} | ||
Строка 17: | Строка 17: | ||
|about = Допустимая сеть является ациклической | |about = Допустимая сеть является ациклической | ||
|statement = | |statement = | ||
− | + | Допустимая сеть <tex>G_{f, h} = (V, E_{f, h})</tex> является ациклической. | |
|proof = | |proof = | ||
Пусть в <tex>G_{f, h}</tex> существует [[Основные определения теории графов|циклический путь]] <tex>p = \left \langle v_0, v_1, \dots, v_k \right \rangle</tex>, где <tex>k > 0</tex>. | Пусть в <tex>G_{f, h}</tex> существует [[Основные определения теории графов|циклический путь]] <tex>p = \left \langle v_0, v_1, \dots, v_k \right \rangle</tex>, где <tex>k > 0</tex>. | ||
− | <tex> ~ ~ h | + | <tex> ~ ~ h[v_{i - 1}] = h[v_{i}] + 1</tex> для <tex>i = 1, 2, \dots, k</tex>, так как каждое ребро данного пути допустимое. Просуммировав равенства вдоль циклического пути, получаем: |
<tex>\sum \limits_{i = 1}^{k} h(v_{i - 1}) = \sum \limits_{i = 1}^{k} (h(v_{i}) + 1) = \sum \limits_{i = 1}^{k} h(v_{i}) + k</tex> | <tex>\sum \limits_{i = 1}^{k} h(v_{i - 1}) = \sum \limits_{i = 1}^{k} (h(v_{i}) + 1) = \sum \limits_{i = 1}^{k} h(v_{i}) + k</tex> | ||
− | + | Вершина циклического пути <tex>p</tex> встречается при суммировании по одному разу. Значит, <tex>k = 0</tex>, что противоречит первоначальному предположению. Следовательно, допустимая сеть является ациклической. | |
}} | }} | ||
− | |||
+ | {{Лемма | ||
+ | |id = Лемма2 | ||
+ | |about = Об изменении допустимой цепи с помощью операции проталкивания | ||
+ | |statement = | ||
+ | Если вершина <tex>u</tex> переполнена и ребро <tex>(u, v)</tex> допустимое, то применяемая операция <tex>push(u, v)</tex> не создает новые допустимые ребра, но может привести к тому, что ребро <tex>(u, v)</tex> станет недопустимым. | ||
+ | |proof = | ||
+ | Из <tex>u</tex> в <tex>v</tex> можно протолкнуть поток, так как ребро <tex>(u, v)</tex> допустимое, по определению. Из-за того что <tex>u</tex> {{---}} переполнена, вызываем операцию <tex>push(u, v)</tex>. В результате выполнения операции может быть создано остаточное ребро <tex>(v, u)</tex>. Поскольку ребро <tex>(u, v)</tex> допустимое, то <tex>h[v] = h[u] - 1</tex>, а это значит, что ребро <tex>(v, u)</tex> не может стать допустимым. | ||
+ | |||
+ | Если выполненная операция <tex>push(u, v)</tex> является насыщающим проталкиванием, то после ее выполнения <tex>c_{f}(u, v) = 0</tex> и ребро <tex>(u, v)</tex> становится недопустимым. | ||
+ | }} | ||
+ | |||
+ | |||
+ | {{Лемма | ||
+ | |id = Лемма3 | ||
+ | |about = Об изменении допустимой цепи с помощью операции подъема | ||
+ | |statement = | ||
+ | Если вершина <tex>u</tex> переполнена и не имеется допустимых ребер, выходящих из <tex>u</tex>, то применяется операция <tex>relabel(u)</tex>. После подъема появляется по крайней мере одно допустимое ребро, выходящее из <tex>u</tex>, но нет допустимых ребер, входящих в <tex>u</tex>. | ||
+ | |proof = | ||
+ | Рассмотрим вершину <tex>u</tex>. Если <tex>u</tex> переполнена, то, согласно [[Метод проталкивания предпотока#Лемма2|лемме (2)]], к ней может быть применима либо операция проталкивания, либо операция подъема. А так как не существует допустимых ребер для <tex>u</tex>, то протолкнуть поток не возможно, значит, применяется операция <tex>relabel(u)</tex>. После данного подъема <tex>h[u] = 1 + min \{ h[v]: (u, v) \in E_{f} \}</tex>. Значит, если <tex>u</tex> {{---}} вершина указанного множества, в которой реализуется минимум, то <tex>(u, v)</tex> становится допустимым. А это значит, что после подъема существует, хотя бы одно, допустимое ребро, выходящее из <tex>u</tex>. | ||
+ | |||
+ | Пусть, после подъема существует такая вершина <tex>u</tex>, что ребро <tex>(v, u)</tex> допустимо. Тогда после подъема <tex>h[v] = h[u] + 1</tex>, а перед ним <tex>h[v] > h[u] + 1</tex>. Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных ребер. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро <tex>(v, u)</tex> не может находится в допустимой сети, так как оно не принадлежит остаточной сети. | ||
+ | }} | ||
== Операция разгрузки (discharge) == | == Операция разгрузки (discharge) == | ||
− | |||
− | + | '''Разгрузка''' (англ. ''discharge'') {{---}} операция, применяемая к переполненной вершине <tex>u</tex>, для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая <tex>u</tex>, делая недопустимые ребра, выходящие из вершины <tex>u</tex>, допустимыми. | |
− | + | Будем хранить для каждой вершины <tex>u</tex> список <tex>N[u]</tex> (список вершин, смежных с ней). То есть список <tex>N[u]</tex> содержит каждую вершину <tex>v</tex> такую, что в сети <tex>G = (V, E)</tex> ребро <tex>(u, v) \in E</tex> или <tex>(v, u) \in E</tex>. | |
− | Для | + | На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex> \varnothing</tex>, если <tex>w</tex> {{---}} последняя вершина в списке. |
− | ''' | + | Для каждой вершины <tex>u</tex> указатель <tex>current[u]</tex> {{---}} указатель на текущую вершину списка. Изначально <tex>current[u] = head[N[u]]</tex>. |
− | '''while''' e[u] > 0 | + | |
− | v = current[u] | + | '''function''' <tex>\mathtt{discharge}(u):</tex> |
− | '''if''' v = | + | '''while''' <tex>e[u] > 0 </tex> |
− | relabel(u) | + | <tex>v = current[u]</tex> |
− | current[u] = head[N[u]] | + | '''if''' <tex>v = \varnothing</tex> |
+ | <tex>\mathtt{relabel}(u)</tex> | ||
+ | <tex>current[u] = head[N[u]]</tex> | ||
'''else''' | '''else''' | ||
− | '''if''' c(u, v) > 0 and h[u] = h[v] + 1 | + | '''if''' <tex>c(u, v) - f(u, v) > 0</tex> '''and''' <tex>h[u] = h[v] + 1 </tex> |
− | push(u, v) | + | <tex>\mathtt{push}(u, v) </tex> |
'''else''' | '''else''' | ||
− | current[u] = next[v] | + | <tex>current[u] = next[v]</tex> |
+ | |||
+ | Операция завершится только тогда, когда избыток <tex>e(u)</tex> станет равным нулю, и ни подъем, ни перемещение указателя <tex>current[u]</tex> не влияет на значение <tex>e(u)</tex>. | ||
+ | |||
+ | Докажем, что когда <tex>\mathtt{discharge}</tex> вызывает операции [[Метод проталкивания предпотока#Проталкивание (push)|push]] и [[Метод проталкивания предпотока#Подъем (relabel)|relable]], они применимы. | ||
− | |||
{{Лемма | {{Лемма | ||
− | |id = | + | |about = О применимости операции push |
+ | |id = Лемма4 | ||
|statement = | |statement = | ||
− | Когда | + | Когда <tex>\mathtt{discharge}</tex> вызывает в операцию <tex>push(u, v)</tex>, то для пары вершин <tex>(u, v)</tex> применима операция проталкивания. |
|proof = | |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>. | + | Проверки операции <tex>\mathtt{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 = Лемма2 | + | |about = О применимости операции relabel |
+ | |id = Лемма5 | ||
+ | |statement = | ||
+ | Когда <tex>\mathtt{discharge}</tex> вызывает в операцию <tex>relabel(u)</tex>, то для вершины <tex>u</tex> применим подъем. | ||
+ | |proof = | ||
+ | Из [[Алгоритм "поднять-в-начало"#Лемма3|леммы об изменении допустимой цепи (для операции relabel)]] и условия <tex>e(u) > 0</tex> следует, что для доказательства данной леммы необходимо показать, что все ребра, выходящие из <tex>u</tex>, являются недопустимыми. | ||
+ | |||
+ | Каждый проход операции <tex>\mathtt{discharge}(u)</tex> начинается с головы списка <tex>N[u]</tex> и оканчивается, когда <tex>current[u] = \varnothing</tex>. Именно тогда вызывается <tex>relabel(u)</tex>, и начинается новый проход. К концу прохода все ребра, выходящие из <tex>u</tex>, станут недопустимыми, так как из [[Алгоритм "поднять-в-начало"#Лемма2|леммы об изменении допустимой цепи (для операции push)]] следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина <tex>u</tex> не подвергается подъему во время прохода, а любая другая вершина <tex>v</tex>, для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из [[Алгоритм "поднять-в-начало"#Лемма3|леммы об изменении допустимой цепи (для операции relabel)]]. Значит, в конце прохода все ребра, выходящие из <tex>u</tex>, останутся недопустимыми. | ||
+ | }} | ||
+ | |||
+ | == Алгоритм == | ||
+ | Инициализируем предпоток и высоты, с помощью операции [[Метод проталкивания предпотока#Схема алгоритма|<tex>\mathtt{initializePreflow}</tex>]]. Список <tex>L</tex> {{---}} список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель <tex>current</tex> каждой вершины <tex>u</tex>, чтобы он указывал на первую вершину в списке <tex>u</tex>. | ||
+ | |||
+ | Пройдем по списку <tex>L</tex>, разгружая вершины, начиная с первой. И если операция <tex>\mathtt{discharge}</tex> изменила высоту вершины, то перемещаем ее в начало списка <tex>L</tex>. Передвинем указатель на следующую вершину списке <tex>L</tex>. Если после разгрузки была изменена высота, то берем следующую вершину в новом списке <tex>L</tex>. | ||
+ | |||
+ | '''function''' <tex>\mathtt{relabelToFront}(s, t): </tex>''' | ||
+ | <tex>\mathtt{initializePreflow(s)}</tex> | ||
+ | <tex>L = V \setminus \{ s, t \}</tex> | ||
+ | '''for''' <tex>u \in V </tex> <tex>\setminus</tex> <tex>\{ s, t \}</tex> | ||
+ | <tex>current[u] = head[N[u]]</tex> | ||
+ | <tex>u = head[L]</tex> | ||
+ | '''while''' <tex>u \ne null</tex> | ||
+ | <tex>oldHeight = h[u]</tex> | ||
+ | <tex>\mathtt{discharge(u)}</tex> | ||
+ | '''if''' <tex>h[u] > oldHeight</tex> | ||
+ | передвинуть <tex>u</tex> в начало списка <tex>L</tex> | ||
+ | <tex>u = nextVertex[u]</tex> | ||
+ | |||
+ | В приведенном псевдокоде предполагается, что для каждой вершины <tex>u</tex> уже создан список <tex>N[u]</tex>. | ||
+ | |||
+ | <tex>nextVertex[u]</tex> хранит вершину, следующую за <tex>u</tex> в списке <tex>L</tex>. Если <tex>u</tex> {{---}} последняя вершина в списке, то <tex>nextVertex[u] = null</tex>. | ||
+ | |||
+ | '''Инвариант цикла''': "при каждом выполнении условия вхождения в цикл <tex>\mathtt{while}</tex> вершины в списке <tex>L</tex> топологически упорядочены в допустимой сети <tex>G_{f, h} = (V, E_{f, h})</tex>, и ни одна вершина, стоящая в списке перед <tex>u</tex>, не имеет избыточного потока". | ||
+ | |||
+ | == Корректность алгоритма == | ||
+ | Для доказательства корректности алгоритма, то есть чтобы показать что операция <tex>\mathtt{relabelToFront}</tex> вычисляет поток, покажем, что она является реализацией универсального алгоритма [[Метод проталкивания предпотока|проталкивания предпотока]]. Для начала, заметим, что она выполняет операции <tex>push</tex> и <tex>relabel</tex> только тогда, когда они применимы, следует из [[Алгоритм "поднять-в-начало"#Лемма4|лемм о применимости операций push и relabel]]. Покажем, что когда операция <tex>\mathtt{relabelToFront}</tex> завершится, не применима ни одна основная операция. Для этого подробно рассмотрим операцию <tex>\mathtt{relabelToFront}</tex>: | ||
+ | |||
+ | #После вызова <tex>\mathtt{initializePreflow}</tex> <tex>h[s] = |V|</tex> и <tex>h[u] = 0</tex> для всех <tex>u \in V \setminus {s}</tex>. Так как <tex>|V| \geqslant 2</tex>, то ни одно ребро не является допустимым. Значит, <tex>E_{f, h} = \varnothing</tex> и любой порядок множества <tex>V \setminus \{s, t\}</tex> является топологическим упорядочением <tex>G_{f, h}</tex>. | ||
+ | #Проверим, что топологическое упорядочение сохранится при проведении итераций цикла <tex>\mathtt{while}</tex>. Для начала заметим, что сеть может изменится только из-за операций проталкивания и подъема. Из [[Алгоритм "поднять-в-начало"#Лемма2|леммы об изменении допустимой цепи]] нам известно, что после операции проталкивания новые допустимые ребра не появляются, а это значит, что они могли появится только во время выполнения операции подъема. После того как для вершины <tex>u</tex> применили операцию подъема, больше не существует допустимых ребер, входящих в <tex>u</tex>, но могут быть допустимые ребра, выходящие из нее. Таким образом, перемещая <tex>u</tex> в начало списка <tex>L</tex>, все допустимые ребра, выходящие из <tex>u</tex>, удовлетворяют условию топологического упорядочения. | ||
+ | #Проверим, что ни одна вершина, предшествующая <tex>u</tex> в списке <tex>L</tex>, не имеет избытка потока. Пусть вершина <tex>u'</tex> {{---}} вершина <tex>u</tex> на следующей итерации. | ||
+ | ##Если <tex>u</tex> подверглась подъему, то вершин предшествующих <tex>u'</tex> на следующей итерации, кроме <tex>u</tex>, нет или если высота <tex>u</tex> не изменилась, то там остались те же вершины, что и ранее. Так как <tex>u</tex> подверглась разгрузке, то она не содержит избытка потока. Значит, если <tex>u</tex> подверглась подъему в процессе разгрузки, то ни одна вершина, предшествующая <tex>u'</tex>, не содержит избытка потока. | ||
+ | ##Если высота <tex>u</tex> не поменялась во время разгрузки, то вершины, стоящие в списке <tex>L</tex> перед ней, не получили избыток потока, так как <tex>L</tex> топологически упорядочен все время в процессе разгрузки, поэтому каждая операция проталкивания продвигает поток только по вершинам дальше по списку. В этом случае ни одна вершина, предшествующая <tex>u'</tex>, также не имеет избытка потока. | ||
+ | #После завершения цикла <tex>u = null</tex>, поэтому избыток всех вершин равен <tex>0</tex> (инвариант цикла). Значит, ни одна основная операция неприменима. | ||
+ | |||
+ | == Оценка быстродействия == | ||
+ | {{Теорема | ||
|statement = | |statement = | ||
− | + | Время выполнения операции <tex>\mathtt{relabelToFront}</tex> для любой сети <tex>G = (V, E)</tex> составляет <tex>O(V^{3})</tex>. | |
|proof = | |proof = | ||
+ | Пусть '''фаза''' {{---}} время между двумя последовательными операциями подъема. Так как всего, по [[Метод проталкивания предпотока#Лемма6|лемме (6)]], выполняется <tex>O(V^{2})</tex> подъемов, значит, в алгоритме всего <tex>O(V^{2})</tex> фаз. | ||
+ | Если операция <tex>\mathtt{discharge}</tex> не выполняет подъем, то следующий ее вызов происходит дальше по списку <tex>L</tex> <tex>(</tex>длина <tex>L</tex> меньше <tex>|V|)</tex>. Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более <tex>|V|</tex> вызовов <tex>\mathtt{discharge}</tex>. | ||
+ | |||
+ | Таким образом, цикл <tex>\mathtt{while}</tex> процедуры <tex>\mathtt{relabelToFront}</tex> выполняет работу (без учета операций вызываемых в <tex>\mathtt{discharge}</tex>), за <tex>O(V^{3})</tex>. | ||
+ | |||
+ | Оценим работу выполнения внутри операции <tex>\mathtt{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>\mathtt{discharge}</tex>, то есть <tex>O(V^{3})</tex>. | ||
+ | |||
+ | Таким образом, время выполнения операции <tex>\mathtt{relabelToFront}</tex> составляет <tex>O(V^{3} + VE)</tex>, что эквивалентно <tex>O(V^{3})</tex>. | ||
}} | }} | ||
− | == Схема алгоритма | + | ==См. также== |
− | + | * [[Метод проталкивания предпотока]] | |
− | == Источники == | + | * [[Теорема Форда-Фалкерсона]] |
+ | * [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | ||
+ | * [[Схема алгоритма Диница]] | ||
+ | * [[Алоритм Эдмондса-Карпа]] | ||
+ | |||
+ | == Источники информации == | ||
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785. | * Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785. | ||
* [http://ru.wikipedia.org/wiki/Алгоритм_проталкивания_предпотока Алгоритм проталкивания предпотока — Википедия] | * [http://ru.wikipedia.org/wiki/Алгоритм_проталкивания_предпотока Алгоритм проталкивания предпотока — Википедия] | ||
− | + | *[http://e-maxx.ru/algo/preflow_push_faster MAXimal::algo::Модификация метода Проталкивания предпотока для нахождения максимального потока за O (N3)] | |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о максимальном потоке]] | [[Категория: Задача о максимальном потоке]] |
Текущая версия на 19:43, 4 сентября 2022
Алгоритм "поднять-в-начало" (англ. relabel-to-front) основан на методе проталкивание предпотока, но из-за тщательного выбора порядка выполнения операций проталкивания и подъема, время выполнения данного алгоритма составляет , что асимптотически не хуже, чем .
Содержание
Допустимые ребра
сеть с истоком и стоком , — предпоток в , — функция высоты.
—Определение: |
Допустимое ребро (англ. admissible edge) — ребро | , у которого и . В противном случае называется недопустимым (англ. inadmissible).
Определение: |
Допустимая сеть (англ. admissible network) — сеть | , где — множество допустимых ребер.
Лемма (Допустимая сеть является ациклической): |
Допустимая сеть является ациклической. |
Доказательство: |
Пусть в циклический путь , где . существуетдля , так как каждое ребро данного пути допустимое. Просуммировав равенства вдоль циклического пути, получаем: Вершина циклического пути встречается при суммировании по одному разу. Значит, , что противоречит первоначальному предположению. Следовательно, допустимая сеть является ациклической. |
Лемма (Об изменении допустимой цепи с помощью операции проталкивания): |
Если вершина переполнена и ребро допустимое, то применяемая операция не создает новые допустимые ребра, но может привести к тому, что ребро станет недопустимым. |
Доказательство: |
Из Если выполненная операция в можно протолкнуть поток, так как ребро допустимое, по определению. Из-за того что — переполнена, вызываем операцию . В результате выполнения операции может быть создано остаточное ребро . Поскольку ребро допустимое, то , а это значит, что ребро не может стать допустимым. является насыщающим проталкиванием, то после ее выполнения и ребро становится недопустимым. |
Лемма (Об изменении допустимой цепи с помощью операции подъема): |
Если вершина переполнена и не имеется допустимых ребер, выходящих из , то применяется операция . После подъема появляется по крайней мере одно допустимое ребро, выходящее из , но нет допустимых ребер, входящих в . |
Доказательство: |
Рассмотрим вершину лемме (2), к ней может быть применима либо операция проталкивания, либо операция подъема. А так как не существует допустимых ребер для , то протолкнуть поток не возможно, значит, применяется операция . После данного подъема . Значит, если — вершина указанного множества, в которой реализуется минимум, то становится допустимым. А это значит, что после подъема существует, хотя бы одно, допустимое ребро, выходящее из . Пусть, после подъема существует такая вершина . Если переполнена, то, согласно , что ребро допустимо. Тогда после подъема , а перед ним . Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных ребер. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро не может находится в допустимой сети, так как оно не принадлежит остаточной сети. |
Операция разгрузки (discharge)
Разгрузка (англ. discharge) — операция, применяемая к переполненной вершине
, для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая , делая недопустимые ребра, выходящие из вершины , допустимыми.Будем хранить для каждой вершины
список (список вершин, смежных с ней). То есть список содержит каждую вершину такую, что в сети ребро или .На первую вершину в списке указывает указатель
. Для перехода к следующей вершине в списке за , поддерживается указатель . Он равен , если — последняя вершина в списке.Для каждой вершины
указатель — указатель на текущую вершину списка. Изначально .functionwhile if else if and else
Операция завершится только тогда, когда избыток
станет равным нулю, и ни подъем, ни перемещение указателя не влияет на значение .Докажем, что когда push и relable, они применимы.
вызывает операции
Лемма (О применимости операции push): |
Когда вызывает в операцию , то для пары вершин применима операция проталкивания. |
Доказательство: |
Проверки операции | , сделанные до вызова операции проталкивания, гарантируют то, что операция будет вызвана только тогда, когда она применима. То есть , и .
Лемма (О применимости операции relabel): |
Когда вызывает в операцию , то для вершины применим подъем. |
Доказательство: |
Из леммы об изменении допустимой цепи (для операции relabel) и условия следует, что для доказательства данной леммы необходимо показать, что все ребра, выходящие из , являются недопустимыми. Каждый проход операции начинается с головы списка и оканчивается, когда . Именно тогда вызывается , и начинается новый проход. К концу прохода все ребра, выходящие из , станут недопустимыми, так как из леммы об изменении допустимой цепи (для операции push) следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина не подвергается подъему во время прохода, а любая другая вершина , для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из леммы об изменении допустимой цепи (для операции relabel). Значит, в конце прохода все ребра, выходящие из , останутся недопустимыми. |
Алгоритм
Инициализируем предпоток и высоты, с помощью операции . Список — список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель каждой вершины , чтобы он указывал на первую вершину в списке .
Пройдем по списку
, разгружая вершины, начиная с первой. И если операция изменила высоту вершины, то перемещаем ее в начало списка . Передвинем указатель на следующую вершину списке . Если после разгрузки была изменена высота, то берем следующую вершину в новом списке .functionfor while if передвинуть в начало списка
В приведенном псевдокоде предполагается, что для каждой вершины
уже создан список .хранит вершину, следующую за в списке . Если — последняя вершина в списке, то .
Инвариант цикла: "при каждом выполнении условия вхождения в цикл
вершины в списке топологически упорядочены в допустимой сети , и ни одна вершина, стоящая в списке перед , не имеет избыточного потока".Корректность алгоритма
Для доказательства корректности алгоритма, то есть чтобы показать что операция проталкивания предпотока. Для начала, заметим, что она выполняет операции и только тогда, когда они применимы, следует из лемм о применимости операций push и relabel. Покажем, что когда операция завершится, не применима ни одна основная операция. Для этого подробно рассмотрим операцию :
вычисляет поток, покажем, что она является реализацией универсального алгоритма- После вызова и для всех . Так как , то ни одно ребро не является допустимым. Значит, и любой порядок множества является топологическим упорядочением .
- Проверим, что топологическое упорядочение сохранится при проведении итераций цикла леммы об изменении допустимой цепи нам известно, что после операции проталкивания новые допустимые ребра не появляются, а это значит, что они могли появится только во время выполнения операции подъема. После того как для вершины применили операцию подъема, больше не существует допустимых ребер, входящих в , но могут быть допустимые ребра, выходящие из нее. Таким образом, перемещая в начало списка , все допустимые ребра, выходящие из , удовлетворяют условию топологического упорядочения. . Для начала заметим, что сеть может изменится только из-за операций проталкивания и подъема. Из
- Проверим, что ни одна вершина, предшествующая
- Если подверглась подъему, то вершин предшествующих на следующей итерации, кроме , нет или если высота не изменилась, то там остались те же вершины, что и ранее. Так как подверглась разгрузке, то она не содержит избытка потока. Значит, если подверглась подъему в процессе разгрузки, то ни одна вершина, предшествующая , не содержит избытка потока.
- Если высота не поменялась во время разгрузки, то вершины, стоящие в списке перед ней, не получили избыток потока, так как топологически упорядочен все время в процессе разгрузки, поэтому каждая операция проталкивания продвигает поток только по вершинам дальше по списку. В этом случае ни одна вершина, предшествующая , также не имеет избытка потока.
в списке , не имеет избытка потока. Пусть вершина — вершина на следующей итерации.
- После завершения цикла , поэтому избыток всех вершин равен (инвариант цикла). Значит, ни одна основная операция неприменима.
Оценка быстродействия
Теорема: |
Время выполнения операции для любой сети составляет . |
Доказательство: |
Пусть фаза — время между двумя последовательными операциями подъема. Так как всего, по лемме (6), выполняется подъемов, значит, в алгоритме всего фаз. Если операция не выполняет подъем, то следующий ее вызов происходит дальше по списку длина меньше . Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более вызовов .Таким образом, цикл процедуры выполняет работу (без учета операций вызываемых в ), за .Оценим работу выполнения внутри операции :
|
См. также
- Метод проталкивания предпотока
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Схема алгоритма Диница
- Алоритм Эдмондса-Карпа
Источники информации
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 774—785.
- Алгоритм проталкивания предпотока — Википедия
- MAXimal::algo::Модификация метода Проталкивания предпотока для нахождения максимального потока за O (N3)