Алгоритм "поднять-в-начало" — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Допустимые ребра)
м (rollbackEdits.php mass rollback)
 
(не показана 61 промежуточная версия 9 участников)
Строка 1: Строка 1:
'''Алгоритм "поднять-в-начало" (relabel-to-front)''' основан на [[Метод проталкивания предпотока|методе проталкивание предпотока]], но из-за тщательного выбора порядка выполнения операций [[Метод проталкивания предпотока#Проталкивание (push)|проталкивания]] и [[Метод проталкивания предпотока#Подъем (relabel)|подъема]], время выполнения данного алгоритма составляет <tex>O(V^{3})</tex>, что асимптотически не хуже, чем <tex>O(V^{2}E)</tex>.
+
'''Алгоритм "поднять-в-начало"''' (англ. ''relabel-to-front'') основан на [[Метод проталкивания предпотока|методе проталкивание предпотока]], но из-за тщательного выбора порядка выполнения операций [[Метод проталкивания предпотока#Проталкивание (push)|проталкивания]] и [[Метод проталкивания предпотока#Подъем (relabel)|подъема]], время выполнения данного алгоритма составляет <tex>O(V^{3})</tex>, что асимптотически не хуже, чем <tex>O(V^{2}E)</tex>.
  
 
== Допустимые ребра ==
 
== Допустимые ребра ==
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Допустимое ребро (admissible edge)''' {{---}} ребро <tex>uv</tex>, у которого <tex>c_{f}(u, v) > 0</tex> и <tex>h(u) = h(v) + 1</tex>. В противном случае <tex>uv</tex> называется '''недопустимым (inadmissible)'''.
+
'''Допустимое ребро''' (англ. ''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)''' {{---}} сеть <tex>G_{f, h} = (V, E_{f, h})</tex>, где <tex>E_{f, h}</tex> {{---}} множество допустимых ребер.
+
'''Допустимая сеть''' (англ. ''admissible network'') {{---}} сеть <tex>G_{f, h} = (V, E_{f, h})</tex>, где <tex>E_{f, h}</tex> {{---}} множество допустимых ребер.
 
}}
 
}}
  
Строка 17: Строка 17:
 
|about = Допустимая сеть является ациклической
 
|about = Допустимая сеть является ациклической
 
|statement =
 
|statement =
Если <tex>G = (V, E)</tex> {{---}} сеть с истоком <tex>s</tex> и стоком <tex>t</tex>, <tex>f</tex> {{---}} предпоток в <tex>G</tex>, а <tex>h</tex> {{---}} функция высоты, тогда допустимая сеть <tex>G_{f, h} = (V, E_{f, h})</tex> является ациклической.
+
Допустимая сеть <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(v_{i - 1}) = h(v_{i}) + 1</tex> для <tex>i = 1, 2, \dots, k</tex>, так как каждое ребро данного пути допустимое. Просуммировав равенства вдоль циклического пути, получаем:
+
<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>, что противоречит первоначальному предположению. Значит, допустимая сеть является ациклической.
+
Вершина циклического пути <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) ~ (u, v) \in E</tex> или <tex>(v, u) \in E</tex>.  
+
'''Разгрузка''' (англ. ''discharge'') {{---}} операция, применяемая к переполненной вершине <tex>u</tex>, для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая <tex>u</tex>, делая недопустимые ребра, выходящие из вершины <tex>u</tex>, допустимыми.
  
На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex>null</tex> если <tex>w</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>u</tex> указатель <tex>current[u]</tex> - указатель на текущую вершину списка. Изначально <tex>current[u] = head[N[u]]</tex>.
+
На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex> \varnothing</tex>, если <tex>w</tex> {{---}} последняя вершина в списке.
  
  '''discharge'''(u)
