Введение.

Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира.

60 лет назад, эта задача решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения задачи о максимальном потоке ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов. Асимптотическая оценка его быстродействия превзошла O(nm), о такой скорости многие годы можно было только мечтать. Уверен, что за прошедшие годы алгоритм Голдберга и Рао тщательно изучался и улучшался.

К сожалению, в России, в настоящее время, передовые алгоритмы освещаются слабо. Во всех русскоязычных учебниках, рассматривающих задачу о максимальном потоке в сети, вы вряд ли встретите что-либо, кроме метода пометок Форда-Фалкерсона 60-летней давности. В то время как в зарубежной литературе им редко ограничиваются.

В этой работе, я рассматриваются 12 алгоритмов решения задачи о максимальном потоке, динамические структуры для их реализации, и применение метода Форда-Фалкерсона для выделения Web-групп в WWW.

 

 

Все материалы этого раздела любезно предоставлены Александром Труфановым. Автор выражает благодарность М. А. Бабенко за предоставленные материалы.