Максимальный поток в сети и его приложения

— расхождение)
определяется как разность сумм её значений на выходящих и входящих дугах:

 

источник

сток

Г.М. Адельсон-Вельский, Е.А. Диниц,
А.В. Карзанов. Потоковые алгоритмы. М.,Наука, 1975 г.

сети равна 0 .
Внутренние вершины сети – это вершины, отличные от источника и стока.

 

 

 

 

0

 

величина потока f

ФПМИ БГУ

способностью дуги

в классической задаче
нижнее ограничение d(e)=0

 

ФПМИ БГУ

ограничения – целые числа.
Считаем, что любая внутренняя вершина сети лежит на некотором (s,t)-пути (m ≥ n – 1).
Предполагаем, что в сети нет кратных дуг.

ФПМИ БГУ

разрезом.

Утверждение
Для сети G величина любого потока f не превосходит пропускной способности любого разреза R: M(f) ≤ с(R).

2

ФПМИ БГУ

Значит, величина максимального потока не превосходит пропускной способности минимального разреза M(fmax)≤с(Rmin). Поэтому, если для некоторого потока f справедливо, что с(R)=M(f), то это будет означать, что f – максимальный поток.

математик

1955 год (метод Форда-Фалкерсона)

Джек Р. Эдмондс
англ.  Jack Edmonds
1934
США
Научная сфера - комбинаторная оптимизация

1972 год (алгоритм Эдмондса-Карпа)

Ричард Мэннинг Карп
англ. Richard Manning Karp
1935
США
Научная сфера – теория алгоритмов и биоинформатика

Делберт Рей Фалкерсон
англ. Delbert Ray Fulkerson
1924 – 1976
США
Научная сфера - комбинаторика

ФПМИ БГУ

– максимальный поток;
для потока f в сети остаточных пропускных способностей Df нет увеличивающего (s, t)-пути
M(f) = c(R) для некоторого разреза R сети.

ФПМИ БГУ

Теорема Форда ̶ Фалкерсона

Лестер Рэндольф Форд младший
англ. Lester Randolph Ford, Jr.

Делберт Рей Фалкерсон
англ. Delbert Ray Fulkerson

итерация

/ В. М. Котов [и др.]. – Минск : БГУ, 2017. С. 26-30.

По теореме Форда-Фалкерсона текущий поток f - максимальный.

поиск в глубину, то можно выписать следующую оценку
O(сmax·n ·m) - псевдополиномиальный алгоритм

Работает для сетей с целочисленными пропускными способностями дуг.

Время работы: O( M(fmax ) · ? ), где

M(fmax ) – величина максимального потока

? – время поиска увеличивающего пути

ширину;
O(n·m) – число итераций алгоритма;
Поиск увеличивающего пути: поиск в ширину (BFS).
После каждой итерации алгоритма длина dist(s,v) (в дугах) наименьшего пути из источника s в вершину v монотонно не убывает. Так как длина (s,t)-пути не превосходит (n-1), то конечная вершина t может изменять свою метку dist(s,t) не более, чем n раз.
Назовем k-этапом совокупность итераций, на которых длина наименьшего пути сохраняется равной k. Эти итерации идут подряд. На k-этапе после каждой итерации алгоритма из новой сети вычёркивается хотя бы одна дуга, построенного на этой итерации увеличивающего пути и она не может появиться вновь, так как она не является обратной дугам следующих увеличивающих путей k-этапа. Поэтому число итераций алгоритма на k-этапе не превосходит m.
Получаем оценку на число итераций O(n·m).

Время работы:

O(n·m ·(n+m))=O(n · m2),

БГУ

Метод Форда ̶ Фалкерсона
псевдополиномиальный алгоритм

Алгоритми Эдмондса ̶ Карпа
полиномиальный алгоритм

[ (7,4) ]

Представление сети остаточных пропускных способностей на списках смежности

списки смежности для остаточной сети

списки смежности для исходной сети

4: [ ]

в котором выделены две вершины s и t.
(1) Необходимо найти наибольшее число (s,t)-путей, которые попарно не пересекаются по дугам.

(2) Необходимо найти наибольшее число (s,t)-путей, которые попарно не пересекаются по вершинам.

После преобразования решается задача нахождения наибольшего числа (s,t)-путей, которые попарно не пересекаются по дугам (пропускные способности всех дуг сети полагаются равными 1).

Время работы

O(m·n)

ФПМИ БГУ

поток

Время работы алгоритма:

O(m2)

Задан ориентированый граф, в котором выделены два подмножества вершин: V1 и V2.
Необходимо найти наибольшее число путей, которые начинаются в V1 и заканчиваются в V2 и попарно не пересекаются по дугам.

граф).

1

2

4

5

M1={{1,5}, {3,6}}

максимальное паросочетание

M2={{1,4}, {2,5}}

паросочетание

3

6

M3={{1,4}, {2,5}, {3,6}}

наибольшее паросочетание

