Алгоритм Малхотры — Кумара — Махешвари
Алгоритм
Малхотры — Кумара — Махешвари позволяет
находить максимальный поток в
графе.
Рассматривается транспортная
сеть, состоящая из ориентированного
графа ,
где V — множество вершин, E —
множество рёбер, и потока f. Для каждой
вершины вводится
потенциал потока, равный максимальному
дополнительному потоку, который может
пройти через эту вершину. Далее следует
цикл. На каждой его итерации определяется
вершинаr с минимальным потенциалом ρ.
Затем пускается поток величины ρ из
истока в сток, проходящий через эту
вершину. При этом если остаточная
пропускная способность ребра равна
нулю, то это ребро удаляется. Также,
удаляются все вершины, у которых не
остаётся ни одного входящего и/или ни
одного выходящего ребра. При удалении
вершины все смежные рёбра удаляются.
Таким образом, будет найден блокирующий
(псевдомаксимальный) поток. Для того,
чтобы найти максимальный поток в графе,
нужно выполнять поиск блокирующего
потока и затем соответствующим образом
изменять граф, и так, до тех пор, блокирующий
поток не окажется равным нулю.
Если информация
о входящих и исходящих дугах будет
храниться в виде связных списков, то
для того, чтобы пропустить поток, на
каждой итерации будет выполнено действий,
где соответствует
числу рёбер, для которых остаточная
пропускная способность уменьшилась,
но осталась положительной, а —
числу удалённых рёбер. Таким образом,
для поиска блокирующего потока будет
выполнено действий.
Поиск блокирующего потока будет
выполнен раз,
так как количество рёбер на пути от
истока к стоку в блокирующем потоке
будет не убывать. Тогда всего
получается действий.