Раздел «Алгоритмы».MaxFlow:

Поиск максимального потока в сети

Аннотация

Дан граф, ребра — это трубы, вершины — это соединения труб. Для каждого ребра (трубы) указана проводимость. Две вершины в графе помечены как исток A и выход B. Нужно найти максимальную проводимость этой сети труб — максимальный поток из A в B. Эта задача решается за полиномиальное время. Два наиболее популярных алгоритма — алгоритм Форда-Фалкерсона и алгоритм "проталкивания предпотока".

Формулировка задачи

Рассмотрим ориентированный граф G = (V,E), каждому ребру (u,v) которого поставлено в соответствие число c(u,v) \ge 0 называемое пропускной способностью ребра. Если c(u,v) не принадлежит графу, то положим c(u,v) = 0. В графе выделим две вершины: исток — s, и сток — t. Такой граф назовем сетью(flow network). Потоком в сети G назовем функцию  f: V\times V \to R, обладающую следующими свойствами:

  1. f(u,v) <= c(u,v).
  2. f(u,v) = -f(v,u)
  3. Закон сохранения жидкости: для каждой вершины (поток входящий) = (поток исходящий) за исключением стока и истока.

Определим величину потока, как сумму f(s, u) по всем вершинам u, т.е. суммарный поток по всем ребрам выходящим из истока.

Тогда возникает задача о максимальном потоке - какой может быть максимальная величина потока в данной сети?

Образно сеть и поток можно представить так: сеть - система труб проводящих жидкость, каждая труба проводит не белее определенного количества жидкости и только в одном направлении. Исток - источник жидкости, а сток приемник. Если открыть исток запустив в сеть жидкость, то она потечет по "трубам" - ребрам к истоку в соответствии с их пропускной способностью. Это собственно и будет потоком. А максимальный поток - величина характеризующая максимальное количество жидкости способное протекать по сети за единицу времени.

Метод Форда-Фалкерсона

Один из способов поиска максимального потока — метод Форда-Фалкерсона:

  1. Положим начальный поток равным нулю.
  2. Пока есть простой путь из истока в сток, по которому можно еще пустить поток, дополняем поток по этому пути.

Наиболее эффективной реализацией метода Форда-Фалкерсона является алгоритм Эдмондса-Карпа, суть которого состоит в том, что поиск пути выполняется обходом дерева в ширину. Для данного алгоритма получается оценка O(V*E*E);

Подробное описание алгоритмов поиска максимального потока  можно найти в книге "Алгоритмы. Построение и анализ" Т. Кормен, Ч. Лейзерсон, Р. Ривест ("Introduction to Algorithms" Thomas Cormen, Charles Leiserson, Roland Rivest) , стр. 536 - 573.

Примеры кода

-- AlexeiKurakin - 06 Apr 2004

Метод проталкивания предпотока

Примеры кода

AlgorithmClasifyForm
Type: Теория
Scope: Графы
Strategy:  
Complexity: High