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

Описание

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

Сложность

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

Литература

• Malhotra V. M., Kumar M. Pramodh, Maheshwari S. N. (англ.) . — 1978.

Примечания