Русская Википедия:Алгоритм Малхотры — Кумара — Махешвари

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Алгоритм Малхотры — Кумара — Махешвари позволяет находить максимальный поток в графе.

Описание

Рассматривается транспортная сеть, состоящая из ориентированного графа <math>G=(V,\;E)</math>, где <math>V</math> — множество вершин, <math>E</math> — множество рёбер, и потока <math>f</math>. Для каждой вершины <math>v\in V</math> вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина <math>r</math> с минимальным потенциалом <math>\rho</math>. Затем пускается поток величины <math>\rho</math> из истока в сток, проходящий через эту вершину. При этом, если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные рёбра удаляются. Таким образом будет найден блокирующий (псевдомаксимальный) поток. Для того, чтобы найти максимальный поток в графе, нужно выполнять поиск блокирующего потока и затем соответствующим образом изменять граф, и так до тех пор, пока блокирующий поток не окажется равным нулю.

Сложность

Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <math>O(\left|V\right|+\left|E_i\right|)</math> действий, где <math>\left|V\right|</math> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <math>\left|E_i\right|</math> — числу удалённых рёбер. Таким образом, для поиска блокирующего потока будет выполнено <math>\sum_i{O(\left|V\right|+\left|E_i\right|)} = O(\left|V\right|^2)</math> действий. Поиск блокирующего потока будет выполнен <math>O(\left|V\right|)</math> раз, так как количество рёбер на пути от истока к стоку в блокирующем потоке будет не убывать. Тогда всего получается <math>O(\left|V\right|^3)</math> действий.

Литература

• Шаблон:Статья