Алгоритм Малхотры

Алгоритм Малхотры

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

Описание

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

Сложность

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

Ссылки

Malhotra V. M., Kumar M. Pramodh, Maheshwari S. N. An O(IVI3) algorithm for finding maximum flows in networks (англ.). — 1978.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Алгоритм Малхотры" в других словарях:

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»