WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

Описание

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

Сложность

Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено действий, где соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а  — числу удалённых рёбер. Таким образом, для поиска блокирующего потока будет выполнено действий. Поиск блокирующего потока будет выполнен раз, так как количество рёбер на пути от истока к стоку в блокирующем потоке будет не убывать. Тогда всего получается действий.

Литература

Примечания

    Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

    Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

    Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




    Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

    Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

    2019-2025
    WikiSort.ru - проект по пересортировке и дополнению контента Википедии