M4={{1,5}, {1,4}}

НЕ паросочетание

Паросочетание это некоторое подмножество рёбер графа, в котором никакие два ребра не смежны.

maximum matching – наибольшее паросочетание

maximal matching – максимальное паросочетание

совершенное паросочетание

ФПМИ БГУ

Необходимо найти наибольшее паросочетание.

M={{1,4}, {2,5}, {3,6}}

достраиваем
до сети

находим
максимальный
поток

рёбра двудольного
графа, по которым поток
равен 1, включаем
в наибольшее
паросочетание

ФПМИ БГУ

Известно разбиение вершин двудольного графа на доли.
Необходимо найти: наибольшее паросочетание минимального веса в двудольном графе.

|M1|=3, с(M1)=20+4+3=27

сначала найдём
наибольшее
паросочетание

строим
максимальный
поток

рёбра двудольного
графа, по которым поток
равен 1, включаем
в наибольшее
паросочетание

ФПМИ БГУ

2 -> 5 -> 1

новое паросочетание
|M2|=3,
с(M2)=1+7+3=11

контур отрицательного веса: НЕТ

M2={{1,5}, {2,4}, {3,6}} –
наибольшее паросочетание
минимального веса
c(M2 )=11

ориентируем
рёбра графа

перестраиваем
паросочетание

повторяем
процесс

ФПМИ БГУ

двудольном графе;

О(cmax ·m · n2)

ФПМИ БГУ

максимальный вес наибольшего паросочетания
(в паросочетании не может быть более, чем n рёбер), поэтому данной величиной можно оценить наибольшее число итераций поиска контура отрицательного веса;

поиск контура отрицательного веса алгоритмом Форда ̶ Беллмана и перестройка наибольшего паросочетания вдоль контура отрицательного веса

+

О(cmax ·n)

О(n·m)

·

удельная стоимость не является минимальной.

f(e)

c(e)

единицу потока, получим поток той же величины, но стоимость которого меньше на |p'(C)| единиц, чем у текущего потока;

исходная сеть

максимальный поток

сеть остаточных пропускных способностей на последней итерации алгоритма построения максимального потока

и вдоль контура отрицательного веса перераспределяем поток

ФПМИ БГУ

исходная сеть

например, алгоритмом Эдмондса ̶ Карпа

О(cmax · pmax · m · n2 + n · m2)

+

ФПМИ БГУ

наибольшая возможная удельная стоимость максимального потока (по предположению сеть целочисленная и нет кратных дуг)

поиск циклов отрицательной удельной стоимости, например, алгоритмом Форда ̶ Беллмана

О(n · m)

способность >0;
дуге e исходной сети приписываем p(e),
а её обратной дуге приписываем –p(e)

в сети могут быть дуги отрицательного веса, но нет отрицательных контуров; находим кратчайший по удельной стоимости (1,6)-путь:

вдоль данного пути увеличиваем
текущий поток, как и на итерациях
метода Форда-Фалкерсон

 

 

>0;
дуге e исходной сети приписываем p(e),
а её обратной дуге приписываем –p(e)

находим кратчайший по удельной стоимости (1,6)-путь:

вдоль данного пути увеличиваем
текущий поток

 

 

ФПМИ БГУ

>0;
дуге e исходной сети приписываем p(e),
а её обратной дуге приписываем –p(e)

находим кратчайший по удельной стоимости (1,6)-путь:

вдоль данного пути увеличиваем текущий поток

 

 

>0;
дуге e исходной сети приписываем p(e),
а её обратной дуге приписываем –p(e)

находим кратчайший по удельной стоимости (1,6)-путь:

вдоль данного пути увеличиваем текущий поток

 

 

ФПМИ БГУ

>0;
дуге e исходной сети приписываем p(e),
а её обратной дуге приписываем –p(e)

НЕТ (1,6)-пути

 

 

ФПМИ БГУ

m · n2)

О (pmax · m2 · n2)

О(pmax · n · m) · (О(n·m) + О(m) )

ФПМИ БГУ

время работы алгоритма Форда ̶ Беллмана; модификация потока вдоль найденного увеличивающего пути.

число шагов запуска алгоритма нахождения кратчайшего пути (доказательство оценки выполняется по той же схеме, как и в алгоритме Эдмондса ̶ Карпа)

так как сеть целочисленная, нет кратных дуг и на каждой итерации метода минимальных путей строится поток большей величины, то число итераций алгоритма ограничено сверху наибольшей возможной величиной потока конкретной индивидуальной задачи, т.е. cmax · n.

время работы алгоритма Форда ̶ Беллмана; модификация потока вдоль найденного увеличивающего пути.

отрицательных циклов

О(cmax · pmax · m · n2 + n · m2)

оба алгоритма ̶ псевдополиномиальные
О(pmax · m2 · n2)

ФПМИ БГУ

(простая версия) 0.12 Максимальный поток в сети (большие ограничения, по желанию)

ФПМИ БГУ