Центральный Дом Знаний - Алгоритм Малхотры — Кумара — Махешвари

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2653

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Алгоритм Малхотры — Кумара — Махешвари

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

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

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

Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24