Изменения
→Алгоритм узкого места
===Идея===
Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина <tex>r</tex> с минимальным потенциалом <tex>\rho</tex>. Затем пускается поток величины <tex>\rho</tex> из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.
===Подробное описание===
Для каждой вершины вычислим входящий и исходящий потенциал вершин — сумму пропускных способностей дуг сети Диница, входящих и исходящих из вершины соответственно. Входящий потенциал истока и исходящий потенциал стока положим равными бесконечности. Определим потенциал или пропускную способность вершины в сети как минимум из ее входящего и исходящего потенциалов. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через нее проходить. Ясно, что через вершины с нулевым потенциалом поток проходить не может. Следовательно, их можно удалить из вспомогательной сети. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удаленными. Если в результате появятся новые вершины с нулевым потенциалом, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с ненулевым потенциалом.
После этого приступим к построению блокирующего потока. Пусть вершина <tex>v</tex> принадлежит <tex>k</tex>-ому слою. Протолкнем <tex>p</tex> единиц потока из вершины с минимальным потенциалом в смежные с ней вершины по исходящим дугам с ненулевой остаточной пропускной способностью. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины <tex>v</tex>) проталкиваемый поток соберется в вершинах <tex>(k+1)</tex>-го слоя. Повторим процесс отправки потока из вершин <tex>(k+1)</tex>-го слоя, содержащих избыток потока, в смежные им вершины <tex>(k+2)</tex>-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое. Заметим, что в этом слое содержится только сток, ибо все остальные вершины, ранее ему принадлежащие, были удалены из сети Диница, как вершины, имеющие нулевой потенциал. Следовательно, весь поток величины <tex>p</tex>, отправленный из вершины с минимальным потенциалом полностью соберется в стоке. На втором этапе вновь, начиная с вершины <tex>v</tex>, осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам <tex>(k-1)</tex>-го слоя, затем <tex>(k-2)</tex>-го. И так до тех пор, пока весь потока величины <tex>p</tex>, отправленные из вершины с минимальным потенциалом, не соберется в истоке. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину <tex>p</tex>.
<tex>MPM algorithm(s, t)</tex>