+
Для каждой вершины <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 = null
+
     '''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]], они применимы.
  
Докажем то, что когда операция '''discharge''' вызывает операции [[Метод проталкивания предпотока#Проталкивание (push)|push]] и [[Метод проталкивания предпотока#Подъем (relabel)|relable]], эти операции применимы.
 
  
 
{{Лемма
 
{{Лемма
|id = Лемма1
+
|about = О применимости операции push
 +
|id = Лемма4
 
|statement =
 
|statement =
Когда операция <tex>discharge</tex> вызывает в операцию <tex>push(u, v)</tex>, то для пары вершин <tex>(u, v)</tex> применима операция проталкивания.
+
Когда <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>discharge</tex> вызывает в операцию <tex>relabel(u)</tex>, то для вершины <tex>u</tex> применим подъем.
+
Время выполнения операции <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) основан на методе проталкивание предпотока, но из-за тщательного выбора порядка выполнения операций проталкивания и подъема, время выполнения данного алгоритма составляет [math]O(V^{3})[/math], что асимптотически не хуже, чем [math]O(V^{2}E)[/math].

Допустимые ребра

[math]G = (V, E)[/math]сеть с истоком [math]s[/math] и стоком [math]t[/math], [math]f[/math]предпоток в [math]G[/math], [math]h[/math]функция высоты.

Определение:
Допустимое ребро (англ. admissible edge) — ребро [math](u, v)[/math], у которого [math]c_{f}(u, v) \gt 0[/math] и [math]h[u] = h[v] + 1[/math]. В противном случае [math](u, v)[/math] называется недопустимым (англ. inadmissible).


Определение:
Допустимая сеть (англ. admissible network) — сеть [math]G_{f, h} = (V, E_{f, h})[/math], где [math]E_{f, h}[/math] — множество допустимых ребер.


Лемма (Допустимая сеть является ациклической):
Допустимая сеть [math]G_{f, h} = (V, E_{f, h})[/math] является ациклической.
Доказательство:
[math]\triangleright[/math]

Пусть в [math]G_{f, h}[/math] существует циклический путь [math]p = \left \langle v_0, v_1, \dots, v_k \right \rangle[/math], где [math]k \gt 0[/math].

[math] ~ ~ h[v_{i - 1}] = h[v_{i}] + 1[/math] для [math]i = 1, 2, \dots, k[/math], так как каждое ребро данного пути допустимое. Просуммировав равенства вдоль циклического пути, получаем:

[math]\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[/math]

Вершина циклического пути [math]p[/math] встречается при суммировании по одному разу. Значит, [math]k = 0[/math], что противоречит первоначальному предположению. Следовательно, допустимая сеть является ациклической.
[math]\triangleleft[/math]


Лемма (Об изменении допустимой цепи с помощью операции проталкивания):
Если вершина [math]u[/math] переполнена и ребро [math](u, v)[/math] допустимое, то применяемая операция [math]push(u, v)[/math] не создает новые допустимые ребра, но может привести к тому, что ребро [math](u, v)[/math] станет недопустимым.
Доказательство:
[math]\triangleright[/math]

Из [math]u[/math] в [math]v[/math] можно протолкнуть поток, так как ребро [math](u, v)[/math] допустимое, по определению. Из-за того что [math]u[/math] — переполнена, вызываем операцию [math]push(u, v)[/math]. В результате выполнения операции может быть создано остаточное ребро [math](v, u)[/math]. Поскольку ребро [math](u, v)[/math] допустимое, то [math]h[v] = h[u] - 1[/math], а это значит, что ребро [math](v, u)[/math] не может стать допустимым.

Если выполненная операция [math]push(u, v)[/math] является насыщающим проталкиванием, то после ее выполнения [math]c_{f}(u, v) = 0[/math] и ребро [math](u, v)[/math] становится недопустимым.
[math]\triangleleft[/math]


Лемма (Об изменении допустимой цепи с помощью операции подъема):
Если вершина [math]u[/math] переполнена и не имеется допустимых ребер, выходящих из [math]u[/math], то применяется операция [math]relabel(u)[/math]. После подъема появляется по крайней мере одно допустимое ребро, выходящее из [math]u[/math], но нет допустимых ребер, входящих в [math]u[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим вершину [math]u[/math]. Если [math]u[/math] переполнена, то, согласно лемме (2), к ней может быть применима либо операция проталкивания, либо операция подъема. А так как не существует допустимых ребер для [math]u[/math], то протолкнуть поток не возможно, значит, применяется операция [math]relabel(u)[/math]. После данного подъема [math]h[u] = 1 + min \{ h[v]: (u, v) \in E_{f} \}[/math]. Значит, если [math]u[/math] — вершина указанного множества, в которой реализуется минимум, то [math](u, v)[/math] становится допустимым. А это значит, что после подъема существует, хотя бы одно, допустимое ребро, выходящее из [math]u[/math].

Пусть, после подъема существует такая вершина [math]u[/math], что ребро [math](v, u)[/math] допустимо. Тогда после подъема [math]h[v] = h[u] + 1[/math], а перед ним [math]h[v] \gt h[u] + 1[/math]. Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных ребер. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро [math](v, u)[/math] не может находится в допустимой сети, так как оно не принадлежит остаточной сети.
[math]\triangleleft[/math]

Операция разгрузки (discharge)

Разгрузка (англ. discharge) — операция, применяемая к переполненной вершине [math]u[/math], для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая [math]u[/math], делая недопустимые ребра, выходящие из вершины [math]u[/math], допустимыми.

Будем хранить для каждой вершины [math]u[/math] список [math]N[u][/math] (список вершин, смежных с ней). То есть список [math]N[u][/math] содержит каждую вершину [math]v[/math] такую, что в сети [math]G = (V, E)[/math] ребро [math](u, v) \in E[/math] или [math](v, u) \in E[/math].

На первую вершину в списке указывает указатель [math]head[N[u]][/math]. Для перехода к следующей вершине в списке за [math]w[/math], поддерживается указатель [math]next[w][/math]. Он равен [math] \varnothing[/math], если [math]w[/math] — последняя вершина в списке.

Для каждой вершины [math]u[/math] указатель [math]current[u][/math] — указатель на текущую вершину списка. Изначально [math]current[u] = head[N[u]][/math].

function [math]\mathtt{discharge}(u):[/math]
    while [math]e[u] \gt  0 [/math]
        [math]v = current[u][/math]
        if [math]v =  \varnothing[/math]
            [math]\mathtt{relabel}(u)[/math]
            [math]current[u] = head[N[u]][/math]
        else
            if [math]c(u, v) - f(u, v) \gt  0[/math] and [math]h[u] = h[v] + 1 [/math]
                [math]\mathtt{push}(u, v) [/math]
            else
                [math]current[u] = next[v][/math]

Операция завершится только тогда, когда избыток [math]e(u)[/math] станет равным нулю, и ни подъем, ни перемещение указателя [math]current[u][/math] не влияет на значение [math]e(u)[/math].

Докажем, что когда [math]\mathtt{discharge}[/math] вызывает операции push и relable, они применимы.


Лемма (О применимости операции push):
Когда [math]\mathtt{discharge}[/math] вызывает в операцию [math]push(u, v)[/math], то для пары вершин [math](u, v)[/math] применима операция проталкивания.
Доказательство:
[math]\triangleright[/math]
Проверки операции [math]\mathtt{discharge}[/math], сделанные до вызова операции проталкивания, гарантируют то, что операция [math]push[/math] будет вызвана только тогда, когда она применима. То есть [math]e(u) \gt 0[/math], [math]c_{f}(u, v) \gt 0[/math] и [math]h(u) = h(v) + 1[/math].
[math]\triangleleft[/math]


Лемма (О применимости операции relabel):
Когда [math]\mathtt{discharge}[/math] вызывает в операцию [math]relabel(u)[/math], то для вершины [math]u[/math] применим подъем.
Доказательство:
[math]\triangleright[/math]

Из леммы об изменении допустимой цепи (для операции relabel) и условия [math]e(u) \gt 0[/math] следует, что для доказательства данной леммы необходимо показать, что все ребра, выходящие из [math]u[/math], являются недопустимыми.

Каждый проход операции [math]\mathtt{discharge}(u)[/math] начинается с головы списка [math]N[u][/math] и оканчивается, когда [math]current[u] = \varnothing[/math]. Именно тогда вызывается [math]relabel(u)[/math], и начинается новый проход. К концу прохода все ребра, выходящие из [math]u[/math], станут недопустимыми, так как из леммы об изменении допустимой цепи (для операции push) следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина [math]u[/math] не подвергается подъему во время прохода, а любая другая вершина [math]v[/math], для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из леммы об изменении допустимой цепи (для операции relabel). Значит, в конце прохода все ребра, выходящие из [math]u[/math], останутся недопустимыми.
[math]\triangleleft[/math]

Алгоритм

Инициализируем предпоток и высоты, с помощью операции [math]\mathtt{initializePreflow}[/math]. Список [math]L[/math] — список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель [math]current[/math] каждой вершины [math]u[/math], чтобы он указывал на первую вершину в списке [math]u[/math].

Пройдем по списку [math]L[/math], разгружая вершины, начиная с первой. И если операция [math]\mathtt{discharge}[/math] изменила высоту вершины, то перемещаем ее в начало списка [math]L[/math]. Передвинем указатель на следующую вершину списке [math]L[/math]. Если после разгрузки была изменена высота, то берем следующую вершину в новом списке [math]L[/math].

 function [math]\mathtt{relabelToFront}(s, t): [/math]
     [math]\mathtt{initializePreflow(s)}[/math]
     [math]L = V \setminus \{ s, t \}[/math]
     for [math]u \in  V [/math] [math]\setminus[/math] [math]\{ s, t \}[/math]
         [math]current[u] = head[N[u]][/math]
     [math]u = head[L][/math]
     while [math]u \ne null[/math]
         [math]oldHeight = h[u][/math]
         [math]\mathtt{discharge(u)}[/math]
         if [math]h[u] \gt  oldHeight[/math]
             передвинуть [math]u[/math] в начало списка [math]L[/math]
         [math]u = nextVertex[u][/math]

В приведенном псевдокоде предполагается, что для каждой вершины [math]u[/math] уже создан список [math]N[u][/math].

[math]nextVertex[u][/math] хранит вершину, следующую за [math]u[/math] в списке [math]L[/math]. Если [math]u[/math] — последняя вершина в списке, то [math]nextVertex[u] = null[/math].

Инвариант цикла: "при каждом выполнении условия вхождения в цикл [math]\mathtt{while}[/math] вершины в списке [math]L[/math] топологически упорядочены в допустимой сети [math]G_{f, h} = (V, E_{f, h})[/math], и ни одна вершина, стоящая в списке перед [math]u[/math], не имеет избыточного потока".

Корректность алгоритма

Для доказательства корректности алгоритма, то есть чтобы показать что операция [math]\mathtt{relabelToFront}[/math] вычисляет поток, покажем, что она является реализацией универсального алгоритма проталкивания предпотока. Для начала, заметим, что она выполняет операции [math]push[/math] и [math]relabel[/math] только тогда, когда они применимы, следует из лемм о применимости операций push и relabel. Покажем, что когда операция [math]\mathtt{relabelToFront}[/math] завершится, не применима ни одна основная операция. Для этого подробно рассмотрим операцию [math]\mathtt{relabelToFront}[/math]:

  1. После вызова [math]\mathtt{initializePreflow}[/math] [math]h[s] = |V|[/math] и [math]h[u] = 0[/math] для всех [math]u \in V \setminus {s}[/math]. Так как [math]|V| \geqslant 2[/math], то ни одно ребро не является допустимым. Значит, [math]E_{f, h} = \varnothing[/math] и любой порядок множества [math]V \setminus \{s, t\}[/math] является топологическим упорядочением [math]G_{f, h}[/math].
  2. Проверим, что топологическое упорядочение сохранится при проведении итераций цикла [math]\mathtt{while}[/math]. Для начала заметим, что сеть может изменится только из-за операций проталкивания и подъема. Из леммы об изменении допустимой цепи нам известно, что после операции проталкивания новые допустимые ребра не появляются, а это значит, что они могли появится только во время выполнения операции подъема. После того как для вершины [math]u[/math] применили операцию подъема, больше не существует допустимых ребер, входящих в [math]u[/math], но могут быть допустимые ребра, выходящие из нее. Таким образом, перемещая [math]u[/math] в начало списка [math]L[/math], все допустимые ребра, выходящие из [math]u[/math], удовлетворяют условию топологического упорядочения.
  3. Проверим, что ни одна вершина, предшествующая [math]u[/math] в списке [math]L[/math], не имеет избытка потока. Пусть вершина [math]u'[/math] — вершина [math]u[/math] на следующей итерации.
    1. Если [math]u[/math] подверглась подъему, то вершин предшествующих [math]u'[/math] на следующей итерации, кроме [math]u[/math], нет или если высота [math]u[/math] не изменилась, то там остались те же вершины, что и ранее. Так как [math]u[/math] подверглась разгрузке, то она не содержит избытка потока. Значит, если [math]u[/math] подверглась подъему в процессе разгрузки, то ни одна вершина, предшествующая [math]u'[/math], не содержит избытка потока.
    2. Если высота [math]u[/math] не поменялась во время разгрузки, то вершины, стоящие в списке [math]L[/math] перед ней, не получили избыток потока, так как [math]L[/math] топологически упорядочен все время в процессе разгрузки, поэтому каждая операция проталкивания продвигает поток только по вершинам дальше по списку. В этом случае ни одна вершина, предшествующая [math]u'[/math], также не имеет избытка потока.
  4. После завершения цикла [math]u = null[/math], поэтому избыток всех вершин равен [math]0[/math] (инвариант цикла). Значит, ни одна основная операция неприменима.

Оценка быстродействия

Теорема:
Время выполнения операции [math]\mathtt{relabelToFront}[/math] для любой сети [math]G = (V, E)[/math] составляет [math]O(V^{3})[/math].
Доказательство:
[math]\triangleright[/math]

Пусть фаза — время между двумя последовательными операциями подъема. Так как всего, по лемме (6), выполняется [math]O(V^{2})[/math] подъемов, значит, в алгоритме всего [math]O(V^{2})[/math] фаз.

Если операция [math]\mathtt{discharge}[/math] не выполняет подъем, то следующий ее вызов происходит дальше по списку [math]L[/math] [math]([/math]длина [math]L[/math] меньше [math]|V|)[/math]. Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более [math]|V|[/math] вызовов [math]\mathtt{discharge}[/math].

Таким образом, цикл [math]\mathtt{while}[/math] процедуры [math]\mathtt{relabelToFront}[/math] выполняет работу (без учета операций вызываемых в [math]\mathtt{discharge}[/math]), за [math]O(V^{3})[/math].

Оценим работу выполнения внутри операции [math]\mathtt{discharge}[/math]:

  1. Обновление указателя [math]current[u][/math] выполняется [math]O(\deg(u))[/math] в том случае, когда вершина [math]u[/math] подвергается подъему. Значит, для всех вершин время составляет [math]O(V \deg(u))[/math]. Следовательно, согласно лемме о рукопожатиях, время равно [math]O(VE)[/math].
  2. Пусть [math]u[/math] — произвольная вершина сети. Она может быть поднята не более [math]O(V)[/math] раз, время каждого подъема [math]O(\deg(u))[/math]. Значит, время всех подъемов ограничивается [math]O(VE)[/math].
  3. Из леммы (8) следует, что количество насыщающих проталкиваний составляет [math]O(VE)[/math]. Ненасыщающее проталкивание уменьшает избыток до [math]0[/math], после чего разгрузка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов [math]\mathtt{discharge}[/math], то есть [math]O(V^{3})[/math].
Таким образом, время выполнения операции [math]\mathtt{relabelToFront}[/math] составляет [math]O(V^{3} + VE)[/math], что эквивалентно [math]O(V^{3})[/math].
[math]\triangleleft[/math]

См. также

Источники информации