ПРИКАСПИЙСКИЙ ЖУРНАЛ

УПРАВЛЕНИЕ И ВЫСОКИЕ ТЕХНОЛОГИИ

Задача нахождения максимального потока в сети

Читать Афонасенков Евгений Владимирович, Степаненко Игорь Александрович Задача нахождения максимального потока в сети  // Прикаспийский журнал:  управление и высокие технологии. — 2012. — №4. — Стр. 31-35.

Афонасенков Евгений Владимирович - аспирант, Волгоградский государственный технический университет, 400005, Российская Федерация, г. Волгоград, пр. Ленина, 28,, stepanenkoigor1988@yandex.ru

Степаненко Игорь Александрович - аспирант, Волгоградский государственный технический университет, 400005, Российская Федерация, г. Волгоград, пр. Ленина, 28,, stepanenkoigor1988@yandex.ru

Данная статья посвящена задаче нахождения максимального потока в сети, т.е. определения оптимального маршрута движения пакетов данных с мест их первоначального расположения к конечному узлу через коммутационный центр. В задаче о максимальном потоке необходимо найти максимальную скорость пересылки продукта от источника к стоку, при которой не будут нарушаться ограничения пропускной способности. Это одна из задач, возникающих в транспортных сетях, и в данной статье приводится эффективный алгоритм ее решения. Более того, основные методы, используемые в рассматриваемом алгоритме решения задач о максимальном потоке, можно применять для решения других задач, связанных с транспортными сетями. В данной статье дается определение таким понятиям, как транспортная сеть, ориентированный граф, ребро графа, а также дается формальное определение задачи о максимальном потоке, приводится словесное описание алгоритма решения поставленной задачи, подробно рассматриваются основные шаги данного алгоритма. Приводится простой пример, иллюстрирующий работу алгоритма по нахождению максимального потока в сети, и в заключение делается вывод о достоинствах и недостатках данного алгоритма.

Ключевые слова: поток,алгоритм,сеть,максимальный поток,граф,задача,узел,источник,коммутационный узел,сток,неориентированная сеть,оптимальный маршрут,пропускная способность,информация