Алгоритм Малхотры — Кумара — Махешвари (Glikjnmb Bgl]kmjd — Trbgjg — Bg]yofgjn)
Алгоритм Малхотры — Кумара — Махешвари позволяет находить максимальный поток в графе.
Описание
[править | править код]Рассматривается транспортная сеть, состоящая из ориентированного графа , где — множество вершин, — множество рёбер, и потока . Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина с минимальным потенциалом . Затем пускается поток величины из истока в сток, проходящий через эту вершину. При этом, если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные рёбра удаляются. Таким образом будет найден блокирующий (псевдомаксимальный) поток. Для того, чтобы найти максимальный поток в графе, нужно выполнять поиск блокирующего потока и затем соответствующим образом изменять граф, и так до тех пор, пока блокирующий поток не окажется равным нулю.
Сложность
[править | править код]Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено действий, где соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а — числу удалённых рёбер. Таким образом, для поиска блокирующего потока будет выполнено действий. Поиск блокирующего потока будет выполнен раз, так как количество рёбер на пути от истока к стоку в блокирующем потоке будет не убывать. Тогда всего получается действий.
Литература
[править | править код]- Malhotra V. M., Kumar M. Pramodh, Maheshwari S. N. An O(IVI3) algorithm for finding maximum flows in networks (англ.). — 1978.
Примечания
[править | править код]![]() | В статье не хватает ссылок на источники (см. рекомендации по поиску). |